Machine Learning

Definition:

• Learn and improve from “experience” without emperically programmed
• Most central problem is generalization, how to generalize the data learned to the data that the model never seen before
  • principle of induction
• Data set
  • comes from a set of samples
  • Each sample is a pair of input-output data
    • input $X$: a set of features (independent variables)
    • output $Y$: a label, a set of features (dependent variable)
    • Test set: final exam to test the ability of model to generalize
      • if test given is too different from what was taught, the algorithm can’t generalize pass its experience, it is a bad test
      • also a bad test if the test is exact same as what was taught, it doesn’t generalize at all
      • → a good test should test the ability to generalize
      • 
• Target function $f:X\to Y$
  • unknown
• Function hypotheses $H=\{h|h:X\to Y\}$
  • a set of possible functions that can map input to output
  • We aim to find $h\in H$ such best approximates $f$
• Loss function: $l(y,f(x))$
  • determines how bad is the predicted label compared to the true label
  • ex: in classification, $l(y,f(x))=0$ if $y=f(x)$, 1 if $y\ne f(x)$
• Data generating distribution: $D(x,y)$
  • Probability density function over pair $x,y$
• Expected loss: ${\mathbb{E}}_{(x,y)\sim D}[l(y,f(x))]={\sum }_{(x,y)}D(x,y)l(y,f(x))$
  • We wish to minimize expected loss
  • as we dont know $D$ but only samples of $D$, we assume Law of large number, therefore, the sample has same distribution as D
  • $\to {\mathbb{E}}_{(x,y)\sim D}[l(y,f(x))]\approx \frac{1}{N}{\sum }_{n=1}^{N}l\left(y^{(n)},f\left(x^{(n)}\right)\right)$

Two approaches in learning:

• Eager learning:
  • ex: Decision trees
  • Learn/train: induce from an abstract model from the data
  • Test/Predict/Classify: apply learned model to new data
• Lazy learning:
  • ex: Nearest neighbor
  • Learn: store data in memory
  • Test/Predict/Classify: compare new data to stored data
  • Properties:
    • retians all information seen in training
    • complex hypothesis space
    • classification can be slow
• To predict the target/label using features: Supervised Learning
• To find interesting patterns in data: Unsupervised learning
• Semi-supervised learning
• Reinforcement Learning
• Deep Learning

Inductive Bias:

• What the machine learns might differ from what we intended
  • ex: recognizing US vs Russian tanks model performs bad due to the quality of input pictures
• Due to not enough variety of data to narrow down the relevant concept to learn

Fitting

• Training Error over training data, ${\text{error}}_{\text{train}}(h)$
• True Error over training data, ${\text{error}}_{\text{true}}(h)$
• Overfitting
  • if ${\text{error}}_{\text{train}}(h)<{\text{error}}_{\text{test}}(h)$
    • test error as we cant know the true error
  • Amount of overfitting = ${\text{error}}_{\text{true}}(h)-{\text{error}}_{\text{test}}(h)$

Decision Tree

Classification Model and Nearest Neighbor for Classification

Perceptron Training

Linear Classifier

---

HMM

Model evaluation

---

Practical Consideration:

Hypothesis Testing

• Accuracy score of once cant tell if a model is better than another, perhaps due to chance

Debugging:

• Check implementation is correct
  • measure loss rather than accuracy
  • replace it with another easier dataset (toy)
• Is data too noisy?
• is learning problem too hard?

Strategies for isolating causes of errors:

• Is representation adequate?
  • Can you learn if you add a cheating feature that perfectly correlates with correct class?
• Train/test mismatch?
  • Try re-selecting train/test by shuffling training data and test together
• Do you have enough data? Try training on 80% of the training set, how much does it hurt performance?

Hyperparameter tuning with validation set vs cross-validation

• Cross-validation: loop through every hyperparameter setting for a hyperparameter and try which one leads to least error
• N-fold cross validation:
  • Instead of a single test-training split, split data into N equal-sized parts
  • Train and test N different classifiers and report average & std.deviation accuracy

Model evaluation

• Formalizing errors:
  • $error(f)=[error(f)-{\min }_{f^{\ast }\in F}error(f^{\ast })]+[{\min }_{f^{\ast }\in F}error(f^{\ast })]$
    • Estimation error (variance) + approximation error (bias)
      • estimation error = error of chosen f to optimal $f^{\ast }$
      • approximation error = error of $f^{\ast }$ of the hypothesis chosen
    • F is set of all possible classifiers of a hypothesis
    • $f^{\ast }$ is optimal classifier

Bias/variance trade-off

• if the learning algorithm is too flexible, it may fit each training dataset differently, high variance
• 
  • only one of bias or variance can be reduced at once and the optimum point should be chosen

Class imbalance problem

• How to deal with:
  1. Choose the right metrics: choose the one that is more relevant and important (ex: recall on cancer prediction is more important)
     • Symmetric vs asymmetric metrics
  2. Data-level methods: resampling
     • Undersampling: remove samples from the majority class
       • can cause loss of information
       • ex: Tomek Links, find pairs of close samples of opposite classes and remove the majority class in each pair
         • 
         • Make decision boundary clear but make model underfit (learn less)
         • only work with low-dimension data
     • Oversampling: add more examples to the minority class
       • can cause overfitting
       • ex: SMOTE
         • Synthesize samples of minority class as convex (linear) combinations of existing points and their nearest neighbors of same class
         • only work with low-dimension data
         • 
  3. Algorithm-level methods:
     • Instead of naive loss where all samples contribute equally to the loss, $L(X,\theta )={\sum }_{x}L(x,\theta )$
     • Idea: training samples we care about should contribute more to the loss
     • Ex:
       • Cost-sensitive learning
         • let $C_{i,j}$ be cost of class i but classified as class j
         • The loss caused by instance x of class i will become the weighted average of all possible classifications of instance x: $L(x,\theta )={\sum }_j{C}_{i,j}P(j|x,\theta )=C_{i0}P(y=0|x,\theta )+C_{i1}P(y=1|x,\theta )$
       • class-balanced loss
         • Give more weight to rare classes - then you incentivize the model to learn to classify them better.
         • $L(X,\theta )={\sum }_i{W}_{y_i}L(x_i,\theta )$
         • $W_c=\frac{N}{\text{number of samples of class C}}$
       • focal loss
         • Give more weight to the examples that the model is having difficulty with.
           • downweighs well-classified samples
         • estimates probability of the model for class $y=1:p_1=\{\begin{array}{ll}p& \text{if }y=1\\ 1-p& \text{otherwise}\end{array}$
         • Cross-entropy: $CE(p_t)=-\log (p_t)$
         • Focal loss: $FL(p_t)=-(1-p_t{)}^{\gamma }\log (p_t)$

A probabilistic view:

• Bayes theorem
• Joint Distribution
• Bayes Optimal Classifier
  • Assume we know the data generating function, $D$
  • We define Bayes Optimal Classifier as $f^{BO}(\hat{x})=\arg {\max }_{\hat{y}}D(\hat{x},\hat{y})$
  • Theorem: Of all the classifiers, the Bayes Optimal Classifier achieve the smallest zero/one loss
• Training = estimating $D$ from the finite training set
  • typically estimate $D$ as parameters of a probability distributions
  • assumption: independent and identically distributed
  • with maximum likelihood
  • If $X_i\perp X_j|Y,P(X_1,X_2,...,X_d)={\prod }_{i=1}^{d}P(X_i|Y)$
  • Naive Bayes classifier

Logistic regression:

• Binary classification:
  • $\begin{array}{rl}& P\left(Y^{(i)}=1\mid X^{(i)},\theta \right)=g\left(<\theta ,X^{(i)}>\right)\\ & P\left(Y^{(i)}=0\mid X^{(i)},\theta \right)=1-g\left(<\theta ,X^{(i)}>\right)\end{array}$
  • Predicted label $i$ of $y$ is $g(<\theta ,X^{(i)}>)$ which is a function that takes in a set of parameters $\theta$ and sample $i$ of input $X$
• We let $g(x)$ be a Sigmoid Function as it range from 0 to 1
• Logistic regression with Maximum Likelihood Estimation:
  • $\underset{\theta }{\max }\prod _{i=1}^{N}P(Y^{(i)}|X^{(i)},\theta )=\underset{\theta }{\max }\prod _{i=1}^{N}g(<\theta ,X^{(i)}>{)}^{Y^{(i)}}(1-g(<\theta ,X^{(i)}>){)}^{1-Y^{(i)}}$
    • the parameter that make the product of observed samples as likely as possible
  • taking $\log$
  • ${\max }_{\theta }{\sum }_{i=1}^N\underset{\text{Cross-entropy loss function }}{\underbrace{Y^{(i)}\log g\left(<\theta ,X^{(i)}>\right)+\left(1-Y^{(i)}\right)\log (1-g\left(<\theta ,X^{(i)}>\right)}})$
    • Solve this by Gradient Descent and Properties
  • Let $\ell (\theta )=y\log \left(g\left({\theta }^{T}x\right)\right)+(1-y)\log \left(1-g\left({\theta }^{T}x\right)\right)$
  • $\frac{\partial }{\partial {\theta }_j}\ell (\theta )=\frac{\partial }{\partial {\theta }_i}\left[y\log \left(g\left({\theta }^{T}x\right)\right)+(1-y)\log \left(1-g\left({\theta }^{T}x\right)\right)\right]$
  • $\begin{array}{rl}\frac{\partial }{\partial {\theta }_j}\ell (\theta )& =\left(y\frac{1}{g\left({\theta }^{T}x\right)}-(1-y)\frac{1}{1-g\left({\theta }^{T}x\right)}\right)\frac{\partial }{\partial {\theta }_j}g\left({\theta }^{T}x\right)\\ & =\left(y\frac{1}{g\left({\theta }^{T}x\right)}-(1-y)\frac{1}{1-g\left({\theta }^{T}x\right)}\right)g\left({\theta }^{T}x\right)(1-g\left({\theta }^{T}x\right))\frac{\partial }{\partial {\theta }_j}{\theta }^{T}x\\ & =\left(y\left(1-g\left({\theta }^{T}x\right)\right)-(1-y)g\left({\theta }^{T}x\right)\right)x_j\\ & =\left(y-h_{\theta }(x)\right)x_j\end{array}$
    • Solve this by Gradient Descent and Properties, Stochastic gradient descent ${\theta }_{k+1}={\theta }_k+\eta \left(Y^i-g\left(<\theta ,X^i>\right)\right)X^{(i)}$

Multiclass classification:

• Classification Model
• Reductions for Multi-class Classification
  • Given
    1. An input space $\mathcal{X}$ and number of classes $K$
    2. An unknown distribution $\mathcal{D}$ over $\mathcal{X}\times [K]$
  • Learning: Find a function $f$ minimizing $E_{(x,y)\sim \mathcal{D}}[f(x)\ne y]$
  • In most task, this works for $K<100$, for larger $K$, frame problem differently
  • Reduction 1: One-versus-All
    • Train K number of binary classifiers, each classifier classifies whether a sample is in that class or not
    • At test time
      • If only one classifier predicts positive, predict that class
      • if not, Break ties randomly
    • OneVersusAllTraing(D_multiclass, BinaryTraing)

        for i = 1 to K:
          D_bin <- relabel D_multiclass so class i is positive and !i is negative
          f_i <- BinaryTrain(D_bin)
       endfor
        return f_1, f_2,..,f_K
      

    • OneVersusAllTest(f_1, f_2,...,f_K, hat_x)

      score <- <0,0,...,0> //initialize K-many scores to 0
      for i = 1 to K:
          y <- f_i(hat_x)
          score_i <- score_i + y
      end for
      return argmax_k(score_k)
      

  • Reduction 2: All-versus-All
    • Train $K(K-1)/2$ number of binary classifiers, each classifier classifies whether a sample is in that class i or class j for every pair of class
• Recall that:
  • $X^{(i)}\to \text{function (example: linear)}{\theta }^{T}x\to g(.)\text{(sigmoid)}\to g({\theta }^T{X}^{(i)})$
  • $g({\theta }^T{X}^{(i)}\approx 1\to Y^{(i)}=1$
  • $g({\theta }^T{X}^{(i)}\approx 0\to Y^{(i)}=0$
  • Let ${\theta }_0$ be array of $0$
  • $P(Y=1\mid X,\theta )=g\left({\theta }^{t}X\right)=\frac{1}{1+e^{-{\theta }^{T}X}}=\frac{e^{{\theta }^{T}X}}{1+e^{{\theta }^{T}X}}=\frac{e^{{\theta }^{T}X}}{e^{{\theta }_0^{t}X}+e^{{\theta }^{T}X}}$
  • $P(Y=0\mid X,\theta )=1-g\left({\theta }^{t}X\right)=\frac{1}{1+e^{{\theta }^{T}X}}=\frac{e^{{\theta }_0^{T}X}}{e^{{\theta }_0^{t}X}+e^{{\theta }^{T}X}}$
  • → softmax function
• This can be extended to work with multl-label classification:
  • 
• Recall the binary case

$$\underset{\theta }{\max }\sum _{i=1}^N{Y}^{(i)}\log g\left(<\theta ,X^{(i)}>\right)+\left(1-Y^{(i)}\right)\log \left(1-g\left(<\theta ,X^{(i)}>\right)\right)$$

• Multi-label case

$$\underset{\theta }{\max }\sum _{\text{all samples }}1\left\{Y^{(i)}=\text{ label }\right\}\log (\text{ corresponding confidence prob.) }$$

Neural Network

PCA

• better representations of our data point
  • to visualize better, remove noise, less resource requirements, better classification
• Sample variance of data project on vector $v$ is ${\sum }_{i=1}^n(x_i^{T}v{)}^2=(Xv{)}^T(Xv)=v^T{X}^{T}Xv$
• Objective: Finding vector that maximize sample variance of projected data → Lagrangian folds constants into objective:
  • $\arg {\max }_v{v}^T{X}^{T}Xv-\lambda (v^{T}v-1)$
  • solution: $v$ such $X^{T}Xv=\lambda v$
• The eigenvalue $\lambda$ denotes the amount of variability captured along dimension $v$
  • sample variance of projection $v^T{X}^{T}Xv=\lambda$
• if we rank eigenvalues from large to small
  • the 1st principle component of $X^{T}X$ is associated with largest eigenvalue
  • the 2nd principle component of $X^{T}X$ is associated with 2nd largest eigenvalue
• It also minimizes construction error: $\frac{1}{n}{\sum }_{i=1}^n||x_i-(v^T{x}_i)v|{|}^2$
• limit to only linear projection and only based on covariance

Autoencoder

• Its non-linear dimensionality reduction method
  • 
• If autoencoder doesnt have activation function, it is works same as PCA
• $f(x)=s(wx+b)=z$
  • $s$ is activation function such as sigmoid
  • $z$ is the latent representation
• $g(z)=s(w_g^{T}z+b_g)=\hat{x}$
• Then $h(x)=g(f(x))=\hat{x}$
• pretraining helps the model start with weights that have already been optimized for general patterns, improving learning efficiency and potentially leading to better performance
• Pretraining process with autoencoders
  • Pretraining step: train a sequence of shallow autoencoders, greedily one layer at a time, using unsupervised data
  • Fine-tuning step 1: train the last layer using supervised data
  • Fine-tuning step 2: use backpropagation to fine-tune the entire network using supervised data.
  • Why does this work?: it is easier to train one layer at a time and can utilize unlabeled data

Kernel methods/tricks:

• Feature mapping:
  • 
  • Add new dimensions to the vector so that its linearly separable
  • example: $x=\{x_1,x_2\}\to z=\{x_1^2,\sqrt{2}{x}_1{x}_2.x_2^2\}=\varphi (x)$
  • Cons: more expensive to train, require more training examples
• Kernel methods:
  • rewrite linear models so that the mapping never needs to be explicitly computed, only depend on the dot products between 2 examples
  • Replace dot product $\varphi (x{)}^T\varphi (z)$ by $k(x,z)$
  • example: $k(x,z)=(x^{T}z{)}^2$ is as same as $\varphi (x)=\{x_1^2,\sqrt{2}{x}_1{x}_2,x_2^2\}$
• Kernels: Formally defined
  • each kernel $k$ has an associated feature mapping $\varphi$ that takes input $x\in \chi$ (input space) and maps to $\mathbb{F}$ (feture space)
  • Kernel k takes 2 inputs and gives their similarity in $F$ space, $k:\chi \times \chi \to \mathbb{R},k(x,z)=\varphi (x{)}^T\varphi (z)$
  • $F$ needs to be s vector space with a dot product defined on it, also called Hilbert Space
• Mercer’s condition
  • Not all function can be used as a kernal function, it must satisfy Mercer’s condition
  • For $k$ to be a kernel function:
    • There must exist a Hilbert Space $F$ for which $k$ defines a dot product
    • The above is true if $K$ is a positive definite function
    • $\int d\mathbf{x}\int d\mathbf{z}f(\mathbf{x})k(\mathbf{x},\mathbf{z})f(\mathbf{z})>0\left(\forall f\in L_2\right)$
      • For all square integrable functions $f$
• Constructing combinations of kernels:
  • slide 22