Machine Learning

X

predictors, independent variables, features, variables

Y

response, dependent variable

\begin{eqnarray} Y = f(X) + \epsilon \end{eqnarray}

\(\epsilon\)

random error term, 1) independent of X and 2) has mean zero

statistical learning

a set of approaches for estimating \(f\).

reducible error

\(\hat{f}\) is not an accurate perfect estimate of \(f\)

irreducible error

the error term \(\epsilon\) This may due to unmeasured variables

overfitting

follow error too closely

degree of freedom

a quantity that summarizes the flexibility of a curve

indicator variable

\(I(y_i = \hat{y}_i)\) is 0 or 1

parametric method

reduce the fitting problem to estimating a set of coefficients. But it will be imprecise if the model choose-d is very different from the true model

non-parametric method

a very large number of observations is required.

regression

a quantitative response

classification

a qualitative response

prediction

\(\hat{f}\) is treated as black box

inference

understand the relationship between X and Y. \(\hat{f}\) cannot be treated as black box.

Bayes Classifier

assign each observation to the most likely class, given its predictor values.

Bayes Error Rate

Bayes classifier produces the lowest possible test error rate. The Bayes error rate is analogous to the irreducible error. This means it is the optimal value. So Bayes classifier serves as an unattainable gold standard against which to compare other methods.

Bayes Decision Boundary

determine the prediction

K-Nearest Neighbors

K points in the training set that are closest to \(x_0\), represented by \(N_0\). Use the largest probability.

mean square error (MSE)

\begin{eqnarray} MSE = \frac{1}{n} \sum_{i=1}^{n} (y_i - \hat{f}(x_i))^2 \end{eqnarray}

training MSE

test MSE

Residual Sum of Squares (RSS)

\begin{eqnarray} RSS = e_1^2 + e_2^2 + \ldots + e_n^2 \\ e_i = y_i - \hat{y}_i \end{eqnarray}

So RSS can also be written as:

\begin{eqnarray} RSS = \sum_{i=1}^n (y_i - \hat{y}_i)^2 \end{eqnarray}

Least square approach chooses \(\beta_0\) and \(\beta_1\) to minimize RSS. The result:

\begin{eqnarray} \hat{\beta_1} & = & \frac{\sum_{i=1}^n (x_i - \bar{x}) (y_i - \bar{y})}{\sum_{i=1}^n (x_i - \bar{x})^2} \\ \hat{\beta_0} & = & \bar{y} - \hat{\beta_1} \bar{x} \end{eqnarray}

1. find the K nearest observations, \(N_0\)
2. estimate \(f(x_0)\) using the average of all the training responses in \(N_0\)

\begin{eqnarray} \hat{f}(x_0) = \frac{1}{K} \sum_{x_i \in N_0} y_i \end{eqnarray}

Linear regression will have negative values. So we use logistic regression, the response is between 0 and 1.

logistic function

\begin{eqnarray} p(X) = \frac{e^{\beta_0 + \beta_1 X}}{1 + e^{\beta_0 + \beta_1 X}} \\ \frac{p(X)}{1 - p(X)} = e^{\beta_0 + \beta_1 X} \\ log(\frac{p(X)}{1 - p(X)}) = \beta_0 + \beta_1 X \end{eqnarray}

The left hand side of last formula is called log-odds or logit. So logistic regression model has a logit that is linear in X.

Assume the observations within each class are drawn from a multivariate Gaussian distribution. Then plug estimates into Bayes' theorem, in order to perform prediction. Many prior and posterior.

It is an alternative to logistic regression. It is more stable, and popular for more than two response classes. it is closely related to logistic regression.

It has similar assumptions as LDA except:

• LDA assumes K classes share a common covariance matrix.
• But QDA assume that each class has its own covariance matrix.

Hold out a subset of training observations from the fitting process, for test.

Can be used to estimate the standard errors of the coefficients from a linear regression fit. It can be easily applied to a wide range of statistical learning methods.

We want to know the standard errors of our estimated coefficients. We sample from the original dataset, with replacement, 1000 samples. For each one, calculate the value. Then use the mean. With replacement means some observations can occur more than once. We can sample 6 items into a sample even if the total number of observations is only 3.

linear combination of the predictors into M new predictors.

\begin{eqnarray} Z_m = \sum_{j=1}^p \phi_{jm} X_j \end{eqnarray}

It is just replace standard linear model to higher dimension ones (typically less than 4). The one with \(X,X^2,X^3\) is called cubic regression.

Also called piecewise constant regression. It actually piecewise the data, and do linear regression. The linear model is

\begin{eqnarray} y_i = \beta_0 + \beta_1 C_1(x_i) + \beta_2 C_2(x_i) + ... + \beta_K C_K(x_i) + \epsilon_i \end{eqnarray}

Given a value X, there's at most one of \(C_i\) can be non-zero.

a set of basis function \(b_i(X)\):

\begin{eqnarray} y_i = \beta_0 + \beta_1 b_1(x_i) + \beta_2 b_2(x_i) + ... + \beta_K b_K(x_i) + \epsilon_i \end{eqnarray}

It is piecewise polynomial. But it ensures the smooth at the knots.

We have K knots, and fit a cubic regression. At the knots, we need to ensure the 0,1,2 deviation is the same.

This is a different approach, but also produces a spline. Instead of making RSS minimal, we make the following minimal

\begin{eqnarray} RSS = \sum_{i=1}^n (y_i - g(x_i))^2 \end{eqnarray}

We need to find a \(g\). If we do not put any constraints, we can simply let \(g\) equal to \(y_i\). But this is overfitting. We need some constraints on \(g\). We want to find the \(g\) that minimizes:

\begin{eqnarray} \sum_{i=1}^n (y_i - g(x_i))^2 + \lambda \int g''(t)^2dt \end{eqnarray}

The function \(g\) that minimizes it is a smoothing spline.

The first term is a loss function, nd second is a penalty term.

1. gather the fraction \(s = k/n\) of training points whose \(x_i\) are closest to \(x_0\).
2. assign a weight \(K_{i0} = K(x_i, x_0)\) to each point, so that the point furthest from x₀ has weight 0, and closest has highest weight. All but these k nearest neighbors get 0.
3. fit a weighted least squares regression, by finding \(\beta_0\) and \(\beta_1\) that minimize

\begin{eqnarray} \sum_{i=1}^n K_{i0} (y_i - \beta_0 - \beta_1 x_i)^2 \end{eqnarray}

local regression can perform poorly if p is much larger than 3 or 4, because there will be very few training observations close to x₀.

It is called additive model because we calculate a separate \(f_j\) for each \(X_j\), and add together all of their contributions.

The decision tree suffers from high variance. If we split the training data into two parts at random, the result two trees can be very different.

Bagging can reduce the variance. It is related to bootstrap.

Bagging involves

1. creating multiple copies of the original training data set using the bootstrap,
2. fitting a separate decision tree to each copy,
3. and then combining all of the trees in order to create a single predictive model.

Each tree is built on a bootstrap data set, independent of the other trees.

The key idea is averaging a set of observations reduces variance.

This is another approach for improving the prediction results from a decision tree. The different from bagging is,

• the trees are grown sequentially: each tree is grown using information from previously grown trees.
• Boosting does not involve bootstrap sampling. Each tree is fit on a modified version of the original data set.

Also known as optimal separating hyperplane.

In fact exist an infinite number of such hyperplanes. This is the motivation.

The separating hyperplane that is farthest from the training observations. That is, we can compute the (perpendicular) distance from each training observation to a given separating hyperplane; the smallest such distance is the minimal distance from the observations to the hyperplane, and is known as the margin

The maximal margin hyperplane is the separating hyperplane for which the margin is largest—that is, it is the hyperplane that has the farthest minimum dis- tance to the training observations.

The closest observations are support vectors. they “support” the maximal margin hyperplane in the sense that if these points were moved slightly then the maximal margin hyperplane would move as well.

guarantees that each observation will be on the correct side of the hyper- plane, provided that M is positive.

The above method is

not stable

An additional blue observation has been added, leading to a dramatic shift in the maximal margin hyperplane.

not allow mistake

Also known as soft margin classifier.

allow some observations to be on the incorrect side of the margin, or even the incorrect side of the hyperplane.

The model formula is TODO.

The parameters in the model:

1. the slack variable εi tells us where the ith observation is located, relative to the hyperplane and relative to the margin
2. C: determines the number and severity of the vio- lations to the margin (and to the hyperplane) that we will tolerate C is treated as a tuning parameter that is generally chosen via cross-validation

Some observations:

1. only observations that either lie on the margin or that violate the margin will affect the hyperplane
2. an observation that lies strictly on the correct side of the margin does not affect the support vector classifier
3. Observations that lie directly on the margin, or on the wrong side of the margin for their class, are known as support vectors.
4. When the tuning parameter C is large, then the margin is wide

enlarging the feature space in a specific way, using kernels. Can deal with non-linear, just use a non-linear kernel.

linear kernel:

\begin{eqnarray} K(x_i, x_{i'}) = \sum_{j=1}^p x_{ij} x_{i'j} \end{eqnarray}

polynomial kernel:

\begin{eqnarray} K(x_i, x_{i'}) = (1 + sum_{j=1}^p x_{ij} x_{i'j})^d \end{eqnarray}

Radial kernel:

\begin{eqnarray} K(x_i, x_{i'}) = exp(-\gamma \sum_{j=1}^p (x_{ij} - x{i'j})^2) \end{eqnarray}

W(C_k)

the amount by which the observations within a cluster differ from each other

It says the total within-cluster variation, summed over all K clusters, is as small as possible. It defines the within-cluster variation. The formula for it is: the sum of all of the pairwise squared Euclidean distances between the observations in the kth cluster.

\begin{eqnarray} W(C_k) = \frac{1}{|C_k|} \sum_{i,i' \in C_k} \sum_{j=1}^p (x_{ij} - x_{i'j})^2 \end{eqnarray}

where \(|C_k|\) denotes the number of observations in the kth cluster.

The algorithm:

1. select a number K, randomly assign a clustering from 1 to K for each observation
2. iterate until cluster assignments stop changing 2.1 for each cluster, compute centroid: the vector of the p features means for the observations in the kth cluster. 2.2 assign each observation to the cluster whose centroid is closest.

This algorithm guarantee to decrease the objective formula above.

Does not predefine the number of clusters. The result is called a dendrogram, a tree-based representation of the observations.

It is constructed bottom-up. The tree node means a fusion. The height of the fusion indicates how different the two observations are. Never compare the horizontal distance.

Construction algorithm: examine all pairwise inter-cluster dissimilarities among all clusters. Fuse the most similar ones.

The four most commonly used types of linkage:

• complete: maximal intercluster dissimilarity
• single: minimal intercluster dissimilarity
• average: mean intercluster dissimilarity
• centroid: dissimilarity between the centroid of cluster A and B