§ 3. Shallow Neural Networks¶
Supervised Learning Problem¶
Definition 3.1 : Supervised Learning Setup
We have data \(X_{1}, \ldots, X_{N} \in \mathcal{X}\) and corresponding labels \(Y_{1}, \ldots, Y_{N} \in \mathcal{Y}\).
- Example) \(X_{i}\) is the \(i\) th email and \(Y_{i} \in\{-1,+1\}\) denotes whether \(X_{i}\) is a spam email.
- Example) \(X_{i}\) is the \(i\) th image and \(Y_{i} \in\{0, \ldots, 9\}\) denotes handwritten digit.
Assume there is a true unknown function
mapping data to its label. In particular, \(Y_{i}=f_{\star}\left(X_{i}\right)\) for \(i=1, \ldots, N\).
The goal of supervised learning is to use \(X_{1}, \ldots, X_{N}\) and \(Y_{1}, \ldots, Y_{N}\) to find \(f \approx f_{\star}\).
Definition 3.2 : Supervised Learning Objective
Assume a loss function such that \(\ell\left(y_{1}, y_{2}\right)=0\) if \(y_{1}=y_{2}\) and \(\ell\left(y_{1}, y_{2}\right)>0\) if \(y_{1} \neq y_{2}\).
Restrict search to a class of parametrized functions \(f_{\theta}(x)\) where \(\theta \in \Theta \subseteq \mathbb{R}^{p}\), i.e., only consider \(f \in\left\{f_{\theta} \mid \theta \in \Theta\right\}\) where \(\Theta \subseteq \mathbb{R}^{p}\).
Take a finite sample \(X_{1}, \ldots, X_{N} \in \mathcal{X}\) and corresponding labels \(Y_{1}, \ldots, Y_{N} \in \mathcal{Y}\). Then solve
which is equivalent to
This is the standard form of the optimization problem (except regularizers) we consider in the supervised learning. We will talk about regularizers later.
Concept 3.3 : Training is optimization.
In machine learning, the anthropomorphized word "training" refers to solving an optimization problem such as
In most cases, SGD or variants of SGD are used.
We call \(f_{\theta}\) the machine learning model or the neural network.
Example 3.4 : Least-Squares Regression
In LS, \(\mathcal{X}=\mathbb{R}^{p}, \mathcal{Y}=\mathbb{R}, \Theta=\mathbb{R}^{p}, f_{\theta}(x)=x^{\top} \theta\), and \(\ell\left(y_{1}, y_{2}\right)=\frac{1}{2}\left(y_{1}-y_{2}\right)^{2}\).
So we solve
where \(X=\left[\begin{array}{c}X_{1}^{\top} \\ \vdots \\ X_{N}^{\top}\end{array}\right]\) and \(Y=\left[\begin{array}{c}Y_{1} \\ \vdots \\ Y_{N}\end{array}\right]\).
The model \(f_{\theta}(x)=x^{\top} \theta\) is a shallow neural network. (The terminology will makes sense when contrasted with deep neural networks.)
Linear Classification¶
Definition 3.5 : Binary Classification and Linear Separability
In binary classification, we have \(\mathcal{X}=\mathbb{R}^{p}\) and \(\mathcal{Y}=\{-1,+1\}\).
The data is linearly separable if there is a hyperplane defined by \((a_{\text {true }}, b_{\text {true }} )\) such that
Support Vector Machine¶
Consider linear (affine) models
Consider the loss function
The optimization problem
has a solution with optimal value 0 when the data is linearly separable.
Problem: Optimization problem is discontinuous and thus cannot be solved with SGD.
Motivation for SVM
Even if the underlying function or phenomenon to approximate is discontinuous, the model needs to be continuous in its parameters. The loss function also needs to be continuous. (The prediction need not be continuous.)
We consider a relaxation, is a continuous proxy of the discontinuous thing. Specifically, consider
Once trained, \(f_{a, b}(x)>0\) means the neural network is predicting \(y=+1\) to be "more likely", and \(f_{a, b}(x)<0\) means the neural network is predicting \(y=-1\) to be "more likely".
Therefore, we train the model to satisfy
Problem with strict inequality \(Y_{i} f_{a, b}\left(X_{i}\right)>0\) :
- Strict inequality has numerical problems with round-off error.
- The magnitude \(\left|f_{a, b}(x)\right|\) can be viewed as the confidence of the prediction, but having a small positive value for \(Y_{i} f_{a, b}\left(X_{i}\right)\) indicates small confidence of the neural network.
We modify our model's desired goal to be \(Y_{i} f_{a, b}\left(X_{i}\right) \geq 1\).
To train the neural network to satisfy
we minimize the excess positive component of the RHS
which is equivalent to
If the optimal value is 0, then the data is linearly separable.
Definition 3.6 : Support Vector Machine (SVM)
Use the model
This following formulation is called the support vector machine (SVM)
It is also common to add a regularizer
Concept 3.7 : Prediction with SVM
Once the SVM is trained, make predictions with
when \(f_{a, b}(x)=0\), we assign \(\operatorname{sign}\left(f_{a, b}(x)\right)\) arbitrarily.
Note that the prediction is discontinuous, but predictions are in \(\{-1,+1\}\) so it must be discontinuous.
If \(\sum_{i=1}^{N} \max \left\{0,1-Y_{i} f_{a, b}\left(X_{i}\right)\right\}=0\), then \(\operatorname{sign}\left(f_{a, b}\left(X_{i}\right)\right)=Y_{i}\) for \(i=1, \ldots, N\), i.e., the neural network predicts the known labels perfectly. Of course, it is a priori not clear how accurate the prediction will be for new unseen data.
Logistic Regression¶
Concept 3.8 : Relaxed Supervised Learning Setup
We relax the supervised learning setup to predict probabilities, rather than make point predictions. So, labels are generated based on data, perhaps randomly. Consider data \(X_{1}, \ldots, X_{N} \in \mathcal{X}\) and labels \(Y_{1}, \ldots, Y_{N} \in \mathcal{Y}\). Assume there exists a function
where \(\mathcal{P}(\mathcal{Y})\) denotes the set of probability distributions on \(\mathcal{Y}\). Assume the generation of \(Y_{i}\) given \(X_{i}\) is independent of \(Y_{j}\) and \(X_{j}\) for \(j \neq i\).
- Example) \(f(X)=\left[\begin{array}{l}0.8 \\ 0.2\end{array}\right]\) in dog vs. cat classifier.
- Example) An email saying "Buy this thing at our store!" may be spam to some people, but it may not be spam to others.
The relaxed SL setup is more general and further realistic.
Definition 3.9 : Empirical Distribution for Binary Classification
In basic binary classification, define the empirical distribution
More generally, the empirical distribution describes the data we have seen. In this context, we have only seen one label per datapoint, so our empirical distributions are one-hot vectors.
(If there are multiple annotations per data point \(x\) and they don't agree, then the empirical distribution may not be one-hot vectors. For example, given the same email, some users may flag it as spam while others consider it useful information.)
Definition 3.10 : KL-Divergence, Cross Entropy
Let \(p, q \in \mathbb{R}^{n}\) represent probability masses, i.e., \(p_{i} \geq 0\) for \(i=1, \ldots, n\) and \(\sum_{i=1}^{n} p_{i}=1\) and the same for \(q\). The Kullback-Leibler-divergence (KL-divergence) from \(q\) to \(p\) is
The cross entropy of \(q\) relative to \(p\) is
Theorem 3.11 : Properties of KL-Divergence
- Not symmetric, i.e., \(D_{\mathrm{KL}}(p \| q) \neq D_{\mathrm{KL}}(q \| p)\).
- \(D_{\mathrm{KL}}(p \| q)>0\) if \(p \neq q\) and \(D_{\mathrm{KL}}(p \| q)=0\) if \(p=q\).
- \(D_{\mathrm{KL}}(p \| q)=\infty\) is possible. (Further detail below.)
Often used as a "distance" between \(p\) and \(q\) despite not being a metric.
Clarification: Use the convention
- \(0 \log \left(\frac{0}{0}\right)=0\left(\right.\) when \(\left.p_{i}=q_{i}=0\right)\)
- \(0 \log \left(\frac{0}{q_{i}}\right)=0\) if \(q_{i}>0\)
- \(p_{i} \log \left(\frac{p_{i}}{0}\right)=\infty\) if \(p_{i}>0\)
Probabilistic interpretation:
with the random variable \(I\) such that \(\mathbb{P}(I=i)=p_{i}\).
Definition 3.12 : Logistic Regression (LR)
Logistic regression (LR), is another model for binary classification:
Use the model
Minimize KL-Divergence (or cross entropy) from the model \(f_{a, b}\left(X_{i}\right)\) output probabilities to the empirical distribution \(\mathcal{P}\left(Y_{i}\right)\).
Concept 3.13 : Other Expression of Logistic Regression
where \(\ell(z)=\log \left(1+e^{-z}\right)\).
Concept 3.14 : Prediction with LR
When performing point prediction with \(\mathrm{LR}, a^{\top} x+b>0\) means \(\mathbb{P}(y=+1)>0.5\) and vice versa.
Once the LR is trained, make predictions with
when \(a^{\top} x+b=0\), we assign \(\operatorname{sign}\left(a^{\top} x+b\right)\) arbitrarily. This is the same as SVM.
Again, it is a priori not clear how accurate the prediction will be for new unseen data.
Both support vector machine and logistic regression can be written as
- SVM uses \(\ell(z)=\max \{0,1-z\}\). Obtained from relaxing the discontinuous prediction loss.
- LR uses \(\ell(z)=\log \left(1+e^{-z}\right)\). Obtained from relaxing the supervised learning setup from predicting the label to predicting the label probabilities.
SVM and LR are both "linear" classifiers:
- Decision boundary \(a^{\top} x+b=0\) is linear.
- Model completely ignores information perpendicular to \(a\).
LR naturally generalizes to multi-class classification via softmax regression. Generalizing SVM to multi-class classification is trickier and less common.
Concept 3.16 : Maximum Likelihood Estimation \(\cong\) minimizing KL divergence
Consider the setup where you have IID discrete random variables \(X_{1}, \ldots, X_{N}\) that can take values \(1, \ldots, k\). We model the probability masses with \(\mathbb{P}_{\theta}(X=1), \ldots, \mathbb{P}_{\theta}(X=k)\). The maximum likelihood estimation (MLE) is obtained by solving
Next, define
Then MLE is equivalent to minimizing the KL divergence from the model to the empirical distribution.
One can also derive LR equivalently as the MLE.
Generally, one can view the MLE as minimizing the KL divergence between the model and the empirical distribution. (For continuous random variables like the Gaussian, this requires extra work, since we haven't defined the KL divergence for continuous random variables.)
In deep learning, the distance measure need not be KL divergence.
Prediction¶
Definition 3.17 : Estimation, Prediction
Finding \(f \approx f_{\star}\) for unknown
is called estimation. When we consider a parameterized model \(f_{\theta}\), finding \(\theta\) is the estimation. However, estimation is usually not the end goal.
The end goal is prediction. It is to use \(f_{\theta} \approx f_{\star}\) on new data \(X_{1}^{\prime}, \ldots, X_{M}^{\prime} \in \mathcal{X}\) to find labels \(Y_{1}^{\prime}, \ldots, Y_{M}^{\prime} \in \mathcal{Y}\).
Concept 3.18 : Is prediction possible?
In the worst hypotheticals, prediction is impossible.
- Even though smoking is harmful for every other human being, how can we be 100% sure that this one person is not a mutant who benefits from the chemicals of a cigarette?
- Water freezes at \(0^{\circ}\), but will the same be true tomorrow? How can we be 100% sure that the laws of physics will not suddenly change tomorrow?
Of course, prediction is possible in practice.
Theoretically, prediction requires assumptions on the distribution of \(X\) and the model of \(f_{\star}\) is needed. This is in the realm of statistics of statistical learning theory.
For now, we will take the view that if we predict known labels of the training data, we can reasonably hope to do well on the new data. (We will discuss the issue of generalization and overfitting later.)
Concept 3.19 : Training Data vs Test Data
When testing a machine learning model, it is essential that one separates the training data with the test data.
In other classical disciplines using data, one performs a statistical hypothesis test to obtain a \(p\)-value. In ML, people do not do that.
The only sure way to ensure that the model is doing well is to assess its performance on new data.
Usually, training data and test data is collected together. This ensures that they have the same statistical properties. The assumption is that this test data will be representative of the actual data one intends to use machine learning on.
Datasets¶
Images of hand-written digits with \(28 \times 28=784\) pixels and integervalued intensity between 0 and 255 . Every digit has a label in \(\{0,1, \ldots, 8,9\}\).
70,000 images (60,000 for training / 10,000 testing) of 10 almost balanced classes.
One of the simplest data set used in machine learning.
The USA government needed a standardized test to assess handwriting recognition software being sold to the government. So the NIST (National Institute of Standards and Technology) created the dataset in the 1990s. In 1990, NIST Special Database 1 distributed on CD-ROMs by mail. NIST SD 3 (1992) and SD 19 (1995) were improvements.
Humans were instructed to fill out handwriting sample forms. However, humans cannot be trusted to follow instructions, so a lab technician performed "human ground truth adjudication".
In 1998, Man LeCun, Corinna Cortes, Christopher J. C. Barges took the NIST dataset and modified it to create the MNIST dataset.
60,000 \(32 \times 32\) color images in 10 (perfectly) balanced classes.
(There is no overlap between automobiles and trucks. “Automobile” includes sedans, SUVs, things of that sort. “Truck” includes only big trucks. Neither includes pickup trucks.)
In 2008, a MIT and NYU team created the 80 million tiny images data set by searching on Google, Flickr, and Altavista for every non-abstract English noun and downscaled the images to \(32 \times 32\). The search term provided an unreliable label for the image. This dataset was not very easy to use since the classes were too numerous.
In 2009, Alex Krizhevsky published the CIFAR10, by distilling just a few classes and cleaning up the labels. Students were paid to verify the labels.
The dataset was named CIFAR-10 after the funding agency Canadian Institute For Advanced Research.
There is also a CIFAR-100 with 100 classes.
Concept 3.22 : Roles of Datasets in ML Research
An often underappreciated contribution.
Good datasets play a crucial role in driving progress in ML research.
Thinking about the dataset is the essential first step of understanding the feasibility of a ML task.
Accounting for the cost of producing datasets and leveraging freely available data as much as possible (semi-supervised learning) is a recent trend in machine learning.