text:
# Tag Info

12

First note that, $$\begin{vmatrix} a & a^2 & a^3+1 \\ b & b^2 & b^3+1 \\ c & c^2 & c^3+1 \\ \end{vmatrix} = \begin{vmatrix} a & a^2 & a^3 \\ b & b^2 & b^3 \\ c & c^2 & c^3 \\ \end{vmatrix} + \begin{vmatrix} a & a^2 & 1 \\ b & b^2 & 1 \\ c & c^2 & 1 \\ \end{vmatrix}=0$$ Then, ...

8

A non - trivial counterexample with $\det A = 0$ and $\det D \neq 0$: Let $$A =\begin{bmatrix} 0 & 0 \\ 1 & 2 \end{bmatrix}$$ and $$D = \begin{bmatrix} -1 & 0 \\ 0 & -2\end{bmatrix}.$$ Then, $$A+D =\begin{bmatrix} -1 & 0 \\1 & 0 \end{bmatrix},$$ with $\det(A+D) = 0$.

8

Consider for trivial counterexample $A=-D$

7

I guess it's easier to go for a reduction formula. I proceed along the generalization mentioned in comment: Call the determinant $M = M_n(x_1,x_2,\cdots, x_n)$ \displaystyle \begin{align}M &= \left|\begin{matrix}\dfrac{1}{x_1+x_1} & \cdots & \dfrac{1}{x_1+x_n}\\ \dfrac{1}{x_2+x_1} & \cdots & \dfrac{1}{x_2+x_n}\\ \cdot & \cdot ... 6 The hard part is to compute the determinants and factor them nicely:  \det\begin{bmatrix}a&a^2&1\\b&b^2&1\\c&c^2&1\end{bmatrix} = (ab^2+bc^2+ca^2)- (b^2c+c^2a+a^2b) = (a-b)(b-c)(c-a)  and \det\begin{bmatrix}a&a^2&1+a^3\\b&b^2&1+b^3\\c&c^2&1+c^3\end{bmatrix} = (ab^2(1+c^3)+bc^2(1+a^3)+ca^2(1+b^3)) - ... 6 You are looking at a special case of the Matrix determinant Lemma. From the Wikipedia page, the proof for the case A = I follows from the equality \begin{bmatrix} I & 0 \\ v^T & 1 \end{bmatrix} \begin{bmatrix} I + uv^T & u \\ 0 &1 \end{bmatrix} \begin{bmatrix} I & 0 \\ -v^T & 1 \end{bmatrix} = \begin{bmatrix} I & u \\ ...

5

Let's rewrite the system as $$\mathbf r \times \mathbf P\mathbf{r} = \begin{vmatrix}\mathbf{i}&\mathbf{j}&\mathbf{k}\\x&y&z\\z&x&y\end{vmatrix} = 2\mathbf{i} + 3\mathbf{j} + 1\mathbf{k} \equiv \mathbf f$$ where $\mathbf{r} = (x,y,z)^\top$ and $$\mathbf P = \begin{pmatrix} 0 & 0 & 1\\ 1 & 0 & 0\\ 0 & 1 & 0 ... 5 Given x^2-yz = 1, \quad y^2-xz = 2, \quad z^2-xy = 3, we can sum all of these to get$$(x-y)^2+(y-z)^2+(z-x)^2 = 12 \tag{1}$$OTOH, subtracting gives (y^2-x^2)+z(y-x)=1 \implies (x+y+z)(y-x) = 1 and similarly (x+y+z)(z-y) = 1, so we must have y-x = z - y = a, say. Using this in (1),$$a^2+a^2+4a^2=12 \implies a = \pm \sqrt2$$So we have y = x ... 5 The main thing you need to use is: For any matrix A, Ax = \lambda x is true if and only if (A-I)x = (\lambda - 1)x 5 We consider a general case. Let$$ |A|=\left|\begin{array}{}{\dfrac1{a_1+b_1}\cdots\dfrac1{a_1+b_n}\\ \vdots\hspace{20 mm} \vdots \\\dfrac1{a_n+b_1}\cdots\dfrac1{a_n+b_n}} \end{array}\right| $$In your case, just set a_i=i,b_j=j. By multiplying i^{th} row with \prod\limits_{j=1}^{n}(a_i+b_j) each, we have$$ ...

5

Define $C:=AB^{-1}$, which is possible since $B$ is invertible. Then $$CB=(AB^{-1})B=A(B^{-1}B)=AI=A$$ and $$\det(C)=\det(A)\det(B^{-1})=\frac{\det(A)}{\det(B)}=1$$

4

For part $(a)$ you are almost done. If $\mathrm{det}(A)=0$ and $$A=\begin{bmatrix} a_1 & a_2 & a_3 \\ a_4 & a_5 & a_6 \\ a_7 & a_8 & a_9 \end{bmatrix},$$ then $(a_1,a_2,a_3)=c_1(a_4, a_5, a_6)+c_2(a_7,a_8,a_9)$ for some $c_1,c_2 \in \mathbb{R}$. Note that $c_1, c_2 \neq 0$ by assumption since $a_i \neq a_j$ whenever $i \neq j$. By ...

4

Hint: This is a rank one update of a diagonal matrix. In particular, we have $$M = \pmatrix{ 1-n\\ &2-n\\ && \ddots\\ &&& 0 } + n \cdot xx^T$$ where $x = (1,\dots,1)^T$. We can find the determinant of this matrix using Sylvester's determinant theorem (more specifically, using the matrix determinant lemma). Full Solution: Let ...

4

There does exist a notion of exterior powers of modules over arbitrary (commutative) rings, and they can be defined almost exactly the same way as for vector spaces. Here is a reference that goes through the details. Using this definition, the proof that determinants are multiplicative over a field generalizes straightforwardly to arbitrary rings. ...

3

The resultant of $x^2-yz-1$ and $y^2-xz-2$ with respect to $z$ is $x^3-y^3-x+2y$. The resultant of $x^2 - yz - 1$ and $z^2 - xy - 3$ with respect to $z$ is $x^4-x y^3-2 x^2-3 y^2+1$. The resultant of $x^3-y^3-x+2y$ and $x^4-x y^3-2 x^2-3 y^2+1$ with respect to $x$ is $-y^4(18 y^2-1)$. So either $y = 0$ or $y = \pm 1/\sqrt{18}$. With $y=0$ we get $x^2 - ... 3 Let$z$denote the vector consisting of only$1$s. We can write$A$as $$A = zz^T - I$$ In particular, $$Ax = zz^Tx - Ix = \langle z,x \rangle z - x$$ Now, consider two cases: first, suppose that$x=z$. We then have $$Ax = Az = \langle z,z \rangle z - z = (\langle z,z \rangle - 1)z$$ Next, suppose$x$is perpendicular to$z$. We then have $$Ax ... 3 All OK except \det(2B). Remember that if you multiply a row/column of a matrix by 2, the determinant is multiplied by 2. If you multiply the entire matrix by 2, then you are multiplying each row (or equivalently, each column) by 2. Since there are 3 rows/columns in the matrix, you are multiplying by 2 three times, so$$\det(2B) = 2^3 \det(B) = ... 3 The determinant of a$3\times 3$matrix is just the area of the parallelepiped spanned by it's column vectors. If you think about the problem geometrically, I think it's a bit easier to see why your answer should be correct. 3 Lemma. If positive numbers$a_1,a_2,a_3,a_4$have at least two different values, then they can be put into a$2\times 2$matrix so that the determinant is nonzero. Proof: Suppose that$0 < a_1\leq a_2\leq a_3\leq a_4$, where not all the$a_i$'s are the same. Then$a_1a_2 < a_3 a_4$, so the matrix$\begin{bmatrix}a_3 & a_1 \\ a_2 & ...

3

The answer is"No". Look at a diagonal matrix $D = \text{diag} (d_1, d_2, \ldots, d_n)$ with $d_i \ne 0$, $1 \le i \le n$; then in fact $\det D \ne 0$. Form $A$ from $D$ by replacing at least one $d_i$ with $-d_i$ and at least one $d_j$, $j \ne i$, by $0$· Then $\det A = 0$ and $D + A$ is a diagonal matrix with (at least) $(D + A)_{ii} = 0$, whence $\det ... 3 The block matrix (let us denote by$M$) can be expressed as the Kronecker product of matrices$A$and$I$(the fixed size identity matrix, of dimension$n$) as follows:- $$M=A\otimes I$$ where$A$is the$3\times3$matrix:- $$A=\left[\begin{array}{ccc} \frac{3}{4} & \frac{1}{4} & \frac{1}{4} \\ \frac{1}{4} & \frac{3}{4} & -\frac{1}{4} \\ ... 2 Here c,d are rows and not vectors. There is a formula that is valid for any b (the last equality in kubek's proof is false). According to [Horn, Johnson "Matrix Analysis" (2013), 0.8.5.10 ], one has \det(M)=b\det(A)+c. adj(A).d^T, where adj(A) is the classical adjoint of A. 2 why not just use the Laplace expansion of a determinant ? u can read how exactely it is done in here: https://en.wikipedia.org/wiki/Laplace_expansion in case you don't understand it, or you prefere a step by step tutorial on how to do it u can watch this. it's only 5 minutes: https://www.youtube.com/watch?v=6fmgMTJBWtY or if u are truly lazy, u can just ... 2$$\det \begin{pmatrix} (b+c)^2 & a^2 &a^2\\ b^2 & (c+a)^2 & b^2\\ c^2&c^2&(a+b)^2 \end{pmatrix}\det \begin{pmatrix} (b+c)^2-a^2 & 0 & a^2\\ 0 & (c+a)^2-b^2 & b^2\\ c^2-(a+b)^2 & c^2-(a+b)^2 & (a+b)^2 \end{pmatrix}$$By C_1-C_3, C_2-C_3$$\det \begin{pmatrix} (b+c+a)(b+c-a) & 0 & a^2\\ 0 & ... 2 Take the column$k$. If we denote$x^k=z$then it looks like $$\left[\matrix{z-1\\ z^2-1\\z^3-1\\ \vdots\\ z^n-1}\right]=(z-1)\left[\matrix{1\\ z+1\\z^2+z+1\\ \vdots\\ z^{n-1}+\ldots+z+1}\right].$$ Now use the top row of ones to eliminate all other ones and$z$to eliminate all other$z$and so on $$(z-1)\left[\matrix{1\\ z+1\\z^2+z+1\\ \vdots\\ ... 2 Call your matrix A. If X=(a,b,c,\ldots,f)^T is a column vector then the polynomial$$ p(y) = ay+by^2+cy^3+\cdots+fy^n-(a+c+d+\cdots+f) $$applied to x, x^2, x^3, \ldots, x^n will produce the elements of AX. If AX=0, then accordingly x, x^2, x^3, \ldots, x^n are all roots of p. We can also see directly that 1 is a root of p. If the powers ... 2 Here is the difference between the two concepts: The Jacobian is an m\times n matrix and it consists of first-order derivatives of all the variables of a given function f. The Jacobian matrix is an m\times n matrix that gives the best linear approximation of f near the point x\in \mathbb{R}^n. If we have a square matrix, then ... 2 \det(-3A) = (-3)^5 \det(A). Because in general: if A is an n \times n matrix, we have \det(xA) = x^n \det(A). Thus,$$\det(A) = \frac{-4}{3^5}$$Your$\det(B)$is correct. Finally,$\det(AB) = \det(A) \times \det(B)$. 2 Thought Samrat Mukhopadhyay"s answer is of course in principle correct, it provides no justification for the stated multiplicities of the eigenvalues. In what follows, I have tried to explain, amongst other things, just how these multiplicities arise. If$u = 0 \;\; \text{or} \;\; v = 0 \tag{1}$we have$uv^T = 0 \tag{2}$and$v^Tu = 0; \tag{3}$then ... 2 This is the correct formulation for the$2\times 2\$ case but you still need to prove that these formulas work. So, to finish you must show that \begin{array}{crcrcrcrcr} a_1\dfrac{D_1}{D} &+& b_1\dfrac{D_2}{D} &=& c_1 \\ a_2\dfrac{D_1}{D} &+& b_2\dfrac{D_2}{D} &=& c_2 \end{array} The first of these two equations is proved by ...

Only top voted, non community-wiki answers of a minimum length are eligible

format: plain


text:
# Ray Tracer

## Recommended Posts

Hello, I m building a ray tracer and something really weird goes on :P Global variables:
D3DXVECTOR3 camPos(0.0f, 0.0f, -10.0f);
float fovW = (45.0f)*3.14f/180;
float fovH = (float)HEIGHT / (float)WIDTH * fovW;

I create 5 balls (0, 1, 50.0f) (0, -3, 100.0f) (2, 0, 90.0f) (-1, 0, 75.0f) (-4, 4, 75.0f) and one light at (0,0,1000) To create the ray for each pixel I use the following for its direction and the camera position as its origin:
float xz = ( (2.0f * (float)x) - (float)WIDTH) / (float)WIDTH * tanFovW;
float yz = ( (2.0f * (float)y) - (float)HEIGHT) / (float)HEIGHT * tanFovH;

D3DXVECTOR3 m_direction = D3DXVECTOR3(xz- camPos.x, yz-camPos.y, -camPos.z);
NORMALIZE(m_direction);

Notice that light is further ahead of every ball and the camera yet I get as a result: Also regardless of whether the objects are in shadow I get the same result :S Any ideas why I am getting this result and not proper normalized spheres even though I calculate lambert
//90+ degrees
if (lambert > 0)
{
const float DIFFUSE_COEF = 0.8f;
tempSphere->color = lambert * DIFFUSE_COEF;
}

##### Share on other sites
Yo can't do this:

fovH = (float)HEIGHT / (float)WIDTH * fovW;

These are angles, you can't "scale" an angle like that! Use trigonometry.

You should post some relevant code too (lighting calculations)
Shadows? shadows won't be generated "by themselves". Do you handle it at all? Post the relevant codes.

##### Share on other sites
Quote:
 These are angles, you can't "scale" an angle like that! Use trigonometry.
yeah I actually don't know how this field of view is created or the way i direct the rays to the pixel, I had a similar post but it wasn't clarified.

as for the code:

for each pixel of the screen{  Final color = 0;  Ray = { starting point, direction };  Repeat   {    for each object in the scene    {      determine closest ray object/intersection;    }      if intersection exists     {      for each light in the scene      {        if the light is not in shadow of another object        {          add this light contribution to computed color;        }            }    }    Final color = Final color + computed color * previous reflection factor;    reflection factor = reflection factor * surface reflection property;    increment depth;  } until reflection factor is 0 or maximum depth is reached;}

[Edited by - Tipotas688 on March 30, 2010 4:26:14 AM]

##### Share on other sites

That should give you some hints about the geometry.

Your code is unclear for me.

If you normalize the light direction, you mustn't divide it again with the length of it.

lambert = DOT(sufaceNormal, lightDirection); // don't divide with lightDistance
//since

I can only spot this at the moment.

##### Share on other sites

as for my code I m mostly following this algorithm: http://www.codermind.com/articles/Raytracer-in-C++-Part-I-First-rays.html

##### Share on other sites
I can only say one thing: Ray-casting/tracing is the most straightforward way of rendering. You take everything from life. You cast a ray, and see what happens with it.

What I'm trying to say: I think it's better to make the basic ray-tracing all by yourself, without articles/algorithms(basic ray-casting don't even need algorithms-optimization needs algorithms)/tutorials. It requires the most basic linear algebra: line-intersection,dot/cross product,some trigonometry. You have to fully understand the method, or you will only copy code, and struggle with debugging it.

By the way: did the normalization stuff do the job?

##### Share on other sites
I had already tried taking out the division in the first place as I thought it didn't make any sense but I put it back since it was in the guide as you said.

You are right in saying that I don't need a guide to do all that, to be honest I took out everything that was implemented to find the intersections and turned it all in maths which makes it much clearer.

What do you have to say about the camera-objects-light positioning, it is really confusing me how they are placed and the result I m getting, I should be getting shadowed spheres as light lights them in the other direction instead they appear flat as if I didn't do any light calculations

##### Share on other sites
Here:
NORMALIZE(pointOfIntersection); you normalize a position. You can't normalize a position, only a direction. Then you use this normalized position, to calculate the light direction: wrong. Use the un-normalized position (But again: normalizing a position is wrong)

This will be the problem, you don't take the normals well: I don't know what this line does:
D3DXVECTOR3 sufaceNormal = tempSphere->GetNormal(pointOfIntersection);

I just don't know how to get the normals with the classes you have (that's why I only program in C, this class stuff just ties your hands, if you're not an expert in C++)

In my C ray-tracer, I simply know the index of the intersected triangle (since it's not "hidden" in a class). Maybe you could access the index yourself too, so you can get the vertex normals of the triangle. Then you have to interpolate between the 3 normals, I guess there's a function for that in your math class.

I try to summarize:
-you cast a ray (that's okay, since you have the spheres displayed)
-you calculate the intersection point's coordinates (int_pos) (that's okay)
-you calculate the light direction: light_pos-int_pos
-you normalize the light direction
-you get the normal of the intersection point somehow
-you calculate the dot product of the normalized light direction and the normal
-you check for shadows (that's okay)
-etc

EDIT: maybe D3DXVECTOR3 sufaceNormal = tempSphere->GetNormal(pointOfIntersection); works like this:

you have to calculate the intersection point coordinates in the sphere's space. I don't know how to do that, because I don't know how the classes work.
But this intersection point has to be a temp variable! If you use it later, everything will be screwed up, if you get what I mean.

Or maybe the clas does everything for you: so

Don't normalize the intersection point!

##### Share on other sites
D3DXVECTOR3 Sphere::GetNormal(D3DXVECTOR3 p){	D3DXVECTOR3 normal = p - position;	Normalize(normal);	return normal;}

thats how i get the normal on a point.

To be honest I am using algorithms and guides since I am no expert in C++, but then again I think that C#/Java is not a good language to make a ray tracer, C and C++ are better, so I m trying to learn the language and do the ray tracer. I know its wrong to try multiple stuff like that but I hope I ll manage.

##### Share on other sites
I see. That's fine for a sphere.

So don't normalize intersection point!! Never!!

##### Share on other sites
I still don't understand though what is going wrong with my ray tracer as the position of light is completely wrong and works, also even after modifying all that I still get the same picture as above :S

##### Share on other sites
if(intersected)	{		std::list<Light*>::iterator j;		for(j=lightList.begin(); j != lightList.end(); ++j)		{			D3DXVECTOR3 pointOfIntersection = ray.origin + ray.destination*minimumIntersectDistance;			//NORMALIZE(pointOfIntersection);			D3DXVECTOR3 sufaceNormal = tempSphere->GetNormal(pointOfIntersection);			D3DXVECTOR3 lightDirection = (*j)->position - pointOfIntersection;			//float lightDistance = sqrtf(lightDirection.x*lightDirection.x + 				//lightDirection.y*lightDirection.y + lightDirection.z*lightDirection.z);			NORMALIZE(lightDirection);			if(ShadowRay(pointOfIntersection,(*j)->position))			{												float lambert = DOT(sufaceNormal, lightDirection);// / lightDistance;								if (lambert > 0)				{					const float DIFFUSE_COEF = 0.8f;					tempSphere->color = lambert * DIFFUSE_COEF;				}			}	}	if(GetRValue(tempSphere->color)>255)		tempSphere->color = RGB(255,GetGValue(tempSphere->color),GetBValue(tempSphere->color));		if(GetGValue(tempSphere->color)>255)			tempSphere->color = RGB(GetRValue(tempSphere->color),255,GetBValue(tempSphere->color));		if(GetBValue(tempSphere->color)>255)			tempSphere->color = RGB(GetRValue(tempSphere->color),GetGValue(tempSphere->color),255);		return tempSphere->color;	}
This should be fine now.

##### Share on other sites

DON'T NORMALIZE INTERSECTION POINT!! NEVER EVER!!

##### Share on other sites
Haha yeah I don't

D3DXVECTOR3 pointOfIntersection = ray.origin + ray.destination*minimumIntersectDistance;//NORMALIZE(pointOfIntersection);

Something really interesting happens now when I put the light on a better place: camera(0,0,-1000)

##### Share on other sites
Okay, I have no idea what these lines are doing:
if(GetRValue(tempSphere->color)>255)		tempSphere->color = RGB(255,GetGValue(tempSphere->color),GetBValue(tempSphere->color));		if(GetGValue(tempSphere->color)>255)			tempSphere->color = RGB(GetRValue(tempSphere->color),255,GetBValue(tempSphere->color));		if(GetBValue(tempSphere->color)>255)			tempSphere->color = RGB(GetRValue(tempSphere->color),GetGValue(tempSphere->color),255);		return tempSphere->color;
comment these out, and see what happens.

##### Share on other sites
Those lines get the RGB values to be at most 255 and not above

##### Share on other sites
Quote:
 Original post by Tipotas688Haha yeah I don't*** Source Snippet Removed ***Something really interesting happens now when I put the light on a better place: camera(0,0,-1000)
Hey! those pictures are fine!
You don't map the colors properly, try to divide the output color with 256.0

And post the code of the shadow-ray stuff.

##### Share on other sites
Try to place the light in a more arbitrary position: I guess it's now behind the camera. Of course you don't see shadows.

##### Share on other sites
If I divide with 256 then I get a black screen :S

if I do:

I get the first picture

[Edited by - Tipotas688 on March 30, 2010 11:36:15 AM]

256.0
or (float)256

##### Share on other sites
And do this division in the display code.

Calm down a bit: you return a DWORD: 0-255
Your display stuff (directX) probably uses float: 0.0-1.0

Keep this in mind, and modify either the output of the ray-trace, or the display color mode.

##### Share on other sites
I am doing a SetPixel(hdc, i, j, color); which uses COLORREF

##### Share on other sites
I changed the way I set the color since it creates a hex out of some floats, and I don't think it should work this way so:

BYTE r = GetRValue(tempSphere->color)+DIFFUSE_COEF * lambert;BYTE g = GetGValue(tempSphere->color)+DIFFUSE_COEF * lambert;BYTE b = GetBValue(tempSphere->color)+DIFFUSE_COEF * lambert;tempSphere->color = RGB(r, g, b);

but now its:

##### Share on other sites
Sorry, I told you everything I could.

##### Share on other sites
well if the rest seem fine to you then I ll try to learn how to convert those float-bytes-hex values into something colorful.

Thanks a lot for your time, shall I post the current version again?

## Create an account

Register a new account

• ### Forum Statistics

• Total Topics
627715
• Total Posts
2978782

• 9
• 21
• 14
• 12
• 42


text:
×

# Multi-Pole Problem

So we all know the infamous Two-Pole Problem, which doesn't rely on the distances between the two poles. I have a situation where there are a n poles. Each pair of consecutive poles is used to create a Two-Pole situation, thus creating n-1 shorter poles. Using these, n-2 shorter poles are created in a similar fashion. This continues until there is one pole, which for reference I will call the "supporting pole". if $$x_{1}, x_{2}, x_{3}, ..., x_{n}$$ are the lengths of the starting poles, find a formula for the length of the supporting pole in a n-Pole Problem.

Note by Tristan Shin
2 years, 9 months ago

Sort by:

$$\frac{1}{\sum_{i=1}^n\frac{1}{x_{i}}}$$ · 2 years, 9 months ago

That's close. Try a few other cases that can disprove this(try 5 poles, for instance). · 2 years, 9 months ago

I don't get it...so please can you reveal the answer...:) · 2 years, 9 months ago

I think now you should reveal the solution..... · 2 years, 9 months ago

I'll reveal this solution within the next week(April 21-April 25). · 2 years, 9 months ago

For clarification, the Two-Pole Problem is where there are two poles of length a and b. Lines are drawn from the top of each to the bottom of the other. From the intersection of these two new lines, a vertical line segment parallel to the original poles is drawn. It turns out that the distance between the two poles is irrelevant. To solve this problem, try playing around with a few two-pole scenarios. · 2 years, 9 months ago

I don't know that problem (you said it's infamous then why not show it) · 2 years, 9 months ago

We use the formula $$\dfrac{1}{x}+\dfrac{1}{y}=\dfrac{1}{z}$$ where $$x,y$$ are the two poles and $$z$$ is the height of the middle pole. Solving for the supporting pole is pretty trivial, just plug 'n' chug. · 2 years, 9 months ago


text:
Worksheets

• Worksheet 1: Balancing Redox Reactions
The half-equation method separates the oxidation and reduction of a redox reaction in half reactions. Overall scheme for the half reaction method is discussed with examples to follow.
• Worksheet 2: Galvanic Cells
The batteries in your remote and the engine in your car are only a couple of examples of how chemical reactions create power through the flow of electrons. The cell potential is the way in which we can measure how much voltage exists between the two half cells of a battery. We will explain how this is done and what components allow us to find the voltage that exists in an electrochemical cell.
• Worksheet 3: Complex Ions & Nomenclature
Transition metal ions and some main block elements form coordination compounds which typically consist of a coordinate complex and counter ions. Coordination complexes are composed of ligands surrounding a central metal atom or ion. The coordinate complex itself consists of a transition metal atom or ion and the surrounding ligands. The coordinate complex is always enclosed in square brackets, [ ]. The coordinate complex can be an ion, cation or anion, or a neutral complex.
• Worksheet 4: Complex Ion Structure and Geometry
As you have seen in the chemistry of carbon‐containing compounds, often there are several isomers possible for the same compound formula. Even when atoms are connected in the same order it is possible that we have not uniquely described the structure of the molecule. Isomers have unique properties.
• Worksheet 5: Crystal Field Theory
Crystal field theory is one of the simplest models for explaining the structures and properties of transition metal complexes. The theory is based on the electrostatics of the metal-ligand interaction, and so its results are only approximate in cases where the metal-ligand bond is substantially covalent. But because the model makes effective use of molecular symmetry, it can be surprisingly accurate in describing the magnetism, colors, structure, and relative stability of metal complexes.
• Worksheet 6: Magnetism and Colors in Coordination Complexes
According to Crystal Field Theory, the interaction between a transition metal and ligands arises from the attraction between the positively charged metal cation and negative charge on the non-bonding electrons of the ligand. The theory is developed by considering energy changes of the five degenerate d-orbitals upon being surrounded by an array of point charges consisting of the ligands. As a ligand approaches the metal the loss of degeneracy occurs.
• Worksheet 7: Kinetics I
Chemical kinetics is the study of the rates of chemical reactions; i.e., how fast reactants are converted into products. Experimentally determined rate law expressions show how the rate of a reaction depends upon the concentrations of the reactants and sometimes the products, too. This knowledge can be used to gain insight into the detailed molecular pathway (the mechanism) by which the reaction occurs. Understanding the mechanism allows chemists to devise ways of improving or modifying a chemic
• Worksheet 8A: Kinetics II
This worksheet covers once again the idea of how we define the Rate on the basis of the reaction’s stoichiometry, and it reviews the process of determining the form of the differential rate law from kinetic data. The differential rate law shows how the rate of the reaction changes with concentration of reactants (and sometime products). The integrated rate law, which is derived by means of calculus from the differential rate law, shows how the concentration of reactant changes with time.
• Worksheet 8B: Kinetics III
The half life of a first-order process is a constant that indicates the amount of time it takes for an initial concentration to diminish to half as much material. All chemical reactions have a faster rate at higher temperature. From this we can conclude that the magnitude of the rate constant, k, increases with rising temperature. This behavior is related to the energy barriers associated with the mechanism of the reaction, the set of molecular-level steps by which the reaction proceeds.
• Worksheet 9: Fundamentals of Nuclear Chemistry
Nuclear reactions are going on all around us. Using correctly balanced equations is important whetting to understand nuclear reactions. All equations need to be balance to conform to two conservation laws: The mass number and the electrical charge.
• Worksheet 10: Transmutation and Nuclear Kinetics
This worksheet addresses three basic principles of nuclear chemistry: (1) Energetics (via Binding energy and $$E=mc^2$$, (2) Kinetics (via 1st order reactions), and (3) fission and fusion process (artificial nuclear reactions).


text:
# Construction of symmetry group algebra

In Kitaev's reasoning of constructing the algebra of symmetry group, he said,

"considering the symmetry group G of a fermionic system and a map $$\alpha$$ $$\alpha: G \rightarrow \mathbb{Z}_2$$ where $$\alpha$$ is the indicator that determines whether the group element is unitary or anti-unitary ,then we consider a element in the center of the $$G$$ $$p \in Z(G)$$ where $$P$$ is the fermionic parity operator $$P = (-1)^{N}$$, N is the number of particles, we can easily know that $$P$$ is unitary so that $$\alpha(P) = 1$$ ,then we can construct the "group algebra"(not sure whether it is called like this?) $$\mathscr{A} = \mathbb{R}[G]/(P+1)$$ "

First of all, what is $$\mathbb{R}[G]$$?

It seems like a clifford algebra construction but I have no idea of how these things are organized, especially how to calculate $$\mathscr{A}$$? Hope that someone could give me a logical picture of how things go.


text:
# Chapter 12 Output Hooks (*)

With the knitr package, you have control over every piece of output from your code chunks, such as source code, text output, messages, and plots. The control is achieved through “output hooks.” Output hooks are a series of functions that take a piece of output as the input (typically a character vector), and return a character vector to be written to the output document. This may not be easy to understand for now, but hopefully you can see the idea more clearly with a small example below explaining how the output of a simple code chunk is rendered through knitr’s output hooks.

Consider this code chunk with one line of code:

{r}
1 + 1

After knitr evaluates the code chunk, it gets two output elements, and both are stored as character strings: the source code "1 + 1", and the text output "[1] 2". These character strings will be further processed by chunk hooks for the desired output format. For example, for Markdown documents, knitr will wrap the source code in a fenced code block with a language name. This is done through the source hook, which more or less looks like this function:

# for the above case, x is a character string '1 + 1'
function(x, options) {
# the little 'r' here indicates the language name
paste(c("r", x, ""), collapse = "\n")
}

Similarly, the text output is processed by the output hook that looks like this function:

function(x, options) {
paste(c("", x, ""), collapse = "\n")
}

So the final output of the above code chunk is:

r
1 + 1

[1] 2

The actual hooks are more complicated than the two functions above, but the idea is the same. You may obtain the actual hooks from the object knit_hooks via the get() method, e.g.,

# for meaningful output, the code below should be
# executed *inside* a code chunk of a knitr document
knitr::knit_hooks$get("source") knitr::knit_hooks$get("output")
# or knitr::knit_hooks$get(c('source', 'output')) Unless you are truly interested in making contributions to the knitr package, we do not recommend that you read the source code of these built-in hooks. If you are interested, this code can be found in the scripts named in the form hooks-*.R at https://github.com/yihui/knitr/tree/master/R (e.g., hooks-md.R contains hooks for R Markdown documents). As a knitr user, it usually suffices if you know how to create custom output hooks by taking advantage of the built-in hooks. You will learn that in several examples in this chapter, and we show the basic idea below. A custom output hook is registered through the set() method of knit_hooks. Because this method will override the existing default hook, we recommend that you save a copy of an existing hook, process the output elements in your own way, and pass the results to the default hook. The usual syntax is: # using local() is optional here (we just want to avoid # creating unnecessary global variables like hook_old) local({ hook_old <- knitr::knit_hooks$get("NAME")  # save the old hook
knitr::knit_hooks$set(NAME = function(x, options) { # now do whatever you want to do with x, and pass the # new x to the old hook hook_old(x, options) }) }) Here, NAME is the name of the hook, which can be one of the following values: • source: processing the source code. • output: processing text output. • warning: processing warnings (usually from warning()). • message: processing messages (usually from message()). • error: processing error messages (usually from stop()). • plot: processing plot file paths. • inline: processing output from inline R expressions. • chunk: processing output from the whole chunk. • document: processing the whole document. The meaning of the argument x in the hook functions is explained in the above list. For the options argument of a hook, it denotes the chunk options (as a list) for the current code chunk. For example, if you set foo = TRUE on a chunk, you can obtain its value via options$foo in the hook. The options argument is not available to the inline and document hooks.

Output hooks give you the ultimate control over every single piece of your chunk and document output. Compared with chunk options, which often have predefined purposes, output hooks can be much more powerful since they are user-defined functions, and you can do anything you want in functions.


text:
# What is the meaning of the optimal input probability distribution for a noisy channel in information theory

While trying to understand Shannon's information theory, I never quite managed to get an intuitive feeling for the "optimal input ensemble probability distribution" $$p^*_x$$, which is the distribution that maximizes the mutual information of a channel and gives its capacity

$$C = max_{p_x} I(X;Y)$$.

Specifically, I'm not sure if $$p^*_x$$ provides any insight as to how to construct a code which allows us to communicate efficiently through a channel.

Take for example the "noisy typewriter", through which you are able to send all 26 English letters, but for each letter you send, the channel may output either that letter, or the next one, so A can become either A or B, M can become M or N etc. If you calculate the capacity of such a channel using standard methods, you get $$C=log_2 13$$ bits and $$p^*_x$$ a uniform distribution over the input alphabet. However, for this channel it's easy to devise an optimal coding strategy - just use every other letter, A, C, E..., because they produce outputs fully distinguishable from each other. Since there are now 13 letters you can send with perfect decodability, you can transmit $$log_2 13$$ bits per channel use so this strategy achieves the previously calculated capacity. It turns out, that a uniform distribution over every other letter in the alphabet, call it $$p^{*'}_x$$, ($$p_A = 1/13$$, $$p_B = 0$$, $$p_C = 1/13$$...) also maximizes the capacity. So now we're left with a conundrum - both $$p^*_x$$ and $$p^{*'}_x$$ achieve capacity, but the latter gives an understanding of how the channel can be effectively used, and the former doesn't really say much at all (certainly interpreting it as "use all letters equally often" doesn't lead to a efficient coding strategy).

If so, how do you interpret any other capacity achieving distributions for different channels? Or, why this methodology of assigning probabilities to input symbols and calculating the most optimal ones gives us any clue as to how we should go about sending any message of our own through a noisy channel?

• The codebook should have those symbols appearing with those fractions of occurrence. If we have binary symbols and the optimal input distribution has p(1)=3/4, then codewords should roughly have 1s appearing 75% of the time. Mar 3 '20 at 1:23
• If multiple input distributions maximize, it is possible to construct codewords according to each different distribution, so there are multiple optimal codes. It is easy to do: use the first code (using only a,c,e,...) for even letters and the second (b,d,f...) for odd (this uniformly uses all letters). Mar 3 '20 at 1:27
• Thank you, this does provide intuition. Could you point to some theoretical argument in which it is either derived that "the codebook should have those symbols appearing with those fractions of occurrence" or stated from the beginning, that the input alphabet probabilities correspond to frequencies of symbols in the codebook? I guess part of my confusion stems from the "every-day" understanding of sending messages as in "I want to send a single telegram", while Shannon's theory is in some way asymptotic and thus not directly applicable to single messages, or am I incorrect in saying that? Mar 3 '20 at 1:47
• Suppose p(0) = p(1) = 0.5. An "every-day" question one could ask is: ok, so what if the probabilities of 0 and 1 should be equal. I want to send the message 111010 and none other, and I need to send it in this particular order and length". I suppose the answer would be: "the distribution p(0)=p(1)=0.5 only tells us that 0s and 1s should be used equally frequently when you average over all possible messages, it doesn't tell us anything about how to transmit this specific 111010 message". Mar 3 '20 at 1:52
• Shannon tells us that we can form a codebook randomly by generating codewords according to iid symbols with distribution close to the optimal input distribution. Mar 3 '20 at 2:05

If you calculate the capacity of such a channel using standard methods, you get $$C=log_2 13$$ bits and $$p_x$$ a uniform distribution over the input alphabet
Not quite. What you get is $$I(X;Y)=H(Y)-H(Y|X)=H(Y)-1$$ bits, which is bounded by an uniform output distribution $$p_y$$, with $$H(Y)=\log 26$$ bits. Then comes the realization that a uniform $$p_y=1/26$$ can be obtained by a uniform input $$p_x=1/26$$ - but this not the only solution, you could alternate the probabilities $$P_x(A)=1/13$$ $$P_x(B)=0$$ $$P_x(C)=1/13$$ etc.


text:
Is empty set a subset of every set direct proof confusion

Followup to the accepted answer of this question Direct proof of empty set being subset of every set

I understood the answer based on the nature of vacous truth, however what if we verify a statement $\forall A \forall x, x\in \emptyset$ it holds that $x \notin A$ then this statement also becomes vacously true. Now this means $x \notin A$ is true as well.

Am I missing something, could you please explain?

If you mean that every member of the empty set is not a member of $A$, then yes, you are correct. This statement is vacuously true.

There are no members to the empty set.

The point is that the definition of $X\subseteq Y$ is universal, i.e. given by $\forall x$, whereas the definition of $X\nsubseteq Y$ is existential, i.e. given by $\exists x$. So in order to prove that $\varnothing\nsubseteq A$, one needs not to verify that $\forall x\in\varnothing:x\notin A$, but rather than $\exists x\in\varnothing: x\notin A$, and the latter is indeed false.

If I've understood correctly, you are concerned about the statement $$\forall A, \forall x \in \varnothing : x \notin A.$$

Indeed, since $\forall x \in \varnothing$ is a statement about nothing, the statement is vacuously true. However, it does not mean that $\forall x : x \notin A$. In fact, the statement says pretty much nothing about $A$. To see why, we can write the statement above without syntactic sugar; it then becomes $$\forall A, \forall x : x \in \varnothing \Rightarrow x \notin A.$$

Since the premise $x \in \varnothing$ is always false, the implication is always true, and so the entire quantified statement is true. Note how the truth of this statement says nothing definite about $A$.

Let me know if I've misunderstood your question.


text:
# Why does liveiso-to-disk command exist if there already is the dd command?

I mean...is there any difference between these two commands? (regarding the matter of burning an livecd iso into an usb pen). Thanks!

edit retag close merge delete

I think liveiso-to-disk was supposed to make things easier, and be more specific to creating live USB drives. Unfortunately, I've found that liveiso-to-disk is less reliable than a simple dd...

( 2013-09-24 16:27:40 -0500 )edit

Sort by » oldest newest most voted

I can’t give an official or definitive answer, but here are some thoughts. First some background, which can be skipped if you just want a list of differences.

The mechanisms by which PCs boot from optical discs and magnetic and solid-state disks are quite different. Magnetic and solid-state disks have a boot sector—the first 512 byte sector of the disk—which is loaded and directly executed by BIOS without it needing to understand partitions or file-system formats. Optical discs don’t have a boot sector, so instead a particular file on the disc is flagged as a boot image (via an extension to the ISO9660 file-system standard called “El Torito”).

This is complicated by the fact that media with boot sectors can also be divided into partitions, and the (DOS) partition table uses part of the 512 byte space, leaving… not much space for a boot-loader. Thus there is usually a minimal stage 1 boot-loader in the boot sector, which simply loads a bigger, more complete boot-loader from elsewhere. In Linux, when DOS partitions are used, the gap between the boot sector and the first partition is used for stage 2. With the newer GPT partitions, that gap contains the first GPT, so instead a small “BIOS boot partition” is used (in Linux). Windows uses a the first few sectors of its partition for its stage 2 boot-loader.

Then there is the BIOS successor, UEFI, which can read partitions and the vFAT file-system, and loads boot-loaders from files.

Tools like liveiso-to-disk, liveusb-creator, and UNetBootin, all take an ISO with an El Torito-based boot-loader (isoinux), copy the files to a disk with an existing file-system (either vFAT or Ext2/3/4), and install a boot-sector–based boot-loader (syslinux or extlinux, depending on the file-system).

Now it turns out that the ISO9660 file-system used on optical discs is quite flexible. It is possible to “hide” a boot sector at the start of an ISO and have it ignored when booting from an optical disc. That is called a hybrid image, and the tools for creating them are relatively recent. That is what makes it possible to dd the ISO directly to the USB device and boot it.

So why keep both methods available?

• Using dd will destroy any data already on the USB, whereas the old methods leave existing files intact.

• Using dd gives you no choice about how or whether the USB is partitioned—the partition table is hard-coded into the ISO.

This last point is important, because an awful lot of BIOSes have bugs relating to booting from USB, and even the ones that work well often handle partitioned and unpartitioned USB devices differently. Not all methods produce devices that can boot on all systems.

So, use whichever method is most convenient for you that works on your machines. Be prepared to try other methods if it doesn’t work. Good luck…

more

Oooh, what an answer!!! Incredible, spectacular!!! Thanks, thanks, thanks!!!!

more


text:
#### Example 1

Write each of the following using concise algebraic notation.

1. A number x is multiplied by itself and then doubled.
2. A number x is squared and then multiplied by the square of a second number y.
3. A number x is multiplied by a number y and the result is squared.

#### Solution

1. $$x × x × 2 = x^2 × 2 = 2x^2$$
2. $$x^2 × y^2 = x^2y^2$$
3. $$(x × y)^2 = (xy)^2$$ which is equal to $$x^2y^2$$

#### Summary

 $$2 × x$$ is written as 2$$x$$ $$x^1 = x$$ (the first power of $$x$$ is $$x$$) $$x × y$$ is written as $$xy$$ or $$yx$$ $$x^0 = 1 (x \neq 0)$$ $$x × y × z$$ is written as $$xyz$$ $$1x = x$$ $$x × x$$ is written as $$x^2$$ $$0x = 0$$ $$4 × x × x × x = 4x^3$$ $$x ÷ 3$$ is written as $$\dfrac{x}{3}$$ $$x ÷ (yz)$$ is written as $$\dfrac{x}{yz}$$


text:
Global Convergence Rate of Proximal Incremental Aggregated Gradient Methods

# Global Convergence Rate of Proximal Incremental Aggregated Gradient Methods

N. D. Vanli Laboratory for Information and Decision Systems, Massachusetts Institute of Technology, Cambridge, MA 02139, USA. email: {denizcan, mertg, asuman}@mit.edu.    M. Gürbüzbalaban11footnotemark: 1    A. Ozdaglar11footnotemark: 1
June 29, 2019
###### Abstract

We focus on the problem of minimizing the sum of smooth component functions (where the sum is strongly convex) and a non-smooth convex function, which arises in regularized empirical risk minimization in machine learning and distributed constrained optimization in wireless sensor networks and smart grids. We consider solving this problem using the proximal incremental aggregated gradient (PIAG) method, which at each iteration moves along an aggregated gradient (formed by incrementally updating gradients of component functions according to a deterministic order) and taking a proximal step with respect to the non-smooth function. While the convergence properties of this method with randomized orders (in updating gradients of component functions) have been investigated, this paper, to the best of our knowledge, is the first study that establishes the convergence rate properties of the PIAG method for any deterministic order. In particular, we show that the PIAG algorithm is globally convergent with a linear rate provided that the step size is sufficiently small. We explicitly identify the rate of convergence and the corresponding step size to achieve this convergence rate. Our results improve upon the best known condition number dependence of the convergence rate of the incremental aggregated gradient methods used for minimizing a sum of smooth functions.

## 1 Introduction

We focus on composite additive cost optimization problems, where the objective function is given by the sum of component functions and a possibly non-smooth regularization function :

 minx∈\mathbbmRnF(x)≜f(x)+r(x), \hb@xt@.01(1.1)

and . We assume each component function is convex and continuously differentiable while the regularization function is proper, closed, and convex but not necessarily differentiable. This formulation arises in many problems in machine learning, distributed optimization, and signal processing. Notable examples include constrained and regularized least squares problems that arise in various machine learning applications [7, 21], distributed optimization problems that arise in wireless sensor network as well as smart grid applications [19, 11] and constrained optimization of separable problems [1]. An important feature of this formulation is that the number of component functions is large, hence solving this problem using a standard gradient method that involves evaluating the full gradient of , i.e., , is costly. This motivates using incremental methods that exploit the additive structure of the problem and update the decision vector using one component function at a time.

While these recent advances suggest IAG as a promising approach with fast convergence rate guarantees for solving additive cost problems, in many applications listed above, the objective function takes a composite form and includes a non-smooth regularization function (to avoid overfitting or to induce a sparse representation). Another important case of interest is smooth constrained optimization problems which can be represented in the composite form (LABEL:eq:goal) where the function is the indicator function of a nonempty closed convex set.

Our analysis uses function values to track the evolution of the iterates generated by the PIAG algorithm. This is in contrast with the recent analysis of the IAG algorithm provided in [12], which used distances of the iterates to the optimal solution as a Lyapunov function and relied on the smoothness of the problem to bound the gradient errors with distances. This approach does not extend to the non-smooth composite case, which motivates a new analysis using function values and the properties of the proximal operator. Since we work directly with function values, this approach also allows us to obtain iteration complexity results to achieve an -optimal solution.

In terms of the algorithmic structure, our paper is related to [7], where the authors introduce the SAGA method, which extends the SAG method to the composite case and provides a linear convergence rate result with an analysis that relies on the stochastic nature of the algorithm and does not extend to the deterministic case. Particularly, the SAGA method samples the component functions randomly and independently at each iteration without replacement (in contrast with the PIAG method, where the component functions are processed deterministically). However, such random sampling may not be possible for applications such as decentralized information processing in wireless sensor networks (where agents are subject to communication constraints imposed by the network topology and all agents are not necessarily connected to every other agent via a low-cost link [19]), motivating the study of the deterministic PIAG method. In [7], the authors prove that to achieve a point in the -neighborhood of the optimal solution, SAGA requires iterations.222Let be an optimal solution of the problem (LABEL:eq:goal). A vector is in the -neighborhood of an optimal solution if . However, note that this result does not translate into a guarantee in the function suboptimality of the resulting point because of lack of smoothness. Furthermore, the choice of Lyapunov function in [7] requires each to be convex (to satisfy the non-negativity condition), whereas we do not need this assumption in our analysis.

Our work is also related to [26], where the authors propose a related linearly convergent incrementally updated gradient method for solving the composite additive cost problem in (LABEL:eq:goal) under a local Lipschitzian error condition (a condition satisfied by locally strongly convex functions around an optimal solution). The PIAG algorithm is different from the algorithm proposed in [26]. Specifically, for constrained optimization problems (i.e., when the regularization function is the indicator function of a nonempty closed convex set), the iterates generated by the algorithm in [26] stay in the interior of the set since the algorithm in [26] searches for a feasible update direction. On the other hand, the PIAG algorithm uses the proximal map on the intermediate iterate obtained by moving in the opposite direction of the aggregated gradient, which operates as a projected gradient method and allows the iterates to be on the boundary of the set. Aside from algorithmic differences, [26] does not provide explicit rate estimates (even though the exact rate can be calculated after an elaborate analysis, the dependence on the condition number and the window length of the outdated gradients is significantly worse than the one presented in this paper). Furthermore, the results in [26] provides a -step linear convergence, whereas the linear convergence results in our paper hold uniformly for each step.

Other than the papers mentioned above, our paper is also related to [4], which studies an alternative incremental aggregated proximal method and shows linear convergence when each and are continuously differentiable. This method forms a linear approximation to and processes the component functions with a proximal iteration, whereas our method processes based on a gradient step. Furthermore, our linear convergence results do not require the differentiability of the objective function in contrast to the analysis in [4].

Several recent papers in the machine learning literature (e.g., [7, 14, 8, 17, 16] and references therein) are also weakly related to our paper. In all these papers, the authors propose randomized order algorithms similar to the SAG algorithm [23] and analyze their convergence rates in expectation. In particular, in [8], the authors propose an algorithm, called Finito, which is closely related to the SAG algorithm but achieves a faster convergence rate than the SAG algorithm. These ideas are then extended to composite optimization problems with non-smooth objective functions (as in (LABEL:eq:goal)) in [17, 7]. In particular, in [17], a majorization-minimization algorithm, called MISO, is proposed to solve smooth optimization problems and its global linear convergence is shown in expectation. In [16], the ideas in [17] are then extended for non-smooth optimization problems using proximal operator. Similarly, in [14], a variance reduction technique is applied to the SGD algorithm for smooth problems and its global linear convergence in expectation is proven.

The rest of the paper is organized as follows. In Section LABEL:sec:piag, we introduce the PIAG algorithm. In Section LABEL:sec:main, we first provide the assumptions on the objective functions and then prove the global linear convergence of the proposed algorithm under these assumptions. We conclude the paper in Section LABEL:sec:conclusion with a summary of our results.

## 2 The PIAG Algorithm

Similar to the IAG method, at each iteration , we form an aggregated gradient, which we denote as follows

 gk≜1mm∑i=1∇fi(xτi,k),

where represents the gradient of the th component function sampled at time . We assume that each component function is sampled at least once in the past iterations, i.e., we have

 k−K≤τi,k≤k,∀i∈{1,…,m}.

This condition is typically satisfied in practical implementations of the deterministic incremental methods. For instance, if the functions are processed in a cyclic order, we have [26, 13]. On the other hand, corresponds to the case where we have the full gradient of the function at each iteration (i.e., ) and small may represent a setting in which the gradients of the component functions are sent to a processor with some delay upper bounded by .

Since the regularization function is not necessarily differentiable, we propose to solve (LABEL:eq:goal) with the proximal incremental aggregated gradient (PIAG) method, which uses the proximal operator with respect to the regularization function at the intermediate iterate obtained using the aggregated gradient. In particular, the PIAG algorithm, at each iteration , updates as

 xk+1=proxηr(xk−ηgk), \hb@xt@.01(2.1)

where is a constant step size and the proximal mapping is defined as follows

 proxηr(y)=argminx∈\mathbbmRn{12||x−y||2+ηr(x)}. \hb@xt@.01(2.2)

Here, we define and let denote the set of subgradients of the function at . Then, it follows from the optimality conditions [3] of the problem in (LABEL:eq:prox) that . This yields , for some . Hence, we can compactly represent our update rule as

 xk+1=xk+ηdk, \hb@xt@.01(2.3)

where is the direction of the update at time .

## 3 Convergence Analysis

### 3.1 Assumptions

Throughout the paper, we make the following standard assumptions.

###### Assumption 3.1

(Lipschitz gradients) Each has Lipschitz continuous gradients on with some constant , i.e.,

for any .333If a function has Lipschitz continuous gradients with some constant , then is called -smooth. We use these terms interchangeably.

Defining , we observe that Assumption LABEL:asmp:lips and the triangle inequality yield

 ||∇f(x)−∇f(y)||≤L||x−y||,

for any , i.e., the function is -smooth.

###### Assumption 3.2

(Strong Convexity) The sum function is -strongly convex on for some , i.e., the function is convex, and the regularization function is convex on .

A consequence of Assumption LABEL:asmp:conv is that is strongly convex, hence there exists a unique optimal solution of problem (LABEL:eq:goal) [20, Lemma 6], which we denote by .

We emphasize that these assumptions hold for a variety of cost functions including regularized squared error loss, hinge loss, and logistic loss [6] and similar assumptions are widely used to analyze the convergence properties of incremental gradient methods in the literature [7, 4, 2, 23, 12]. Note that in contrast with many of these analyses, we do not assume that the component functions are convex.

### 3.2 Rate of Convergence

In this section, we show that the PIAG algorithm attains a global linear convergence rate with a constant step size provided that the step size is sufficiently small. We define

 Fk≜F(xk)−F(x∗), \hb@xt@.01(3.1)

which is the suboptimality in the objective value at iteration . In our analysis, we will use as a Lyapunov function to prove global linear convergence. Before providing the main theorems of the paper, we first introduce three lemmas that contain key relations in proving these theorems.

The first lemma investigates how the suboptimality in the objective value evolves over the iterations. In particular, it shows that the change in suboptimality can be bounded as a sum of two terms: The first term is negative and has a linear dependence in the step size , whereas the second term is positive and has a quadratic dependence in . This suggests that if the step size is small enough, the linear term in will be dominant guaranteeing a descent in suboptimality.

###### Lemma 3.3

Suppose that Assumptions 1 and 2 hold. Then, the PIAG algorithm in (LABEL:eq:updaterule) yields the following guarantee

 Fk+1≤Fk−12η||dk||2+η2L2k−1∑j=(k−K)+∣∣∣∣dj∣∣∣∣2,

for any step size .

Proof. We first consider the difference of the errors in consecutive time instances and write

 F(xk+1)−F(xk) =f(xk+1)−f(xk)+r(xk+1)−r(xk) ≤⟨∇f(xk),xk+1−xk⟩+L2||xk+1−xk||2+r(xk+1)−r(xk),

where the inequality follows from the Taylor series expansion of around and since the Hessian of at any point is upper bounded by by Assumption LABEL:asmp:lips. Using the update rule in this inequality, we obtain

 F(xk+1)−F(xk) =η⟨∇f(xk)−gk,dk⟩+η2L2||dk||2+η⟨gk,dk⟩+r(xk+1)−r(xk) ≤η||∇f(xk)−gk||||dk||+η2L2||dk||2−η||dk||2−η⟨hk+1,dk⟩+r(xk+1)−r(xk) =η||∇f(xk)−gk||||dk||+η(ηL2−1)||dk||2+⟨hk+1,xk−xk+1⟩+r(xk+1)−r(xk) ≤η||∇f(xk)−gk||||dk||+η(ηL2−1)||dk||2, \hb@xt@.01(3.2)

where the first inequality follows by the triangle inequality and the last inequality follows from the convexity of .

The gradient error term in (LABEL:eq:c1), i.e., , can be upper bounded as follows

 ||∇f(xk)−gk|| ≤1mm∑i=1∣∣∣∣∇fi(xk)−∇fi(xτi,k)∣∣∣∣ ≤1mm∑i=1Li∣∣∣∣xk−xτi,k∣∣∣∣ ≤1mm∑i=1Lik−1∑j=τi,kη∣∣∣∣dj∣∣∣∣ ≤ηLk−1∑j=(k−K)+∣∣∣∣dj∣∣∣∣, \hb@xt@.01(3.3)

where the first and third inequalities follow by the triangle inequality, the second inequality follows since each is -smooth, and the last inequality follows since . Using (LABEL:eq:lem1) we can upper bound (LABEL:eq:c1) as follows

 F(xk+1)−F(xk) ≤η(ηL2−1)||dk||2+η2Lk−1∑j=(k−K)+∣∣∣∣dj∣∣∣∣||dk|| ≤η(ηL(K+1)2−1)||dk||2+η2L2k−1∑j=(k−K)+∣∣∣∣dj∣∣∣∣2 ≤−η2||dk||2+η2L2k−1∑j=(k−K)+∣∣∣∣dj∣∣∣∣2, \hb@xt@.01(3.4)

where the second inequality follows from the arithmetic-geometric mean inequality, i.e., and the last inequality follows since . This concludes the proof of Lemma LABEL:prop1.

We next introduce the following lemma, which can be viewed as an extension of [25, Theorem 4] into our framework with aggregated gradients. We provide a simplified proof compared to [25] with a tighter upper bound. This lemma can be interpreted as follows. When the regularization function is zero (i.e., for all ) and we have access to full gradients (i.e., ), this lemma simply follows from the strong convexity of the sum function since and due to the optimality condition of the problem. The following lemma indicates that even though we do not have such control over the subgradients of the regularization function (as the regularization function is neither strongly convex nor smooth), the properties of the proximal step yields a similar relation at the expense of a constant of (instead of compared to the case) and certain history dependent terms (that arise due to the incremental nature of the PIAG algorithm) that has a linear dependence in step size . This lemma will be a key step in the proof of Lemma LABEL:prop2, where we illustrate how the descent term in Lemma LABEL:prop1 relates to our Lyapunov function.

###### Lemma 3.4

Suppose that Assumptions 1 and 2 hold and let denote the condition number of the problem. Then, the distance of the iterates from the optimal solution is upper bounded as

 ||xk−x∗||≤2μ||dk||+2ηQk−1∑j=(k−K)+∣∣∣∣dj∣∣∣∣,

for any and .

Proof. Define

as the direction of update with the full gradient. Non-expansiveness property of the proximal map implies

 ∣∣∣∣proxηr(x)−proxηr(y)∣∣∣∣2≤⟨proxηr(x)−proxηr(y),x−y⟩.

Putting and in the above inequality, we obtain

 ∣∣∣∣xk+ηd′k−x∗∣∣∣∣2 ≤⟨xk+ηd′k−x∗,xk−η∇f(xk)−x∗+η∇f(x∗)⟩ ≤⟨xk+ηd′k−x∗,xk+ηd′k−x∗⟩+⟨xk+ηd′k−x∗,−ηd′k+η∇f(x∗)−η∇f(xk)⟩,

which implies

 0≤⟨xk+ηd′k−x∗,−d′k+∇f(x∗)−∇f(xk)⟩.

This inequality can be rewritten as follows

 ⟨xk−x∗,∇f(xk)−∇f(x∗)⟩ ≤⟨xk−x∗,−d′k⟩−η∣∣∣∣d′k∣∣∣∣2+η⟨d′k,∇f(x∗)−∇f(xk)⟩ ≤⟨xk−x∗,−d′k⟩+η⟨d′k,∇f(x∗)−∇f(xk)⟩ ≤∣∣∣∣d′k∣∣∣∣(||xk−x∗||+η||∇f(x∗)−∇f(xk)||) ≤∣∣∣∣d′k∣∣∣∣(||xk−x∗||+ηL||xk−x∗||) ≤2∣∣∣∣d′k∣∣∣∣||xk−x∗||, \hb@xt@.01(3.5)

where the second inequality follows since , the third inequality follows by the Cauchy-Schwarz inequality, the fourth inequality follows from the -smoothness of , and the last inequality follows since . Since -strong convexity of implies

 μ||xk−x∗||2≤⟨xk−x∗,∇f(xk)−∇f(x∗)⟩, \hb@xt@.01(3.6)

then combining (LABEL:eq:app1) and (LABEL:eq:app2), we obtain

 \hb@xt@.01(3.7)

In order to relate to the original direction of update , we use the triangle inequality and write

 ∣∣∣∣d′k∣∣∣∣ ≤||dk||+∣∣∣∣d′k−dk∣∣∣∣ =||dk||+1η∣∣∣∣xk+ηd′k−xk−ηdk∣∣∣∣ =||dk||+1η∣∣∣∣% proxηr(xk−η∇f(xk))−proxηr(xk−ηgk)∣∣∣∣ ≤||dk||+||gk−∇f(xk)||, ≤||dk||+ηLk−1∑j=(k−K)+∣∣∣∣dj∣∣∣∣, \hb@xt@.01(3.8)

where the last line follows by equation (LABEL:eq:lem1). Putting (LABEL:eq:app4) back into (LABEL:eq:app3) concludes the proof of Lemma LABEL:lem.

In the following lemma, we relate the direction of update to the suboptimality in the objective value at a given iteration . In particular, we show that the descent term presented in Lemma LABEL:prop1 (i.e., ) can be upper bounded by the negative of the suboptimality in the objective value of the next iteration (i.e., ) and additional history dependent terms that arise due to the incremental nature of the PIAG algorithm.

###### Lemma 3.5

Suppose that Assumptions 1 and 2 hold. Then, for any , the PIAG algorithm in (LABEL:eq:updaterule) yields the following guarantee

 −||dk||2≤−μ4Fk+1+ηLk−1∑j=(k−K)+∣∣∣∣dj∣∣∣∣2.

Proof. In order to prove this lemma, we use Lemma LABEL:lem, which can be rewritten as follows

 −||dk||≤−μ2||xk−x∗||+ηLk−1∑j=(k−K)+∣∣∣∣dj∣∣∣∣.

Then, we can upper bound as

 −||dk||2 ≤−μ2||dk||||xk−x∗||+ηLk−1∑j=(k−K)+||dk||∣∣∣∣dj∣∣∣∣ ≤−μ2⟨dk,x∗−xk⟩+ηKL2||dk||2+ηL2k−1∑j=(k−K)+∣∣∣∣dj∣∣∣∣2, \hb@xt@.01(3.9)

where the last line follows by the Cauchy-Schwarz inequality and the arithmetic-geometric mean inequality. We can upper bound the inner product term in (LABEL:eq:pop1) as

 −⟨dk,x∗−xk⟩ =⟨gk+hk+1,x∗−xk⟩ =⟨∇f(xk),x∗−xk⟩+⟨hk+1,x∗−xk⟩+⟨gk−∇f(xk),x∗−xk⟩ ≤f(x∗)−f(xk)+⟨hk+1,x∗−xk+1⟩+η⟨hk+1,dk⟩+⟨gk−∇f(xk),x∗−xk⟩ ≤f(x∗)−f(xk)+r(x∗)−r(xk+1)+η⟨hk+1,dk⟩+||gk−∇f(xk)||||x∗−xk||, \hb@xt@.01(3.10)

where the first inequality follows from the convexity of and the second inequality follows from the convexity of and the triangle inequality. The inner product term in (LABEL:eq:pop2) can be upper bounded as

 η⟨hk+1,dk⟩ =−η||dk||2−⟨gk,ηdk⟩ =−η||dk||2+⟨∇f(xk),−ηdk⟩+⟨gk−∇f(xk),−ηdk⟩ ≤−η||dk||2+⟨∇f(xk),xk−xk+1⟩+η||dk||||gk−∇f(xk)|| ≤−η||dk||2+f(xk)−f(xk+1)+η2L2||dk||2+η||dk||||gk−∇f(xk)||, \hb@xt@.01(3.11)

where the first inequality follows by the triangle inequality and the second inequality follows from the -smoothness of . Putting (LABEL:eq:pop3) back in (LABEL:eq:pop2), we obtain

 −⟨dk,x∗−xk⟩≤−Fk+1+η(ηL2−1)||dk||2+||gk−∇f(xk)||(||x∗−xk||+η||dk||). \hb@xt@.01(3.12)

The final term in (LABEL:eq:pop4) can be upper bounded as follows

 ||gk−∇f(xk)||(||x∗−xk||+η||dk||) ≤ηL⎛⎝k−1∑j=(k−K)+∣∣∣∣dj∣∣∣∣⎞⎠(||x∗−xk||+η||dk||) ≤ηL⎛⎝k−1∑j=(k−K)+∣∣∣∣dj∣∣∣∣⎞⎠⎡⎣(η+2μ)||dk||+2ηQk−1∑j=(k−K)+∣∣∣∣dj∣∣∣∣⎤⎦,

where the first line follows by equation (LABEL:eq:lem1) and the last line follows by Lemma LABEL:lem. Using arithmetic-geometric mean inequality in the above inequality, we obtain

 ||gk−∇f(xk)||(||x∗−xk||+η||dk||)≤ηKL2(η+2μ)||dk||+η[ηL2+Q+2ηKQL]k−1∑j=(k−K)+∣∣∣∣dj∣∣∣∣. \hb@xt@.01(3.13)

Putting (LABEL:eq:pop5) back in (LABEL:eq:pop4) yields

 −⟨dk,x∗−xk⟩ ≤−Fk+1+η(ηL2−1+KL2(η+2μ))||dk||2+η[ηL2+Q+2ηKQL]k−1∑j=(k−K)+∣∣∣∣dj∣∣∣∣ =−Fk+1+η(η(K+1)L2−1+KQ)||dk||2+η[ηL2+Q+2ηKQL]k−1∑j=(k−K)+∣∣∣∣dj∣∣∣∣ ≤−Fk+1+η(KQ−12)||dk||2+η(ηL2+Q+2ηKQL)k−1∑j=(k−K)+∣∣∣∣dj∣∣∣∣, \hb@xt@.01(3.14)

where the last line follows since . Finally, using (LABEL:eq:pop6) in our original inequality in (LABEL:eq:pop1), we obtain

 −||dk||2 ≤−μ2Fk+1+η(KL2−μ4+KL2)||dk||2+η(ημL4+L2+ηKL2+L2)k−1∑j=(k−K)+∣∣∣∣dj∣∣∣∣2, ≤−μ2Fk+1+ηKL||dk||2+ηL(μ4+ηKL+1)k−1∑j=(k−K)+∣∣∣∣dj∣∣∣∣2, ≤−μ2Fk+1+ηKL||dk||2+ηL(η(K+1)L+1)k−1∑j=(k−K)+∣∣∣∣dj∣∣∣∣2, ≤−μ2Fk+1+||dk||2+2ηLk−1∑j=(k−K)+∣∣∣∣dj∣∣∣∣2, \hb@xt@.01(3.15)

where the second inequality follows since , the third inequality follows since , and the last inequality follows since . Rearranging the terms in (LABEL:eq:pop7), we obtain

 −||dk||2≤−μ4Fk+1+ηLk−1∑j=(k−K)+∣∣∣∣dj∣∣∣∣2, \hb@xt@.01(3.16)

which completes the proof of Lemma LABEL:prop2.

In the following theorem, we derive a recursive inequality to upper bound the suboptimality at iteration in terms of the suboptimality in the previous iterations (where is a positive integer that measures the length of history considered) and an additive remainder term. We will later show in Corollary LABEL:corr1 that this remainder term can also be upper bounded in terms of the suboptimality observed in previous iterations.

###### Theorem 3.6

Suppose that Assumptions 1 and 2 hold. Then, the PIAG algorithm with step size yields the following recursion

 (1+ημ8)Fk+1≤(1−a−1∑i=1ϵi)Fk+a−1∑i=1ϵiFk−iK+η2KL2ϵa−1k−1∑j=k−aK∣∣∣∣dj∣∣∣∣2, \hb@xt@.01(3.17)

for any , where is an arbitrary constant and .

Proof. We use induction on the constant to prove this theorem. For , the recursion can be obtained as follows. Using Lemma LABEL:prop2 in Lemma LABEL:prop1 and rearranging terms, we get

 (1+ημ8)Fk+1≤Fk+η2Lk−1∑j=k−K∣∣∣∣dj∣∣∣∣2. \hb@xt@.01(3.18)

Rearranging terms in Lemma LABEL:prop1, we obtain

 \hb@xt@.01(3.19)

Putting (LABEL:eq:t2) back in (LABEL:eq:t1), we get

 (1+ημ8)Fk+1 ≤Fk+η2Lk−1∑j=k−K(2η(Fj−Fj+1)+ηLj−1∑i=j−K||di||2) ≤Fk+2ηL(Fk−K−Fk)+η3L2k−1∑j=k−Kj−1∑i=j−K||di||2 ≤Fk+2ηL(Fk−K−Fk)+η3KL2k−1∑j=k−2K||di||2 \hb@xt@.01(3.20)

Since , then (LABEL:eq:t3) can be rewritten as follows

 (1+ημ8)Fk+1≤(1−ϵ1)Fk+ϵ1F(k−K)++η2KL2ϵ1k−1∑j=k−2K∣∣∣∣dj∣∣∣∣2, \hb@xt@.01(3.21)

showing (LABEL:eq:rec) for . As a part of the induction procedure, we then assume that (LABEL:eq:rec) holds for some arbitrary , which amounts to

 (1+ημ8)Fk+1≤(1−a−1∑i=1ϵi)Fk+a−1∑i=1ϵiFk−iK+η2KL2ϵa−1k−1∑j=k−aK∣∣∣∣dj∣∣∣∣2.

Using (LABEL:eq:t2) in the above inequality, we obtain

 (1+ημ8)Fk+1 ≤(1−a−1∑i=1ϵi)Fk+a−1∑i=1ϵiFk−iK+η2KL2ϵa−1 ×k−1∑j=k−aK(2η(Fj−Fj+1)+ηLj−1∑i=j−K||di||2) =(1−a−1∑i=1ϵi)Fk+a−1∑i=1ϵiFk−iK+ϵa(F(k−aK)+−Fk)+η2L2ϵak−1∑j=k−aKj−1∑i=j−K∣∣∣∣dj∣∣∣∣2 ≤(1−a∑i=1ϵi)Fk+a∑i=1ϵiFk−iK+η2KL2ϵak−1∑j=k−(a+1)K∣∣∣∣dj∣∣∣∣2.

Therefore, (LABEL:eq:rec) holds for as well, which concludes the proof of Theorem LABEL:thm1.

###### Corollary 3.7

Suppose that Assumptions 1 and 2 hold. Then, the PIAG algorithm with step size yields the following recursion

 (1+ημ8)Fk+1≤(1−a−1∑


text:
# Tag Info

0

How to solve this, you can generate random portfolios based on constraints see method="random" in optimize.portfolio in PortfolioAnalytics in R See (1) as those would solve the above, however you do not have an objective function so ANY solution that meets your constraints would be accepted, see below for examples of objective functions as they would give ...

1

I have found the slides from Yollin very useful for portfolio optimization using R such as mean-variance, max-sharpe ratio portfolio etc. http://www.rinfinance.com/RinFinance2009/presentations/yollin_slides.pdf Also, there are some packages in R for this such as $PortfolioAnalytics$ I believe : http://www.rinfinance.com/agenda/2014/workshop/RossBennett.pdf ...

2

I'll assume the rest of the world doesn't have access to a similar oracle. Indeed if it did future returns would converge to the risk free rate instantly. In this case, I would prefer holding the AAA bond instead of the stock because the rest of the world would consider it to be much less risky. As a financial institution, reducing the risk of your ...

0

Maybe I'm missing the tricky part of this trick question: If the device is 100% accurate it doesn't matter as both will yield 5% with certainty. This is the same unless you want to take into account coupons or dividends.

1

Here is a guide by morningstar: " A step by step guide to the black litterman model" https://corporate.morningstar.com/ib/documents/MethodologyDocuments/IBBAssociates/BlackLitterman.pdf

1

I would distinguish between Bayesian inference versus Bayesian portfolio management techniques. Inference includes estimating parameters and credible intervals (the Bayesian version of confidence intervals, which are actually far more intuitive) and forecast. If you want to learn about Bayesian inference, get a solid foundation in frequentist methods ...

Top 50 recent answers are included


text:
Lacking Natural Simplicity

Random musings on books, code, and tabletop games.

Emacs and Cygwin python

If you happen to be using Windows Emacs and Cygwin Python there's an annoying interaction where “M-x run-python” hangs. The easiest way to fix it is to mount the directory where you have your emacs installation into the Cygwin file name structure. For instance, I have my emacs installation in C:\emacs\emacs-22.2, and in a cygwin shell I did mount -b ‘C:\emacs' /emacs, and now running the Cygwin python works.

The emacs function run-python adds the emacs data-directory to the PYTHONPATH in the emacs process-environment before running python; unfortunately, since this is the MS Windows emacs, its data-directory starts with a drive letter and a colon. When the Cygwin python initializes sys.path it splits PYTHONPATH at the colons, which means sys.path ends up with the drive letter as one component (usually interpreted as a relative path) and everything after the colon as another component. It that's a valid Cygwin pathname for the Emacs data directory (which is what the above mount command did), things work (accidentally).

Comments

Comments powered by Disqus


text:
# Having issue with font spacing on Motile M142 (Ryzen)

Hello everyone,

I installed Manjaro a few weeks ago on my laptop, and noticed that I had some strange font spacing (kerning?) issues. Here is an example (the m and the o):

Apparently I can’t include links (probably since I just joined) so the image link is
ibb dot co /1qYpg1m

I installed the minimal build of i3, so I am wondering if I am missing some package that would resolve this issue. I did specify a default font in my fontconfig, so that also might be related.


text:
# Question: How to find the roots of Bessel's function between -4 and 4 using the newton raphson method in maple?

March 20 2013 by
false

1

Hi, I am having a little trouble finding the roots of Bessel's function J0 between -4 and 4 using the newton Raphson method, the main issue I am having is not knowing what to input at a certain point.

f:=x->x-evalf(cos(x));                     f := x -> x - evalf(cos(x))> low:=-10;                              low := -10> up:=10;                               up := 10> step:=1;                              step := 1> > dp:=5;                               dp := 5> > for i from low to up-step by step do> >           a:=i:>           b:=i+step: >               >      if f(a)*f(b) < 0 then           > >          print(root in interval,a,b):>                 >      fi:> > od:                         root in interval, 0, 1
As you can see above I was able to get maple to find me the root interval,

How would I do the same for Bessel's function? What would I put into f:=


text:
# My problems 16

Calculus Level 4

$\large \int_0^1 x^6 \sqrt{1-x^2} \, dx$

If the integral above can be expressed as $$\frac {a\pi}b$$ for coprime positive integers $$a$$ and $$b$$, what is the value of $$a+b$$?

×


text:
# Exponential random variable X with a uniform random variable as its parameter

$$X\ \sim Exp(U) ~ and\ U\ \sim U(0,1)$$

The question asked for the value of $$P(X\geqslant 1)$$

I saw the solution and it went like this:

$$P(X\geqslant 1) = E[P(X\geqslant 1)|U] = E[e^{-u}] = \int_{0}^{1}e^{-x}dx$$

Could someone explain the solution to me?

More specifically how did the solution derive each step?

You are given that the conditional distribution of $$X$$ given $$U=u$$ is $$\text{Exp}(u)$$ (presumably $$u$$ is the rate parameter), where $$U$$ itself is uniformly distributed on $$(0,1)$$.
Suppose $$I(X\ge 1)$$ is an indicator variable that equals $$1$$ if $$X\ge 1$$ and equals $$0$$ otherwise. And let the density of $$U$$ be $$f_U$$. Then,
\begin{align} P(X\ge 1)&=E\left[I(X\ge 1)\right] \\&=E\left[E\left[I(X\ge 1\mid U\right]\right] \\&=E\left[P(X\ge 1\mid U)\right] \\&=E\left[e^{-U}\right] \\&=\int e^{-x}f_U(x)\,dx \\&=\int_0^1 e^{-x}\,dx \end{align}
• You can directly say $P(X\ge 1)=\int P(X\ge 1\mid U=x)f_U(x)\,dx$ by law of total probability. Apr 24 at 5:45


text:
# Derivative with respect to matrix

Hello,
1- How to determine a derivative of a function with respect to matrix?
2- For example let a function f such that
f(C)= x'Cy + x'C'y + x'C'ACy
where x and y are vectors and C and A are matrix and (') is the opertor transpose.
what is the derivative of f with respect to C?

Thank you.

### Re: Derivative with respect to matrix

Hello,
If I understand there isn't a derivative with respect to matrix like my example.

There is.


text:
# Metrics and time information

#### Contains

• The metric values for the training and test sets.

The table below lists the names of parameters that define the metric values to output. The values of all functions defined by these parameters are output.

Command-line version parameters Python parameters R parameters
--custom-metric custom_metric custom_loss
--loss-function --loss-function --loss-function
--eval-metric --eval-metric --eval-metric
• Information about the number of seconds of training:

• passed since the beginning
• remaining until the end

#### Format

The resulting JSON file consists of the following arrays:

#### meta

Contains basic information about the training.

Format of the array with prettified sample data:

"meta": {
"launch_mode": "Train",
"name": "second",
"iteration_count": 1000,
"learn_metrics": [
{
"name": "Precision:class=0",
"value": "Max"
},
{
"name": "Precision:class=1",
"value": "Max"
}
],
"test_sets": [
"test",
...
"testN"
],
"test_metrics": [
{
"name":"Precision:class=0",
"value":"Max"
},
{
"name":"Precision:class=1",
"value":"Max"
}
],
"learn_sets": [
"learn"
]
}

Property Type Description
launch_mode string The specified launch mode.

Possible values:
- Train — Training launch mode.
- CV — Cross-validation launch mode (for the Python cv method only).

The command-line implementation of the Cross-validation feature returns the Train value in this parameter.

name string The experiment name.

The value can be set in the --name (--name) training parameter. The default name is .
iteration_count int The maximum number of trees that can be built when solving machine learning problems.
The final number of iterations may be less than the output in this property.
learn_metrics array A list of metrics calculated for the learning dataset and information regarding the optimization method.
test_sets array The names of the arrays within the iterations array that contain the calculated values of metrics for the validation datasets.
test_metrics array A list of metrics calculated for the validation dataset and information regarding the optimization method.
name string The name of the metric.
value string The method for defining the best value of the metric. Possible values:
- Min — The smaller the value of the metric, the better.
- Max — The bigger the value of the metric, the better.
- Undefined — The best value of the metric is not defined.
- Float value — The best value of the metric is user-defined.
learn_sets array The name of the array within the iterations array that contains the calculated values of the metrics for the learning dataset.

#### iterations

Contains an array of metric values for the training and test sets and information on the duration of training for each iteration.

Format of the array with prettified sample data:

"iterations": [
{
"learn": [
0.8333333333,
0.6666666667,
0.7325581395,
-1.0836257,
0.4347826087,
0.1428571429,
0.984375,
-0.6881395691
],
"iteration": 0,
"passed_time": 0.0227411829,
"remaining_time": 22.71844172,
"test1": [
0.8333333333,
0.6666666667,
0.7325581395,
-1.0836257,
0.4347826087,
0.1428571429,
0.984375,
-0.6881395691
],
...
"testN": [
0.7333453333,
0.3666664267,
0.0325581395,
-1.9046257,
0.8937826089,
0.4138571478,
0.004313,
-0.3881390984
]
}
]

Property Type Description
learn array A list of metric values calculated for the learning dataset. The order of metrics is given in the learn_metrics array of the meta array.
iteration int The index of the iteration. Numbering starts from zero.
passed_time float The number of seconds passed since the beginning of training.
remaining_time float The number of seconds remaining until the end of training given that all the scheduled iterations take place.
test array The values of metrics calculated for the corresponding validation dataset.

The order of the metrics is given in the test_metrics array of the meta array.

#### Example

{
"meta": {
"launch_mode": "Train",
"name": "second",
"iteration_count": 1000,
"learn_metrics": [
{
"name": "Precision:class=0",
"value": "Max"
},
{
"name": "Precision:class=1",
"value": "Max"
},
{
"name": "Precision:class=2",
"value": "Max"
},
{
"name": "MultiClass",
"value": "Max"
},
{
"name": "Recall:class=0",
"value": "Max"
},
{
"name": "Recall:class=1",
"value": "Max"
},
{
"name": "Recall:class=2",
"value": "Max"
},
{
"name": "MultiClassOneVsAll",
"value": "Max"
}
],
"test_sets": [
"test"
],
"test_metrics": [
{
"name": "Precision:class=0",
"value": "Max"
},
{
"name": "Precision:class=1",
"value": "Max"
},
{
"name": "Precision:class=2",
"value": "Max"
},
{
"name": "MultiClass",
"value": "Max"
},
{
"name": "Recall:class=0",
"value": "Max"
},
{
"name": "Recall:class=1",
"value": "Max"
},
{
"name": "Recall:class=2",
"value": "Max"
},
{
"name": "MultiClassOneVsAll",
"value": "Max"
}
],
"learn_sets": [
"learn"
]
},
"iterations": [
{
"learn": [
0.8333333333,
0.6666666667,
0.7325581395,
-1.0836257,
0.4347826087,
0.1428571429,
0.984375,
-0.6881395691
],
"iteration": 0,
"passed_time": 0.0227411829,
"remaining_time": 22.71844172,
"test": [
0.8333333333,
0.6666666667,
0.7325581395,
-1.0836257,
0.4347826087,
0.1428571429,
0.984375,
-0.6881395691
]
},
{
"learn": [
0.7142857143,
1,
0.7820512821,
-1.068965402,
0.652173913,
0.1428571429,
0.953125,
-0.6832264
],
"iteration": 1,
"passed_time": 0.04471753966,
"remaining_time": 22.31405229,
"test": [
0.7142857143,
1,
0.7820512821,
-1.068965402,
0.652173913,
0.1428571429,
0.953125,
-0.6832264
]
},
...
]
}


text:
# 19.5 Summary

The Hebb rule ( 19.2.1 ) is an example of a local unsupervised learning rule. It is a local rule, because it only depends on pre- and postsynaptic firing rates and the present state $w_{ij}$ of the synapse, i.e., information that is easily ‘available’ at the location of the synapse. Experiments have shown that, not only the firing rates, but also the membrane voltage of the postsynaptic neuron, as well as the relative timing of pre- and postsynaptic spikes determine the amplitude and direction of change of the synaptic efficacy. In order to account for spike timing effects, classical pair-based models of STDP are formulated with a learning window that consists of two parts: If the presynaptic spike arrives before a postsynaptic output spike, the synaptic change is positive. If the timing is reversed, the synaptic change is negative. However, classical pair-based STDP models neglect the frequency and voltage dependence of synaptic plasticity which are included in modern variants of STDP models.

The synaptic weight dynamics of Hebbian learning can be studied analytically if weights are changing slowly as compared to the time scale of the neuronal activity. Weight changes are driven by correlations between pre- and postsynaptic activity. More specifically, simple Hebbian learning rules in combination with a linear neuron model find the first principal component of a normalized input data set. Generalized Hebb rules, such as Oja’s rule, keep the norm of the weight vector approximately constant during plasticity.

The interesting aspect of STDP is that it naturally accounts for temporal correlations by means of a learning window. Explicit expressions for temporal spike-spike correlations can be obtained for certain simple types of neuron model such as the linear Poisson model. Spike-based and rate-based rules of plasticity are equivalent as long as temporal spike-spike correlations are disregarded. If firing rates vary slowly, then the integral over the learning window plays the role of the Hebbian correlation term.

Hebbian learning or STDP are examples of unsupervised learning rules. Hebbian learning is considered to be a major principle of neuronal organization during development and a driving force for receptive field formation. However, Hebbian synaptic plasticity is not useful for behavioral learning, since it does not take into account the success (or failure) of an action. Three-factor learning rules combine the two Hebbian factors (i.e. pre- and postsynaptic activity) with a third factor (i.e., a neuromodulator such as dopamine) which conveys information about an action’s success. Three factor rules with an eligibility trace can be used to describe behavioral learning, in particular during conditioning experiments.

# Literature

Correlation-based learning can be traced back to Aristoteles 99 Aristoteles, ”De memoria et reminiscentia”: There is no need to consider how we remember what is distant, but only what is neighboring, for clearly the method is the same. For the changes follow each other by habit, one after another. And thus, whenever someone wishes to recollect he will do the following: He will seek to get a starting point for a change after which will be the change in question. and has been discussed extensively by James ( 242 ) who formulated a learning principle on the level of ‘brain processes’ rather than neurons:

When two elementary brain-processes have been active together or in immediate succession, one of them, on re-occurring, tends to propagate its excitement into the other.

A chapter of James’ book is reprinted in volume 1 of Anderson and Rosenfeld’s collection on Neurocomputing ( 25 ) . The formulation of synaptic plasticity in Hebb’s book ( 210 ) of which two interesting sections are reprinted in the collection of Anderson and Rosenfeld ( 25 ) has had a long-lasting impact on the neuroscience community. The historical context of Hebb’s postulate is discussed in the reviews of Sejnowski ( 466 ) and Makram et al. ( 326 ) .

Classical experimental studies on STDP are ( 328; 567; 117; 55; 56; 483 ) , but precursors of timing dependent plasticity can be found even earlier ( 295 ) . Note that for some synapses, the learning window is reversed ( 43 ) . For reviews on STDP, see Abbott and Nelson ( 3 ) ; Bi and Poo ( 54 ) ; Caporale and Dan ( 89 ) ; Sjöström and Gerstner ( 482 ) .

The theory of unsupervised learning and principal component analysis is reviewed in the textbook by Hertz et al. ( 215 ) . Models of the development of receptive fields and cortical maps have a long tradition in the field of computational neuroscience; see, e.g., von der Malsburg ( 540 ) ; Willshaw and von der Malsburg ( 550 ) ; Sejnowski ( 467 ) ; Bienenstock et al. ( 58 ) ; Kohonen ( 271 ) ; Linsker ( 300 ) ; Miller et al. ( 346 ) ; MacKay and Miller ( 318 ) ; Miller ( 344 ) ; for reviews see, e.g., Erwin et al. ( 144 ) ; Wiskott and Sejnowski ( 556 ) . The essential aspects of the weight dynamics in linear networks are discussed in Oja ( 369 ) ; Miller and MacKay ( 343 ) . Articles of Grossberg ( 200 ) and Bienenstock et al. ( 58 ) or the book of Kohonen ( 271 ) illustrate the early use of the rate-based learning rules in computational neuroscience.

The early theory of STDP has been developed by ( 178; 176; 256; 442; 530; 489; 448 ) but precursors of timing-dependent plasticity can be found in earlier rate-based formulations ( 216; 488 ) . Modern theories of STDP go beyond the pair-based rules ( 468; 394 ) , consider voltage effects ( 99 ) , variations of boundary conditions ( 202 ) or Calcium-based models ( 302; 303 ) ; for reviews see Morrison et al. ( 353 ) ; Sjöström and Gerstner ( 482 ) .

Experimental support for three-factor learning rules is reviewed in ( 429; 391 ) . Model studies to reward modulated STDP are ( 238; 294; 153; 157 ) . The consequences for behavior are discussed in ( 306; 307 ) . The classic reference for dopamine in relation to reward-based learning is Schultz et al. ( 460 ) . Modern reviews on the topic are ( 461; 462 ) .

# Exercises

1. 1.

Normalization of firing rate.

Consider a learning rule ${{\text{d}}\over{\text{d}}t}w_{ij}=\gamma\,(\nu_{i}-\nu_{\theta})\,\nu_{j}\,,$ i.e., a change of synaptic weights can only occur if the presynaptic neuron is active ( $\nu_{j}>0$ ). The direction of the change is determined by the activity of the postsynaptic neuron. The postsynaptic firing rate is given by $\nu_{i}=g(\sum_{j=1}^{N}w_{ij}\nu_{j})$ . We assume that presynaptic firing rates $\nu_{j}$ are constant.

(i) Show that $\nu_{i}$ has a fixed point at $\nu_{i}=\nu_{\theta}$ .

(ii) Discuss the stability of the fixed point. Consider the cases $\gamma>0$ and $\gamma<0$ .

(iii) Discuss whether the learning rule is Hebbian, anti-Hebbian, or non-Hebbian.

2. 2.

Fixed point of BCM rule . Assume a single postsynaptic neuron $\nu_{i}$ which receives constant input $\nu_{j}>0$ at all synapses $1\leq j\leq N$ .

(i) Show that the weights $w_{ij}$ have a fixed point under the BCM rule ( 19.9 ).

(ii) Show that this fixed point is unstable.

3. 3.

Receptive field development with BCM rule . 20 presynaptic neurons with firing rates $\nu_{j}$ connect onto the same postsynaptic neuron which fires at a rate $\nu_{i}^{\rm post}=\sum_{j=1}^{20}w_{ij}\,\nu_{j}$ . Synaptic weights change according to the BCM rule ( 19.9 ) with a hard lower bound $0\leq w_{ij}$ and $\nu_{\theta}=10$ Hz.

The 20 inputs are organized in two groups of 10 inputs each. There are two possible input patterns $\mbox{\boldmath$$\xi$$}^{\mu}$ , with $\mu=1,2$ .

(i) The two possible input patterns are: $\mu=1$ - group 1 fires at 3Hz and group 2 is quiescent; and $\mu=2$ - group 2 fires at 1Hz and group 1 is quiescent. Inputs alternate between both patterns several times back and forth. Each pattern presentation lasts for $\Delta t$ . How do weights $w_{ij}$ evolve? Show that the postsynaptic neuron becomes specialized to one group of inputs.

(ii) Similar to (i), except that that the second pattern now is $\mu=2$ : group 2 fires at 2.5Hz and group 1 is quiescent. How do weights $w_{ij}$ evolve?

(iii) As in (ii), but you are allowed to make $\nu_{\theta}$ a function of the time-averaged firing rate $\bar{\nu}_{i}^{\rm post}$ of the postsynaptic neuron. Is $\nu_{\theta}=\bar{\nu}_{i}^{\rm post}$ a good choice? Why is $\nu_{\theta}=(\bar{\nu}_{i}^{\rm post})^{2}/10Hz$ a better choice?

Hint: Consider the time it takes to update your time-averaged firing rate in comparison to the presentation time $\Delta t$ of the patterns.

4. 4.

Weight matrix of Hopfield model. Consider synaptic weights that change according to the following Hebbian learning rule: ${{\text{d}}\over{\text{d}}t}w_{ij}=c(\nu_{i}-\nu_{0})\,(\nu_{j}-\nu_{0}).$ (i) Identify the parameters $c$ and $\nu_{0}$ with the parameters of Eq. ( 19.2.1 ).

(ii) Assume a fully connected network of $N$ neurons. Suppose that the initial weights $w_{ij}$ vanish. During presentation of a pattern $\mu$ , activities of all neurons $1\leq k\leq N$ , are fixed to values $\nu_{k}=p_{k}^{\mu}$ , where $p_{k}^{\mu}\in\{0,1\}$ and synapses change according to the Hebbian learning rule. Patterns are applied one after the other, each for a time $\Delta t$ . Choose an appropriate value for $\nu_{0}$ so that after application of $P$ patterns, the final weights are $w_{ij}=\gamma\sum_{j=1}^{P}p_{i}^{\mu}\,p_{j}^{\mu}$ . Express the parameter $\gamma$ by $c,\nu_{0},\Delta t$ .

(iii) Compare your results with the weight matrix of the Hopfield model in Chapter 17 . Is the above learning procedure realistic? Can it be classified as unsupervised learning?

Hint: Consider not only the learning phase, but also the recall phase. Consider the situation where input patterns are chosen stochastically.

5. 5.

PCA with Oja’s learning rule . In order to show that Oja’s learning rule ( 19.7 ) selects the first principal component proceed in three steps.

(i) Show that the eigenvectors $\{\mbox{\boldmath$$e$$}_{1},\dots,\mbox{\boldmath$$e$$}_{N}\}$ of $C$ are fixed points of the dynamics.

Hint: Apply the methods of Section 19.3 to the batch version of Oja’s rule and show that

 $\Delta\mbox{\boldmath$$w$$}=\gamma\,C\,\mbox{\boldmath$$w$$}-\gamma\,\mbox{% \boldmath$$w$$}\,[\mbox{\boldmath$$w$$}\cdot C\,\mbox{\boldmath$$w$$}]\,,$ (19.49)

The claim then follows.

(ii) Show that only the eigenvector $\mbox{\boldmath$$e$$}_{1}$ with the largest eigenvalue is stable.

Hint: Assume that the weight vector $\mbox{\boldmath$$w$$}=\mbox{\boldmath$$e$$}_{1}+\epsilon\mbox{\boldmath$$e$$}_% {k}$ has a small perturbation $\epsilon\ll 1$ in one of the principal direction. Derive an equation for ${\text{d}}\epsilon/{\text{d}}t$ and show that the perturbation grows if $k\neq 1$ .

(iii) Show that the output rate represents the projection of the input onto the first principal component.

6. 6.

Triplet STDP rule and BCM . Show that for Poisson spike arrival and output spike generated by an independent Poisson process of rate $\nu_{i}$ , the triplet STDP model gives rise to a rate-based plasticity model identical to BCM. Identify the function $\phi$ in Eqs. ( 19.8 ) and ( 19.9 ) with the parameters of the triplet model in ( 19.15 ).

Hint: Use the methods of Section 19.3.3 . Independent Poisson output means that you can neglect the pre-before-post spike correlations.