# Elements of Statistical Learning

I am reading the book Elements of Statistical Learning by Hastie, Tibshirani and Friedman. What I wanted to get out of this book is both the practical aspect and the theoretical aspect of functional approximation. This is somewhat tied to my effort to gain more understanding in other branches of mathematics and applications, such as representation theory, harmonic analysis, and time series analysis. There are already plenty of people writing up notes on this book. I will incorporate my own notes and solution while cross-checking theirs. This post will be my workspace for reading this book. This post uses the same notation as the book. The input variable is denoted by . If is a vector, its component is denoted by . Quantitative outputs is denoted by , and qualitative outputs by . These uppercase letters are used to refer to the generic aspect of a variable. Observed values are written in lowercase, so the observation of is . Matrices are represented by bold uppercase, so a set of input of -vectors , would be represented by matrix . The component from the matrix is denoted by . Therefore and are distinguished by their dimension.

#### Overview of Supervised Learning

Two of the classical methods for supervised learning are introduced: The least-square method and the nearest-neighbor method. Both methods can be derived from the framework of statistical decision theory. We will develop the theory first then go into each of these two methods.

Given some random input vectors and is a real-valued random output variable, and a joint probability distribution , we want to find a function from a general function space that relates to . The simplest example is to set to be a dimensional Euclidean space and to be . It can also accommodate classification problem by setting to be .

If the function space is unrestricted, then one can find functions whose output matches the training outputs exactly but will probably perform horribly out-of-sample. Therefore we can put some restriction on the space . For example, we can be working exclusively in the space of linear functions or the space of quadratic functions.

Functions from the space of linear functions are not expected to fit the output data exactly even when the underlying relationship is linear. This is because there are still errors associated with the data. Supposing that there is no errors, but the underlying relationship is a quadratic relationship while we restrict our function space to the space of all linear functions, then any function from this space will not fit the observed output exactly. The way to choose a function that “best” relate the input and output requires a notion of how well a function fit the data. This is measured through loss function . A common choice of is . Given these we can have a criteria for choosing such that it minimizes the expected prediction error (EPE), . For example, let , the expected prediction error is

and by conditioning on , we have

and to find the that minimizes the EPE, we have, given any ,

Therefore the function can be found by minimizing the EPE pointwise, and the solution at is

the conditional expectation. We may not want to use this particular loss function. Let us replace the loss function with . The solution of using this loss function is

The function is sometimes called the decision rule, and I think this is where the term “statistical decision theory” comes from. Another commonly heard term is the Statistical Learning Theory, which is in a sense a superset of the statistical decision theory. Roughly speaking, the statistical decision theory deals with the cases where we assume some amount of knowledge about the distribution . The statistical learning theory, on the other hand, deals with the cases where our knowledge of the joint probability distribution is limited. In the latter case, the decision rule itself is based only on the data, rather than the assumed, predetermined probability distribution.

We are now ready to get back to the least-square method and the nearest-neighbor method.

##### Linear Models and Least Squares Methods

In a linear model, one predicts the output from a vector of inputs via

The most popular method of fitting the linear model is to use the method of least squares, which choose to minimize the residual sum of squares

which has solution

We can see that this method can be derived from the statistical decision framework by setting the function space to be the space of all linear functions and with the loss function to be . Here we assume that , but this need not be the case. The choice of in this case can also be the set that numerically codes some qualitative variable with two classes.

To Be Continued…

# Multiple Time Series Analysis

I am reading the book New Introduction to Multiple Time Series Analysis by Lütkepohl to refresh my memory of vector autoregressive models, error correction models, and state space models (supposedly all equivalent.) I will build in some computational aspect of these models into this post using python or julia. This post serves as my workbook while reading the book.

To Be Continued…

# Representation Theory of Finite Group

I am reading the book Representation Theory of Finite Groups by Benjamin Steinberg due to my interest in probability theory on groups and other algebraic structure. This is related to my earlier post on random walk on n-gons which I found to be very interesting. This post will be my workspace for reading through this book and other related material, notably Group Representations in Probability and Statistics by Persi Diaconis.

Representation theory studies how a group act on vector spaces. Another way to think about it is that for any group , what are the ways to embed or map it to the general linear group . We need to first review what a group action is. The action of a group on a set is a homomorphism , assigning each group member some permutation of the set that is compatible with the structure of the group . This is always possible because one can do this trivially (the trivial action) such that for all , mapping every element of to the identity permutation. If we take , then it is also always possible because of Cayley’s Theorem, which states that every group is isomorphic to a group of permutation or a subgroup of the symmetric group . The set can have some additional structure, and if we take to be a vector space over field and ensure the map respect the additional structure of the vector space as well, then the group action is called a group representation.

##### Definition (Representation)

A representation of group is the homomorphism from to the general linear group of the vector space . The degree of is the dimension of .

We write the linear map as , and , sometimes written as for the action of on . Below is an example of the representation on .

##### Example (Representation of )

Immediately from the definition we see the analogy of trivial action as a representation: the trivial representation given by for all . We also see that the degree of the trivial representation is 1. It is interesting to see some other representations of a small group such as the group of all permutations on 3 elements. Aside from the trivial representation, we can compute two others: the alternating representation and the standard representation or the permutation representation.

Let be a permutation on 3 elements, the alternating representation is the function where if can be written as a product of an even number of transpositions, and otherwise. More precisely, define the signum of by

then the map is a group homomorphism of to the subgroup of the multiplicative group . Thus the number of transpositions in a representation of is either even or odd. We can check that this is a representation. For we have

so . This representation has degree 1.

The standard representation takes each permutation to a matrix in on standard basis such that rows of the matrix is permuted according to . In other words, . For example

The standard representation has degree 3.

If we start with a representation where is a basis for , and if we have another isomorphism with a basis , then is another representation. These two representation are intuitively the “same”. More generally, we have the definition of equivalence

##### Definition (Equivalence)

Two representations and are said to be equivalent if there exists an isomorphism such that for all , or , or in picture, the following diagram commutes:

If is equivalent to , we write .

An example of equivalent representations is given in Sternberg as follows:

##### Example (Equivalence)

Define and by

To show that , we need to find an an invertible matrix such that . This matrix also represents a simple basis transformation in . Let us find the eigenvectors of the two operators. The eigenvectors for are and , and for is and the standard basis, while the eigenvalues for are and and for are and . By Euler’s formula, the two sets of eigenvalues are the same, so we can deduce that the change of basis matrix is the matrix with columns of eigenvectors of , namely,

Indeed, after some calculation.

The notion of equivalent representation are the same as matrix similarity, except that the former describes the equivalence between operators and the latter their matrix representation. Also note that in the example above there are two eigenspaces for , namely and . For , we have for all as well. This motivates the definition of -invariant subspace.

##### Definition (-Invariant Subspace)

Let be a representation. A subspace is -invariant if, for all and , one has .

We can use this definition to find the -invariant subspace of the standard representation . Note that the 1-dimensional space spanned by is a -invariant subspace, since for any ,

(1)

is again in the . Also note that its compliment is also -invariant. Indeed, if is a representation and is a -invariant subspace, then restricting to yields a subrepresentation The following computation of restricting the standard representation to follows that of Disconis.

##### Computation of the 2-Dimensional Representation of

Let and . Let then since the components of add to . then yields . Therefore and are basis for . Let’s consider the action on this basis.

This gives the 2-dimensional representation of

The 2-dimensional representation of is also irreducible, which means

##### Definition: Irreducible Representation

A non-zero representation of a group is said to be irreducible if the only -invariant subspaces of are and .

To show that, assume a non-zero vector (say ) and let be the span of this vector. If is a sub representation, then . Since , and so their difference is also in . If , then . Since , must be in as well, so . If then . . Take the difference and we have . Then must also be in , so again . This irreducible representation is 2-dimensional. We will see that the restriction of the permutation representation of to is an irreducible -dimensional representation.

Since we can form direct sum of vector spaces, we can similarly define a direct sum of representations. We want to do this because we want to show that if and are two -invariant subspaces and is a representation, then it makes sense to talk about a representation that maps from to .

##### Definition: Direct Sum of Representations

Let and be two representations, then their external direct sum

is defined by

and has dimension .

If we restrict ourselves to matrices, then suppose and . Then

has the block matrix form

The representation in the example about equivalence is a good demonstration of how to form direct product of representations. It should also be clear that if a representation can be written as a direct sum of subrepresentations, then it is not irreducible. Therefore. the representations in our equivalence example are not irreducible.

Related to the notion of irreducible representation are the decomposable and completely reducible representations.

To Be Continued…

# From Line to Circle

Sometimes a problem involving a finite sequence can be changed slightly to yield other interesting results. One of my favourite tweak is to make the sequence into a circle so that the last element is adjacent to the first element of the sequence, and try to solve the same problem on this circular sequence. Sometimes the problem is already in this circular form. Take the following problem from the 1988 Austrian Mathematics Olympiad, for example:

Determine the number of all sequences , with for , that satisfy and for .

One of the solutions is from the book From Erdös to Kiev by Ross Honsberger. The other solution is from Crux Mathematicorum due Curtis Cooper.

#### Solution 1

First let us get our hands dirty. Let denote the number of sequence of length satisfying the conditions in the question. The table below gives a the first few terms

 n Sequence 1 a 1 2 0 3 aba, aca 2 4 abca, acba 2 5 ababa, abaca, acaba, acaba, abcba, acbca 6

Now we need a general rule to generate this table. Looking at , note that we can generate row 5 from sequences in row 4 and row 3 in the following way. For each sequence in row 3, we can append a ‘ca’ and a ‘ba’ at the end. The total number of sequence constructed this way is . Also, for each sequence in row 4, we can insert one and only one letter before the final ‘a’ that is different from the second last letter. This can only be done in one way for each sequence in row 4, so the total number of ways is . Combining these two gives us the recursive relation:

(1)

which has the characteristic equation

that has roots at and . Therefore the general solution to Equation 1 is

Given that , , we have and . The general solution for is

#### Solution 2

This solution is based on the observation that the number of sequence satisfying the condition but ends with or instead of can be used to construct the sequence of length that satisfy the condition of the problem. Let be the set of sequences of length that satisfy the and the condition, and let = . Similarly, let and be the sets of sequences of length that satisfy the condition but instead has and condition, respectively. Let and let and as well. Then observe that for each sequence in and , we can append an at the end to create a sequence of length that satisfy and , which is in . Moreover, none of the sequence in sequence can be used to create sequences in . Therefore . Similarly, and . We now have the following system of equations

and we write this as

(2)

The solution for the homogeneous difference equation is the “guess”

where is the number of distinct eigenvalues of the matrix , is the corresponding eigenvector, and . This is a solution because if we plug this solution into Equation 2 we get

since .

The matrix has eigenvalues and of multiplicity . The eigenvectors are:

The generic solution to is then . Solving with boundary condition and gives the same solution above.

# Make a Dollar, Pave a Road

A popular combinatorics problem is the Making a Dollar problem:

Making a Dollar Given unlimited numbers of 1, 5, 10, 25, and 50-cent denomination coin, how many ways are there to make a dollar.

The number of ways to mix the coins into a dollar can be counted in two mutually exclusive ways: 1) the number of ways where the biggest denomination is in the coin mix, and 2) the number of ways the biggest denomination is not in the coin mix. If (1) is true, then there is at least one coin of the biggest denomination in the mix. Let us then use one coin of the biggest denomination and count the number of ways to make the remaining amount using using coins of all denominations. If (2) is true, then let us calculate the number of ways to make a dollar using all other denominations. Let be the number of ways to make -cents using coins with denominations in , then

This recursive relation needs several boundary conditions: when the amount to make is equal to zero, when the amount is less than zero, and when the set of denominations is empty. The first boundary condition implies that we have just found a way to make the exact change because the remaining amount is zero. The second boundary condition says that we have not been able to found an exact change because the denomination of the coin we just used is too large. The last boundary condition says that we have used up all possible denominations and still cannot make the change. These statements translate respectively to , for all negative n, and .

I am picking up a new programming language called Julia so I decided to code this up as an exercise. The procedure described above can be put as follows

function const_comb(sum::Int, parts::Array{Int})
if sum == 0
return 1
end
if sum < 0 || length(parts) < 1
return 0
end
return const_comb(sum - parts[end], parts) + const_comb(sum, parts[1:end-1])
end

This problem can be generalised in several ways. Suppose it matters what order the coins are returned to make the dollar, for example, we want to treat as different from , then how many ways can we make a dollar? It may seem necessary to keep track of the sequence to get the changes and then to count each sequence separately. However, this is not too hard to do and we can recycle the algorithm above. Instead of return 1 when we have the the exact change, we return the number of permutations of the coins to get the change, such as the number of permutations of to make 6 cents. Such permutation with repeating elements are called a permutation of a multi-set. A multi-set is a collection of objects that need not be distinct, i.e. a multi-set where are non-negative integers and are distinct objects, contains of . From combinatorics theory, the number of ways to form a permutation on a multi-set such that is . Sounds like a plan.

Let us first code up the above expression to calculate the number of multi-set permutation. Since it involves a few factorials, special care should be taken to avoid integer overflow. (If you ever wonder why the function lfact–the natural log of the factorial function–needs to exist in Julia’s built-in math library, you will like this post where it shows why a function calculating the hypotenuse of a right triangle need to exist in the cmath library.)

function nPr(n::Int, r::AbstractArray{Int,1})
if(any(i->i>n, r))
return 0
end
if(n==0 || all(i->i==0,r))
return 1
else
return exp(lfact(n) - sum(lfact(r)));
end
end

Now we simply need to keep track of the multi-set of coins of each denomination that make the exact change, and count the number of multi-set permutation. The fact that each object is distinct makes the use of a dictionary in our code a natural choice. The multi-set can be modelled as a dictionary with keys being the distinct object and value being the number of object

function const_comb_rep(sum::Int, parts::AbstractArray{Int, 1}, multiset::Dict)
if sum == 0
return nPr(sum(collect(values(multiset))), collect(values(multiset)))
end
if sum < 0 || length(parts) < 1
return 0
end
sub_multiset = copy(multiset)
sub_multiset[parts[end]] = sub_multiset[parts[end]] + 1
else
sub_multiset[parts[end]] = 1
end
return const_comb_rep(sum - parts[end], parts, sub_multiset) + const_comb_rep(sum, parts[1:end-1], multiset)
end

running with some test inputs get

const_comb_rep(7, [1, 2, 3], Dict())
44.0
[const_comb_rep(n,1:n, Dict{Int,Int}()) for n = 1:10]
10-element Array{Union{Float64,Int64},1}:
1.0
2.0
4.0
8.0
16.0
32.0
64.0
128.0
256.0
512.0

As we recurse, the dictionary keeps tract of the number and denomination of the coins used. Finally when we have an exact change, the number of ways to arrange them is computed and returned back.

Note that the number of ways to make Integer using numbers from is .

Of course, in real life one does not care the order of which changes are returned to make up the right amount. The problem is perhaps more suitable to describe the Pave a Road problem:

Paving a Road Find the number of ways to pave a block of road using , , and blocks, assuming each block is indistinguishable.

The above algorithm gives 44 ways, and one can actually print out each way if one add a print command inside the if sum == 0 statement.

# Random Walk Down n-gon

I found this problem to be quite interesting.

Random Walk on a Square Consider a particle walk randomly around the edges of a square. From any vertex, the probability of it moving to any of the two adjacent vertices is 0.5. Suppose the walk stops as soon as it has traversed all the vertices and returned to the starting vertex. What is the expected path length?

The solution I saw involves breaking the problem down into several possibilities, and find the expected path length and the probability of each possibility, then sum them up. This method seem to work with the case when the number of nodes are small, but perhaps it is more interesting to find a generalised solution to a regular n-gon.

Indeed someone has already thought of that, and wrote a paper about it. What I particularly like about this paper is that it transform the problem into a gambler’s ruin problem, which was my first thought when I read the problem. Let’s recap and solve the Gambler’s Ruin Problem first.

## Gambler’s Ruin Problem

To recap, the Gambler’s Ruin Problem is extracted from the paper and stated below.

Gambler’s Ruin Problem A gambler plays a series of independent bets wagering one dollar on each bet. She either wins one dollar (and gets back her wager) with probability , or loses her wager with probability . Initially she has i dollars. She must quit broke when her fortune reaches 0 (no credit is allowed). Also, she has adopted a policy to quit a winner when her fortune reaches dollars. Here, is a predetermined integer where remains fixed throughout.

• What is the probability that the gambler quits a winner with N dollars rather than goes broke?
• What is the expected number of bets she plays until the game ends?

One can see the connection between these two problems. The random walk down n-gon problem is like the gambler’s ruin problem wrap around a circle. Let us solve the simpler problem first, analytically and programmatically.

### Probability of Quitting a Winner

Let be the probability of winning this game with initial wealth and quitting wealth of , then the following recursive relationship holds

Using the fact that , the relationship can also be written as

(1)

with boundary conditions and . Consider the value : with only 1 dollar of wealth, the probability of ruin is , while the probability of making one more dollar is . Using the formula above, we have or by the boundary condition . Now we consider the value , which can also be written as or . There are two equivalent way of proceeding from here to find :

• we can start with the Equation 1 for , and substitute them back to solve . This is the approach in Ross’s Introduction to Probability Models. Doing so yields the system of equations

(2)

To get an expression for , we can sum the first equations up to get

and to solve for , use the fact that then

We can substitute the expression for to to get

Now if we let , and denote the probability of winning this game as we obtain

(3)

• Alternatively, let’s first solve a simpler problem. Let us first assume that our gambler is playing against the house with infinite wealth, and the games goes on as long as our gambler has not lost all her money, or in other words, assume . This is almost like working backward from the first approach. Let be the probability of our gambler lose the game with an initial wealth . To solve , we note that , because she will lose 1 dollar with probability , and reach state 2, which has probability of ruin. In general,

(4)

which is just the other way of writing Equation 1. To calculate , we note that starting with wealth of 2, it has to first lose 1 dollar (not necessarily in 1 step) to end up at wealth 1 and from there has to lose another dollar (also not necessarily in 1 step) to reach ruin. Therefore . Substituting this into the expression for :

which yields

and we can then find the solution for
This checked out with Equation 3 when . To find the general solution, note that we already have and . We can prove that by induction using Equation 4, and the result implies .

We have only just solved the simpler problem for the case when . The probability of our gambler winning at is the same as the probability of not losing with initial capital of divided by the probability of not losing with initial capital of . This is because the probability of reaching dollars with initial wealth of dollars times the probability of not losing at dollars.

• ### Expected Number of Bets

We can find the expected number of steps similarly using the above recursive relation. Let denote the random variable of the number of steps until the game finishes, either

(5)

where we add 1 on the RHS to indicate that wether she wins or loses this round, she has used up one bet. Coupling this with the boundary condition and , we can solve the system of equations similarly.

To Be Continued…

# The 100 Hats Problem

I am starting to keep a list of things I learned throughout the day. Nothing horrifies me more than realizing at the end of a day that nothing has been learned, not even the trivial things. Keeping track of them will probably alleviate this kind of anxiety. Today I learned that there are generalizations to the 100 hats puzzle.

I read about the 100 hat puzzle from the NYT a while back. Today in a conversation I learned that the problem have been generalized perhaps several times, and that there are quite a few variants of the problem. The problem goes like this, copied from the NYT article:

One hundred persons will be lined up single file, facing north. Each person will be assigned either a red hat or a blue hat. No one can see the color of his or her own hat. However, each person is able to see the color of the hat worn by every person in front of him or her. That is, for example, the last person in line can see the color of the hat on 99 persons in front of him or her; and the first person, who is at the front of the line, cannot see the color of any hat.

Beginning with the last person in line, and then moving to the 99th person, the 98th, etc., each will be asked to name the color of his or her own hat. If the color is correctly named, the person lives; if incorrectly named, the person is shot dead on the spot. Everyone in line is able to hear every response as well as hear the gunshot; also, everyone in line is able to remember all that needs to be remembered and is able to compute all that needs to be computed.

Before being lined up, the 100 persons are allowed to discuss strategy, with an eye toward developing a plan that will allow as many of them as possible to name the correct color of his or her own hat (and thus survive). They know all of the preceding information in this problem. Once lined up, each person is allowed only to say “Red” or “Blue” when his or her turn arrives, beginning with the last person in line.

Your assignment: Develop a plan that allows as many people as possible to live. (Do not waste time attempting to evade the stated bounds of the problem — there’s no trick to the answer.)

There are countless number of papers (too many), presentations, master thesis, and blogs (such as this) that talk about the solutions to this set of problems. I also learned a nice application of the axiom of choice to this problem.