Notes on Foundation of Machine Learning

@(Machine Learning)[Notes, Machine Learning]

Notes on Foundation of Machine Learning

Chapter 1 Introduction

Three different criteria for learning algorithm:
1. Time complexity
2. memory complexity
3. sample complexity: how many samples are need to learning concepts in hypothesis set.

Some other concepts like training set, validation set and test set. One important thing i learned from chapter is what so called Learning Scenario. Different learning scenarios differed from each other by the type of training and testing data (with label, without label), how the training data and testing data is arrived, how to use the training and testing data. We have following scenarios:
1. Supervised Learning
2. Unsupervised Learning
3. Active Learning
4. Dimension Reduction
5. Transductive Learning
6. Online Learning

Then we also have learning tasks, task means the target we want to get:
1. Classification
2. Regression
3. Ranking
4. Sequence labeling

and so on.

Chapter 2 PAC Learning Framework

Machine learning is using a learning algorithm $A$ to find one hypothesis $h$ among hypothesis class $H$ according to specific loss function $l$. Two potential criterion for one hypothesis $h$:
1. loss on available training sample called Empirical Risk $\hat{R(h)} = \frac{1}{m} \sum_{i=1} ^ {m} l[h(x_i), y_i]$;
2. average on all the possible samples called Risk $R(h) = E_{x}{l(x, y_{x})}$

The most important question would be the correlation between empirical risk and risk. This kind of relation is called Generalization Bound. Because in machine learning, low risk is the ultimate goal not low empirical risk. Low risk means good generalization ability. If the generalization bound is clear, we can estimate the real performance of hypothesis returned by learning algorithm $A$. Under certain circumstance, we can put the same question in another way: How many samples we need so that the returned hypothesis has a risk less the prescribed $\epsilon \gt 0$.
Basic background for derivation. Each training sample $x$ comes from sample space $X$, all these samples distributed according to distribution $D$. There is a concept family $C$, each of the concept will map a sample into target value space $Y$, i.e. $y = c(x)$. Learning algorithm $A$ use hypothesis space $H$ to approximate the concept class $C$. Each of the hypothesis $h \in H$ will map sample $x$ into $Y$. Here we assume the possible hypothesis of $H$ is finite, i.e. size is $|H|$.
Now PAC-Learnable defined as follow:
A concept class $C$ is PAC-Learnable, if exists algorithm $A$ and a polynomial function $poly(.,.,.,.)$, for all the $\epsilon \gt 0$ and $\delta \gt 0$, for all the distribution $D$ on $X$ and any target concept $c$ in $C$, if sample size $m \gt poly(1/\epsilon, 1/\delta, O(n), size(c))$ then the following statements hold:
$Pr[R(h_{S}) \le \epsilon] \ge 1 - \delta$.

In order to derive the bound for consistent and inconsistent case, we need union bound and hoedding inequality.
Some generalization to above statement:
1. Assume the label $y$ according to input instance $x$ is deterministic, which means we can get the label from the input data. However, in real application the relation of input and output is stochastic. Which means we have the following distribution $P(Y = y | X = x)$ for each training instance $x$. So we have so assume a distribution $D$ over input and output space, i.e. $X \times Y \in D$. One possible explanation for this is: we do not have enough features to distinguish each training instances. So like use height and weight to classify a person is man or woman. For a set of height and weight, there is a possibility for man and woman.
2. When the output is a distribution conditioned on input sample $x$, We have the bayesian error. This is the minimum error the best classifier can get.
3. We can decompose the risk difference between hypothesis returned by learning algorithm $h_{S}$ and bayesian risk $h_{Bayesian}$ into a combination of estimation error and approximation error.
4. According to generalization bound, the risk of hypothesis $h$ depend on empirical error and ratio of sample size and number of hypothesis. We can find a hypothesis among different hypothesis size for model selection. Or we can use regularization to perform model selection.

Lecture 3 Rademacher Complexity and VC dimension

Rademacher Complexity and VC dimension are two different means to describe the complexity of hypothesis spaces. Because when the number of hypothesis is infinite, the generalization boudn derived in chapter 2 is useless. Rademacher complexity and VC dimension is another way to evaluate the complexity of hypothesis set except the number of hypothesis.
With these two different notation of hypothesis complexity, combined with concentration of inequality to give a uniform generalization bound.

Chapter 4 SVM

Start with linear separable case and then extend to non-separable case. The derivation of primal and dual problem is the way i expected. The most important is the derivation of generalization bound for SVM based on margin rather than feature dimension $N$. One more interesting thing is using hinge loss is actually optimization the generalization bound of SVM.

Chapter 5 Kernel Method

For Kernel method, just know the implicit mapping from input space to high dimension space. The other work is about Positive Definite Symmetric kernel, the rest like RKHS, it’s unnecessary to know all these stuffs.

Chapter 6 Boosting

Boosting comes with one question: can we build a strong classifier with weak classifier ? what’s the definition of weak classifier? How can we combine this weak classifier? What’s its generalization bound and what’s the factor that impact the generalization ability.
Boosting is a strategy, AdaBoost is one real algorithm that can be used when the base weak classifier is a hypothesis set mapping from input space $X$ to $[-1, 1]$. One basic idea is assign weight to each training sample, for samples harder to classify by nature, we give them more weight and then combine the classifier from each iteration linearly to get final classifier.
AdaBoost is optimize a exponential loss function and can be interpreted as coordinate descent algorithm.
Maximum margin can’t explain the performance of adaboost.
One disadvantage of AdaBoost: prone to noisy data. This is not good, because noisy data is everywhere and hard to control.
Another question is the selection of base classifier. Usually we can use decision tree as base learner and trained a tree model based on the current samples.

Chapter 7 Online Learning

Online learning handle the data point one by one, when the learning algorithm receive one data point, then make prediction and have a loss related to the prediction.
Online learning different from the techniques in the previous chapter: No fixed distribution $D$ is assumed on input $x$. This means we can’t use risk to evaluate the hypothesis. So online learning using another set of notation for hypothesis evaluation: mistake model and regret analysis.
Online learning model with expert advice: When doing online learning, $N$ experts will give advice for each input sample $x_t$.
Mistake model is simple, i.e. the number of mistake learning algorithm made during $T$ round of learning. Regret defined as follow: the difference of cumulative loss minus the loss of expert give the minimal loss.
$$R_T = \sum_{i=1}^{T}{L(\hat{y}_i, y_i)} - min_{i =1 } ^ { N } { \sum_{t=1} ^ { T } { L_{i, t} } }$$
All the analysis of online learning algorithm will give results on the total number of mistakes or regret of T rounds learning.
In the setting of $N$ experts, have Weighted Majority (WM), Randomized Weight Majority(RWM) and Exponential Weighted Majority(EWM) algorithms.
When analyzing the mistake bound and regret, it’s usually by deriving the upper and lower bound of weight, then get the results.
For linear classification, perceptron and winnow algorithm are two standards approaches.
Since online learning do not have distribution over data $D$, batch algorithm assume a distribution $D$. What’s the result training a online learning algorithm on data with generated from fixed distribution $D$? The risk can be bounded by the average loss and some factor of $O(N/T)$ where $N$ is the size of dimension, $T$ is the number of learning rounds.

Chapter 8 Multi-Class Classification

Compared with binary classification, multi-class classification differed in three aspects:
1. Large number of class require more computational resources.
2. There are unbalanced classes in multi-class, some class have much larger samples than the other one, need the change of loss function.
3. There are some internal structures inside the output classes, should be used in the design of loss function.

This chapter starts with the generalization bound for multi-class classification. I fond the standard steps for building generalization bound:
1. find the rademacher complexity of the hypothesis set.
2. Derive the relation of rademacher complexity and margin, then get a bound rely on the margin.

There two different approaches have appeared multiple times in this book.
For multi-class classification:
1. Multi-class SVM by define margin as the different between correct label and second largest label score.
2. boosting: Same as AdaBoost. It’s used for multi-label problem.
3. Decision tree: One important knowledge about decision tree is decision tree will split the input space into multiple regions. Each region will have its label.

Other methods called: Aggregated Method
1. one V.S. rest
2. one V.S. one
3. Error Correction codes, quite interesting method, using hamming distance to classify the label of instance.

Multi-class classification and sequence labeling
For sequence labeling, following objective function provided:
1. Maximum Margin objective
2. Struct-SVM objective

Chapter 9 Ranking

Ranking is a new task compared with classification and regression, although this problem can be solved using same techniques when solving classification and regression.
For ranking task, there are two different approaches:
1. score-based approach: This method will train a hypothesis mapping from $X$ to $R$. When predicting, each instance will get a score from hypothesis $h$ then ranking according to this score.
2. preference-based approach: I do not understand this method! This method split ranking into two stages. First stage will train a preference function from training sample, second stage will perform ranking based on the score of preference function.

Score-based approach for ranking
This is pair-wise ranking method, training data is pair of data points and objective function is average mis-ranked pair. For score-based approach, each instance will get a score from hypothesis $h: {X -> R}$. Can use SVM and RankBoost method to training the hypothesis. The analysis of generalization bound is based on rademacher complexity or margin, very much like SVM and AdaBoost.
One interesting scenario is bipartie ranking. In this scenario, all the instance can be classified into two classes. The only requirement is the pos has a higher than neg. This special scenario can be solve using boost method.

Preference-based ranking
i don’t know what’s the meaning of this method.

Chapter 10 Regression

Regression with target value of real. This chapter derive the generalization of linear regression based on rademacher complexity. Other concept similar to VC-dimension is Psudo-Dimension which based on the concept of shattering. The real algorithm for regression has linear regression (with linear hypothesis), ridge regression, kernel ridge regression, support vector regression, lasso and group lasso algorithm. Some analysis are based on rademacher complexity not on margin.

Chapter 11 Algorithmic Stability

Only care one definition of stability: when two samples $S$ and $S'$ only different by one data sample, but the hypothesis output difference can be bounded by some constant number $\beta$. This is called $\beta$ stability.

Chapter 12 Dimension Reduction

PCA is the most formal one of dimensional reduction method, aimed at preserve the maximum variance of original data. Kernel PCA is a version based on a PDS kernel, has many connections with other non-linear dimension reduction method.
Other methods like Isomap (keep the pariwise distance), LLE (keep neighbour distance) and Lapancian Eigenmap (keep the neighbor distance).

Chapter 13 Learning Automata and Languages

Skipped, don’t think it’s relevant to my work.

Chapter 14 Reinforcement Learning

Reinforcement learning based on on abstraction: MDP (markov decision process). Which includes state, action, reward, transition probability (depend on the sate and action), reward probability.
There are two different assumptions:
1. The transition probability and reward probability is known to learner.
2. The transition probability and reward probability is unknown to learner.

A policy is a mapping from state to action: $\pi : s -> a$

In the first case, we only need to plan action based on the known statistics. In the second case, learner need to estimate the parameters from the interaction between environment. For unknown environment, have model-free approach which estimate the policy directly. Also have model-based approach which estimate the transition probability and reward probability at first, then estimate the policy. Q-learning is the most famous algorithm estimate the policy directly.
All these methods based on the stochastic approximate method.

Written with StackEdit.

Notes on Dragon Star

龙星计划笔记

龙星计划的机器学习视频，2012年的。主讲者包括余凯和张瞳。这个笔记是为了记录看视频中觉得有趣的内容，以免自己忘记了。

1. 线性模型
   形式如下：$y = w ^ T x$

2. Boosting & Bagging
   这里主要的内容就是如何从弱分类器构造强分类器，Boosting就是这样的方法。AdaBoost通过对样本给予不同的权重来实现这个效果，GBDT是通过不同的target来做拟合。

2. Linear Model

线性模型使用下面的方法来解决： $y = w ^ T x$.对于这个问题来说，有如下的问题需要解决：

• 如果估计模型参数 $w$
• 估计出来的模型参数 $w$有多好，还能不能继续改进。
• 在p个参数之中，哪些变量更重要些。

9. Learning Theory

Learning Theory的核心内容在于generalization analysis，也就是如何从training error估计test error。如果training error和test error的差距太大，那么就会产生over-fitting，如果有一个办法可以很好的估计training error和test error的误差，那么可以有效的避免误差。
1. Generalization analysis主要处理一下的问题：
1. 在训练集上获得的最好模型与最好的模型由多大的差距
2. 如何由训练集上的误差来估计这个模型在测试集上的错误。
Generalization analysis的主要的工具就是Uniform Convergence这个方法。推到Uniform Convergence的主要方法就是几个概率不等式。

10. Optimization in Machine Learning

• Gradient Descent
• Proximal Gradient
• Coordinate Descent
• Dual Coordinate Descent
• LBFGS (second order method)

11. Online Learning

Regret analysis instead of Generalization analysis
Approaches to Online Learning
- Perceptron Learning algorithm

original online learning algorithm.

Online convex optimization
keypoint: transform the batch method to online optimization method.
- Online gradient descent
- Online proximal gradient descent (L1-regularized solved by proximal gradient contains subtle problem which do not leads to sparse solution. Dual averaging should solve the problem.)
- online second order algorithm also works.
(Online optimization faster convergence than batch method)

Stochastic Gradient Descent is the workhorse of online learning, works much better than other algorithm.

12. Sparsity Models

Used when face high dimention data, only when some of the variable are useful.
convex relaxation of sparsity models.
1. Use L1-norm instead of L-0 norm
2. use greedy (forward stage-wise algorithm to select variable) algorithm to select the problem.
L1-norm regularization is just a convex-relaxation of L0-norm normalization.
Other kind of sparsity

• Structure sparisity of some problem, like group sparsity.

13. Graphical Model

Key point to this kind of model
Definition of graphical model
1. variable
2. Conditional independence.

• Inference
• Learning

14. Structure Learning

Structure exists in input, model and output.
input structure like:
Naive Bayes
model structure
model sparsity, model group sparisity and other structures.

output structure
most important is the sequence labeling task.
HMM
MEMM
CRF
M3N

other development.

Learning algorithms
- perceptron learning
- max-margin learning
- so on.

15. Deep Learning & Feature Learning

Deep learning is architecture for machine learning. We use deep learning approach to learn more representative feature for further task.

• CNN like with deep layer network.
• autoencoders for feature learning with unsupervised data. (love this)

16. Transfer Learning & Semi-Supervised Learning

differetn task share same input space.(Transfer learning, also called multi-task learning)
typical example:
Hierarchiel linear model
nerual netowrk

common approach: Learn a common feature representation, then use this feature to perform different task.
Bayesian approach to transfer learning.

17. Recommendation

CF is the workhorse for recommendation.
CF treated as matrix completion problem get the best performance.
SVD like matrix decomposition (low-rank matrix factorization) gives the best idea.

19. Application of Machine Learning on WEB

1. Query classification
   Key point of web-based classification is to use multiple sources of information to peform ranking. For example, we want to classify a short query, we may use the label of the related web pages.
2. Ranking

GBDT with different cost function.

Dragon Start 2010 course

Generative approach to machine learning leads to Bayesian Error, which stands for the best possible performance.

amazing facts about kNN classifier:
1. close to optimal (Bayesian Error)
2. Density estimation used.

Lecture 2. Generative & Discriminative

Generative vs. Discriminative
Naive Bayes vs. Logistic Regression
Naive Bayes need the data fits gaussian distribution.
Logistic regression do no assume the distribution. Naive Bayes convergence faster than logistic regression.

Lecture 3. Neural Network

BP like algorithm.
DBN, (Boltaman machine), CNN algorithm for image classification.

Lecture 4. Support Vector Machine

max-margin classifiers, talk about primal problem, dual problem and SMO algorithm.

Lecture 5. Learning Theory

Goal of Learning Theory
- Estimate the testing error from training error.
- Relation of current training error and the best training error under same class of model.
- Sample complexity, how many samples needed to train a model so as to achieve desired accuracy.
- how many iterations and resources need to run the algorithm.
Notes on the bound of Learning Theory
1. All the bounds from learning theory are too loose, thus may not give the exact number. but the trends is okay.
2. Some assumptions are made in the derivation of error bounds, be careful. Some of the bounds are not satisfied.

Inequality
- Union equality
- Hoeffding inequality

• PAC
• finite number of hypothesis
• infinite number of hypothesis, VC dimension. (some set of points that can be shuttered by the hypothesis.)

Lecture 6. Over-fitting & Model selection

Big problem when dealing with learning problem, the phenomenon is you get a relative good score in training set yet bad on test set. (Watch out: You can’t judge you model is over-fitted by its performance on test set. If you change your model when its performance is poor on test set, you will overfit to test set.)

One intuitive explanation of over-fitting is you model fit a sampling or some kind of random error too much. Every model will over-fit to

Bias-Variance trade off

We can decompose the test error into two terms, first one is bias and the other one is variance. We assume the true hypothesis is $h(x)$ and our hypothesis is $\hat{y}(x)$. Here is the derivation:
$E_D\left[ (\hat{y}(x;D) - h(x) ) ^ 2 \right] = (E_D \left[ \hat{y}(x;D) \right] - h(x) ) ^ 2 + E_D\left[ { (\hat{y}(x;D) - E_D \left[ {\hat{y}(x;D)} \right] ) ^ 2 } \right]$. Here we get the bias term and variance term. The explanation as follow:
We draw a fixed size of $m$ samples from underlying yet unknown distribution $\Phi$ to form training data $D$. And then we train our hypothesis on the sampled data $D$ and test a fixed point $x$. We repeat this experiment for infinite times and get the expectation of our prediction $E_D \left[ \hat{y}(x;D) \right]$. Then the expectation of difference between our trained hypothesis and true hypothesis is decomposed into two terms. One is the difference of prediction expectation and true result, the other is the variance of our prediction.

Explanation & Advice from Learning Theory

Q. Under which condition will a learning model be consistent.
A. A model will be consistent if and only if the VC dimension of target hypothesis space is finite. (A model consistent means the our trained hypothesis can approach the true hypothesis, this means a model will generalize well when its VC dimension is finite.)

Q. What’s the main reason for the difference between training and test error for a training sample of finite size $m$ ?
A. A formula as follow: $\left| Error_{test} - Error_{train} \right| \le \; g(d/m)$, here the $d$ is the VC dimension of our hypothesis class and $m$ is the training sample size.

Insight form Learning Theory: For fixed sample size, complex model will lead to larger difference between training and testing error; For fixed VC dimension, more sample will lower the performance gap between training and testing.

Generalization Theory & Structural Risk Minimization

$Risk \; Expectation = Empirical \; Risk + Structural \; Risk$, The empirical risk is the training error, the structure risk can be viewed as the function of VC dimension and sample size. We have the following bound:
$Generalization = TrainingError + \sqrt{\frac{d(\ln{(2m/d)} + 1) - \ln{\delta}}{m}}$
So we not only need to perform empirical risk minimization, but also need structural risk minimization. And we know the structural risk minimization comes from two perspect: VC dimension and sample size, but this two factors combined in a complex way.
For example, we get series models $H_1, \; H_2, \; ... \; H_n$ and their VC dimension non-decreased order. as model complexity increased, the empirical risk get down but structural risk get increased. We need a comprised model which give the best generalization performance.

Q. how can be control the VC dimension of hypothesis classes
- Reduce the number of parameters (works in most cases)
- If the number of parameters is fixed, we can use regularization.

Q. Connection between Bias-Variance and Structural Risk
A. Low structural risk model will be biased easily,a more complex model (which means high structural risk) will have high variance.

Against Over-fitting

Avoid over-fitting need to choose one model among lots of model. One basic yet very useful way would be

Cross Validation

practical advice for cross validation
- small data size need larger $K$.
- larger K will reduce the variance.

bias-variance trade off in cross validation. the number of folds $K$.
- larger K leads to lower bias estimate of the generalization error, but this estimate can be high variance.
- smaller value K will leads to higher bias but lower variance.

Regularization

regularization will reduce the structural risk, but you will need some kind of regularization parameters that need be determined through cross validation.

another interesting point about the regularization is the regularization can be interpretation of bayesian statistics. Like L2-norm regularization corresponds to gaussian prior, lapalce prior leads to L1-norm and so on.

Feature Selection

very effective through L1-norm regularization.
Another approach is to rank the feature and delete the feature that is not important. Ranking method listed below:
Mutual Information and So no.
Approaches to feature selection:
- filter ( ranking feature individually)
- wrapper (test the performance on some validation set)
- embedding (eliminate the feature at the same time of training models)

Information Criterion

like AIC/TIC, models the likelihood but also the model complexity.

Bayesian Model Averaging

Model the complexity through the following formula:
$P (D|M) = \log P(D | \hat{ \theta }_{ML}) - \frac{k}{2}\log{N}$
Often much better way than cross validation.

Lecture 7. Dimensionality Reduction

Parametric-driven dimensionality reduction
data-driven dimensionality reduction.
Linear dimensionality reduction:
- PCA
- LDA

Nonlinear dimensionality reduction:
- Isomap
- LLE

Lecture 8. Spectral Clustering

Some kind of matrix and then using SVD like methods to extract the features.

Spectral Clustering supplement to k-means clustering method.
Form the similarity matrix, calculate the degree matrix and get some kind of eigen value to get the cluster.

k-mean aimed at solving problem with gaussian-like distribution, but spectral clustering cal solve problem with much fancy structure.

Question: Need too much memory.

Lecture 9. Probabilistic Graphical Model

Graph model contains independence assumption and easy be factored.

directed graphical model can be factored according to conditional probability density. Independence can be retrieved from d-separation.

Undirected model is markov random fields, composed into factors.

Lecture 10. EM & Mixture Model

Optimize over the lower bound of full likelihood function.

Learning
Inference

Lecture 11. Exact Inference

Three most common inference problem
- likelihood of observed variable
- posterior of variable given evidence (observed variable)
- MAP estimate of variable Y given evidence X.

Algorithm
- Variable Elimination
- Message Passing
- Junction Tree Algorithm (Tree of cliques)

Lecture 12. Learning

Estimate parameters
- ML of completely observed of given structure. (Easy to calculate, but need to think data sparsity problem)
- Learning partially observed GM. (Need EM algorithm)
Learning depends on the inference algorithm.

Learning Structure model is hard.

Lecture 13. from HMM to CRF

CRF is a markov random field based on the observation which overcome label bias problem in HMM. The reason for label bias is easy, because HMM is an locally normalized model whereas CRF is global normalized model which could avoid the impact of locally feature sparsity.

Lecture 14. Latent Variable Model

Hierarchry Model for Text and Vision

Lecture 15. Approximate Inference

• Mean field
• Gibbs Sampling
  for approximate inference

Lecture 16. Maximum Margin Markov Network

Transfer what the objective from svm to markov network, i.e. maximize the margin.

Key point:
Test with synthetic data to test the algorithm and result.