CMU 11-785 L03 Learning the network

Preliminary

• The bias can also be viewed as the weight of another input component that is always set to 1

• $z=\sum_{i} w_{i} x_{i}$z=∑i​wi​xi​

• What we learn: The …parameters… of the network

• Learning the network: Determining the values of these parameters such that the network computes the desired function

• How to learn a network?

  • $\widehat{\boldsymbol{W}}=\underset{W}{\operatorname{argmin}} \int_{X} \operatorname{div}(f(X ; W), g(X)) d$W=Wargmin​∫X​div(f(X;W),g(X))d
  • div() is a divergence function thet goes to zero when $f(X ; W)=g(X)$f(X;W)=g(X)

• But in practice $g(x)$g(x) will not have such specification

  • Sample $g(x)$g(x): just gather training data

Learning

Simple perceptron

do For $i = 1.. N_{train}$i=1..Ntrain​

$O(x_i) = sign(W^TX_i)$O(xi​)=sign(WTXi​)

if $O(x_i) \neq y_i$O(xi​)​=yi​

$W = W+Y_iX_i$W=W+Yi​Xi​

until no more classification errors

A more complex problem

• This can be perfectly represented using an MLP
• But perveptron algorithm require linearly separated labels to be learned in lower-level neurons
  • An exponential search over inputs
• So we need differentiable function to compute the change in the output for …small… changes in either the input or the weights

Empirical Risk Minimization

Assuming $X$X is a random variable:
$\begin{aligned} \widehat{\boldsymbol{W}}=& \underset{W}{\operatorname{argmin}} \int_{X} \operatorname{div}(f(X ; W), g(X)) P(X) d X \\ &=\underset{W}{\operatorname{argmin}} E[\operatorname{div}(f(X ; W), g(X))] \end{aligned}$W=​Wargmin​∫X​div(f(X;W),g(X))P(X)dX=Wargmin​E[div(f(X;W),g(X))]​
Sample $g(X)$g(X), where $d_{i}=g\left(X_{i}\right)+ noise$di​=g(Xi​)+noise, estimate function from the samples

The empirical estimate of the expected error is the average error over the samples
$E[\operatorname{div}(f(X ; W), g(X))] \approx \frac{1}{N} \sum_{i=1}^{N} \operatorname{div}\left(f\left(X_{i} ; W\right), d_{i}\right)$E[div(f(X;W),g(X))]≈N1​i=1∑N​div(f(Xi​;W),di​)

Empirical average error (Empirical Risk) on all training data
$\operatorname{Loss}(W)=\frac{1}{N} \sum_{i} \operatorname{div}\left(f\left(X_{i} ; W\right), d_{i}\right)$Loss(W)=N1​i∑​div(f(Xi​;W),di​)

Estimate the parameters to minimize the empirical estimate of expected error
$\widehat{\boldsymbol{W}}=\underset{W}{\operatorname{argmin}} \operatorname{Loss}(W)$W=Wargmin​Loss(W)

Problem statement

• Given a training set of input-output pairs

  $\left(\boldsymbol{X}_{1}, \boldsymbol{d}_{1}\right),\left(\boldsymbol{X}_{2}, \boldsymbol{d}_{2}\right), \ldots,\left(\boldsymbol{X}_{N}, \boldsymbol{d}_{N}\right)$(X1​,d1​),(X2​,d2​),…,(XN​,dN​)

• Minimize the following function

$\operatorname{Loss}(W)=\frac{1}{N} \sum_{i} \operatorname{div}\left(f\left(X_{i} ; W\right), d_{i}\right)$Loss(W)=N1​i∑​div(f(Xi​;W),di​)

• This is problem of function minimization
  • An instance of optimization