Stochastic Gradient Descent
" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "We are interested in minimizing the **additive** loss function \n", "\n", "$$\n", "J(\\theta) = \\sum_{i=1}^m J_i(\\theta),\\quad\\quad\\quad J_i(\\theta):= ( h_\\theta({\\bf x}^{(i)}) - y^{(i)} )^2\n", "$$" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "One random instance $\\{(x^{(\\omega)},y^{(\\omega)})\\}$ in the training set is picked at every step $k$ and the gradient is computed based only on this instance. This gradient is $\\nabla J_\\omega(\\theta) = \\nabla_\\theta J_\\omega(\\theta)$ and is equal to\n", "\n", "$$\n", "\\nabla J_\\omega(\\theta):=\n", "2 (h_\\theta({\\bf x}^{(\\omega)}) - y^{(\\omega)}) {\\bf x}^{(\\omega)}.\n", "$$" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "The **Stochastic Gradient Descent** (SGD) algorithm for MSE minimization in linear regression is given by \n", "\n", "$$\n", "\\theta^{(0)} \\mbox{ initial guess},\\quad \\quad\\quad \n", "\\left\\{\\begin{array}{}\n", "{\\omega} \\mbox{ randomly selected in} \\{1,2,\\dots,n\\} \\\\\n", "\\theta^{(k+1)}= \\theta^{(k)} - \\eta \\nabla J_{\\omega}(\\theta^{(k)})\n", "\\end{array}\n", "\\right.\n", "\\quad\\quad\\quad k\\geq0.\n", "$$\n", "\n", "Only one random instance $\\{(x^{(\\omega)},y^{(\\omega)})\\}$ of training data $X$ is used at every step." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "- Every step $k$ of the algorithm is much faster. \n", "- This makes it possible to train on large training sets.\n" ] }, { "cell_type": "code", "execution_count": 10, "metadata": { "slideshow": { "slide_type": "subslide" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "[[1.97779774]\n", " [4.97149486]]\n" ] } ], "source": [ "n_epochs = 50\n", "t0, t1 = 5, 50 # learning schedule hyperparameters\n", "def learning_schedule(t): \n", " return t0/(t+t1)\n", " \n", "theta = np.random.randn(2,1) # random initialization\n", "for epoch in range(n_epochs): \n", " for i in range(m):\n", " random_index = np.random.randint(m)\n", " xi = X_b[random_index:random_index+1]\n", " yi = y[random_index:random_index+1]\n", " gradients = 2 * xi.T.dot(xi.dot(theta) - yi)\n", " eta = learning_schedule(epoch * m + i)\n", " theta = theta - eta * gradients\n", " \n", "print(theta)" ] }, { "cell_type": "code", "execution_count": 11, "metadata": { "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "name": "stderr", "output_type": "stream", "text": [ "/anaconda3/lib/python3.7/site-packages/sklearn/linear_model/stochastic_gradient.py:152: DeprecationWarning: n_iter parameter is deprecated in 0.19 and will be removed in 0.21. Use max_iter and tol instead.\n", " DeprecationWarning)\n" ] }, { "data": { "text/plain": [ "(array([1.97771021]), array([4.960105]))" ] }, "execution_count": 11, "metadata": {}, "output_type": "execute_result" } ], "source": [ "from sklearn.linear_model import SGDRegressor\n", "sgd_reg = SGDRegressor(n_iter=50, penalty=None, eta0=0.1) \n", "sgd_reg.fit(x, y.ravel())\n", "sgd_reg.intercept_, sgd_reg.coef_ " ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "### Variant\n", "\n", "- Mini-batch SGD\n", "- Momentum \n", "- Nesterov accelerated gradient\n", "- Adagrad / Adadelta / RMSprop / Adam / AdaMax / Nadam" ] }, { "cell_type": "code", "execution_count": 12, "metadata": { "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "data": { "text/html": [ "\n", "Logistic Regression
" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "Principle
\n", "\n", "**Logistic Regression** (also called **Logit Regression**) algorithms are used for **binary classification**.\n", "The model estimates the probability that an instance belongs to one of two classes (**{0,1}** or **{Y,N}** or **{+,-}** etc) and predicts for the instance the class with the highest probability.\n", "\n" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "In logistic regression, the model estimate a parameter \n", "$\\theta= (\\theta_0,\\theta_1,\\dots,\\theta_n)^T\\in {\\mathbb R}^{n+1}$, and predicts \n", "a class in **{0,1}** according to\n", "\n", "$$\n", "\\hat y = \n", "\\left\\{\n", "\\begin{array}{cc}\n", "0 \\quad \\mbox{if}\\quad \\sigma(\\theta.{\\bf x})<0.5 \\\\\n", "1 \\quad \\mbox{if}\\quad \\sigma(\\theta.{\\bf x})\\geq 0.5\n", "\\end{array}\n", "\\right.\n", "$$\n", "where $\\sigma$ is the sigmoid function. \n", "\n", "\n", "The number $\\hat p:=\\sigma(\\theta.{\\bf x})\\in ]0,1[$ is an estimated\n", "probability that $x$ belongs to class $1$. \n", "
" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "Logistic function
\n", "\n", "
![](\"sigmoid_function.svg\")
\n",
"\n",
"\n"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"Observe: \n",
"\n",
"● $\\sigma(\\theta\\cdot{\\bf x})\\geq0.5$ if and only if $\\theta \\cdot {\\bf x}\\geq 0$.
\n", "● $\\sigma(\\theta\\cdot{\\bf x})\\lt0.5$ if and only if $\\theta \\cdot {\\bf x} \\lt 0$. \n", "
"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"Observe: \n",
"$$\n",
"\\sigma'(t) = \\sigma(t) (1- \\sigma(t))\n",
"$$"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"\n", "● $\\sigma(\\theta\\cdot{\\bf x})\\lt0.5$ if and only if $\\theta \\cdot {\\bf x} \\lt 0$. \n", "
Loss function
\n", "We introduce \n", "\n", "$$\n", "\\hat p=h_\\theta(x)=\\sigma(\\theta. {\\bf x})=\\sigma(\\theta_0+\\theta_1 x_1+\\dots+\\theta_n x_n)\n", "$$\n", "\n", "then \n", "\n", "$$\n", "c(\\theta)=\\left\\{\\begin{array}{l}- \\log(\\hat p)\\quad &\\quad y=1\\\\- \\log(1- \\hat p)\\quad &\\quad y=0\\\\\n", "\\end{array}\n", "\\right.\n", "\\quad\\quad\n", "\\equiv \n", "\\quad\\quad\n", "c(\\theta)\n", "=-\\bigg[\\log(\\hat p) y+ \\log(1- \\hat p) (1-y)\\bigg]\n", "$$\n", "\n", "This cost function is intuitive \n", "- $-\\log(p)=\\log(1/p)$ grows very large when $p$ approaches $0$. The cost (penality) is large if the model estimates a probability close to $0$ for instance in class $1$.\n", "\n", "\n", "- $-\\log(1-p)=\\log(1/(1-p))$ is close to $0$ when $p$ approaches $0$. The cost (penality) is small if the model estimates a probability close to $0$ for instance in class $0$.\n", "\n", "\n", "- Same observation if $p$ approaches $1$.\n" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "Given a training set $\\{(x^{(1)},y^{(1)}),\\dots,(x^{(m)},y^{(m)})\\} \\subset \\mathbb R^n \\times \\mathbb \\{0,1\\}$. \n", "The **loss function** is given by \n", "\n", "$$\n", "J(\\theta) = \\frac 1{m} \\sum_{i=1}^m c^{(i)}(\\theta),\\quad\\quad\\quad c^{(i)}(\\theta)=-\\bigg[\\log(\\hat p^{(i)}) y^{(i)} + \\log(1- \\hat p^{(i)}) (1-y^{(i)})\\bigg]\n", "$$" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "Gradient computation
\n", "\n", "Given $c(\\theta) =-\\big[\\log(\\hat p) y+ \\log(1- \\hat p) (1-y)\\big]$, observe\n", "\n", "$$\n", "\\frac {\\partial c }{\\partial \\theta_j}\n", "=\\frac {\\partial c }{\\partial \\hat p }\\frac {\\partial \\hat p }{\\partial (\\theta.{\\bf x})}\\frac {\\partial (\\theta.{\\bf x})}{\\partial \\theta_j }\n", "=\\frac {\\partial c }{\\partial \\hat p }\\;\\sigma'(\\theta.{\\bf x})\\;x_j\n", "$$\n", "\n", "We have \n", "\n", "$$\n", "\\frac {\\partial c }{\\partial \\hat p } = -\\bigg[\\frac 1 {\\hat p} y - \\frac 1{1- \\hat p} (1-y)\\bigg]\\quad\\quad\\sigma'(\\theta.{\\bf x})\\;= \\sigma (\\theta.{\\bf x}) (1-\\sigma(\\theta.{\\bf x})) = \\hat p (1- \\hat p) \n", "$$\n", "\n", "Finally\n", "\n", "$$\n", "\\frac {\\partial c }{\\partial \\theta_j}=-\\bigg[(1- \\hat p) y - \\hat p (1-y)\\bigg]x_j=\\big[ \\hat p -y \\big]x_j\n", "$$" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "Chain rule: seed to Back-propagtion algorithms
" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "The partial derivatives of $J$ are given by \n", "$$\n", "\\frac {\\partial J(\\theta) }{\\partial \\theta_j}=\\frac 1{m} \\sum_{i=1}^m \\frac {\\partial c^{(i)}(\\theta) }{\\partial \\theta_j}=\\frac 1{m} \\sum_{i=1}^m \\big[ \\sigma(\\theta.{\\bf x}^{(i)})-y^{(i)} \\big]\\;x_j^{(i)}\n", "$$\n" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "### Decision Boundaries for the iris flower dataset\n", "\n", "![](\"https://s3.amazonaws.com/media-p.slid.es/uploads/633656/images/6079473/iris-machinelearning.png\")
\n"
]
},
{
"cell_type": "code",
"execution_count": 13,
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"outputs": [
{
"data": {
"text/plain": [
"['data', 'target', 'target_names', 'DESCR', 'feature_names', 'filename']"
]
},
"execution_count": 13,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"from sklearn import datasets\n",
"iris = datasets.load_iris()\n",
"list(iris.keys())"
]
},
{
"cell_type": "code",
"execution_count": 14,
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [
{
"data": {
"text/plain": [
"['sepal length (cm)',\n",
" 'sepal width (cm)',\n",
" 'petal length (cm)',\n",
" 'petal width (cm)']"
]
},
"execution_count": 14,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"iris['feature_names']"
]
},
{
"cell_type": "code",
"execution_count": 15,
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"outputs": [
{
"name": "stderr",
"output_type": "stream",
"text": [
"/anaconda3/lib/python3.7/site-packages/sklearn/linear_model/logistic.py:433: FutureWarning: Default solver will be changed to 'lbfgs' in 0.22. Specify a solver to silence this warning.\n",
" FutureWarning)\n"
]
},
{
"ename": "NameError",
"evalue": "name 'save_fig' is not defined",
"output_type": "error",
"traceback": [
"\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
"\u001b[0;31mNameError\u001b[0m Traceback (most recent call last)",
"\u001b[0;32mSoft-max regression
" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "Principle
\n", "\n", "Soft-max regression generalizes logistic regression in order to support $K$ classes. The model estimates a **parameter matrix**\n", "\n", "$$\n", "\\Theta = [\\Theta_1|\\Theta_2\\dots|\\Theta_K]^T\\in {\\mathbb R}^{K \\times (n+1)},\\quad\\quad\n", "\\Theta_k =(\\Theta_{0,k},\\Theta_{1,k},\\dots,\\Theta_{n,k} )^{T}.\n", "$$\n", "\n", "Given $x\\in{\\mathbb R}^n$ and ${\\bf x} = (1,x) \\in {\\mathbb R}^{n+1}$, we compute \n", "$z=\\Theta {\\bf x}~$ ( i.e. $z_j=\\Theta_j. {\\bf x}$ for every $j=1,\\dots,K$), then compute\n", "the $K$ probabilities \n", "\n", "$$\n", "\\hat p_k = \\frac {\\exp({z_k})}{\\displaystyle\\sum_{j=0}^K \\exp({z_j})},\\quad\\quad k=1,\\dots,K.\n", "$$" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ " The class predicted for $x$ is \n",
"the class $k$ with the highest probabilities $ \\hat p_k$.
\n"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"Example: Decision Boundaries for the iris flower dataset
\n", "\n", "
"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"Loss function
\n", "\n", "Given a training set $\\{(x^{(1)},y^{(1)}),\\dots,(x^{(m)},y^{(m)})\\} \\subset \\mathbb R^n \\times \\mathbb \\{1,2,\\dots,K\\}$, the model minimizes a **suitable loss function** in order to find the best parameter matrix $\\Theta^*$. Given $\\{{ x}^{(i)},{ y}^{(i)}\\} $, the associated individual loss is given by \n", "\n", "$$\n", "c^{(i)}(\\Theta)= - \\log (\\hat p_k^{(i)}),\n", "\\quad\\quad \\mbox{if}\\quad\\quad\n", "y^{(i)} = k. \n", "$$\n", "\n", "Intuitively, given $y^{(i)}$ belongs to class $k$\n", "- we want $\\hat p_k^{(i)}$ to be close to $1$ (so that $\\hat p_k^{(i)}$ is the highest probability). \n", "- the closer $\\hat p_k^{(i)}$ is to $0$ (i.e. the more certain that a miss-classification occurs), the larger is the loss (penalization) $c^{(i)}(\\Theta)$.\n", "\n", "Then the loss function for the whole training set is given by \n", "\n", "$$\n", "J(\\Theta)= \\frac 1{m} \\sum_{i=1}^m c^{(i)}(\\Theta)=- \\frac 1{m} \\sum_{i=1}^m \\log (\\hat p_{y(i)}^{(i)}).\n", "$$\n" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "\n", "We will view the function $J$ as a function of $(\\Theta_1,\\Theta_2,\\dots,\\Theta_K)$.
" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "Gradient computation
\n", "\n", "We Let $\\theta = \\Theta_{j} \\in \\mathbb R^{n+1}$ for some $j\\in \\{1,\\dots,K\\}$: We have the following **function dependency diagram** \n", "\n", "$$\n", "\\Theta \\longrightarrow (z^{(i)}_l)_{\\substack{i=1,\\dots,m\\\\l=1,\\dots,K}} \\longrightarrow J.\n", "$$\n", "\n", "Using **chain rule** with respect to the intermediates variables and $\\nabla_{\\theta} z_l = \\delta_{j,l}{\\bf x}$ which follows from $z_l=\\Theta_l. {\\bf x}$, one has \n", "\n", "$$\\nabla_{\\theta} J(\\Theta)=\\sum_{i=1}^m \\sum_{l=1}^K\\frac {\\partial J(\\Theta)}{\\partial z_l^{(i)}}\\nabla_{\\theta} z_l^{(i)}=\\sum_{i=1}^m \\frac {\\partial J(\\Theta)}{\\partial z_j^{(i)}}{\\bf x}^{(i)}$$" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "In view of the formula for $J$\n", "$$\n", " \\frac {\\partial J(\\Theta)}{\\partial z_j^{(i)}}=\n", "-\\frac 1m \\frac {\\partial \\log(\\hat p_k^{(i)})}{\\partial z_j^{(i)}}\n", "$$\n", "\n", "By derivation of usual functions, one has \n", "\n", "$$\\frac {\\partial \\log(\\hat p_k)}{\\partial z_j} =\\frac 1{\\hat p_k} \\frac {\\partial \\hat p_k}{\\partial z_j}\n", "=\n", "\\frac 1{\\hat p_k}\n", "\\left\\{\n", "\\begin{array}{ll}\n", "\\hat p_k - (\\hat p_k)^2&\\quad \\mbox{if}\\quad j=k \n", "\\\\\n", "- \\hat p_k \\hat p_j &\\quad \\mbox{if}\\quad j\\neq k\n", "\\end{array}\n", "\\right.\n", "=\n", "\\left\\{\n", "\\begin{array}{ll}\n", "1 - \\hat p_k&\\quad \\mbox{if}\\quad j=k \n", "\\\\\n", "- \\hat p_j &\\quad \\mbox{if}\\quad j\\neq k\n", "\\end{array}\n", "\\right.\n", "$$ \n", "\n", "The combination of the previous formulas implies\n", "\n", "$$\n", "\\nabla_{\\theta} J(\\Theta) = - \\frac 1m \\sum_{i=1}^m ({\\mathbb 1}_{y^{(i)}=j} - \\hat p_j^{(i)}) {\\bf x}^{(i)}\n", "\\quad\\quad\\quad\\quad\n", "\\nabla_{\\theta} J(\\Theta)\n", "\\in {\\mathbb R}^{n+1}\n", "$$\n", "\n", "" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "The function $J$ as a function of $(\\Theta_1,\\Theta_2,\\dots,\\Theta_K)$ satisfies\n", "\n", "$$\n", "\\nabla_{\\Theta_j} J(\\Theta) = - \\frac 1m \\sum_{i=1}^m ({\\mathbb 1}_{y^{(i)}=j} - \\hat p_j^{(i)}) {\\bf x}^{(i)}.\n", "$$\n", "\n", "Finally \n", "\n", "$$\n", "\\nabla_{\\Theta} J(\\Theta) = [\\nabla_{\\Theta_1} J(\\Theta) |\\nabla_{\\Theta_2} J(\\Theta) |\\dots|\\nabla_{\\Theta_k} J(\\Theta) ]^T\\in {\\mathbb R}^{K \\times (n+1)}.\n", "$$\n", "\n", "- Batch gradient descent;\n", "- stochastic gradient descent;\n", "- mini-Batch stochastic gradient descent;\n", "\n", "can all be implemented." ] }, { "cell_type": "code", "execution_count": 17, "metadata": { "slideshow": { "slide_type": "subslide" } }, "outputs": [ { "ename": "NameError", "evalue": "name 'save_fig' is not defined", "output_type": "error", "traceback": [ "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m", "\u001b[0;31mNameError\u001b[0m Traceback (most recent call last)", "\u001b[0;32mSummary
\n", "\n", "\n", "How do we **learn** the \"best\" weights vector $(\\theta_0^*,\\dots,\\theta_n^*)$ or matrix $(\\Theta_0^*|\\dots|\\Theta_n^*)$ in linear/logistic/soft-max regression\n", "\n", "
\n", "\n", "\n", "
\n",
" Gradient Descent Algorithms\n",
"![](\"https://s3.amazonaws.com/media-p.slid.es/uploads/655061/images/3516655/sgd_contour.gif\"/)
\n",
"
\n"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"\n",
"- \n",
"
- \n", " Give weights random initial values\n", " \n", "
- \n", " Evaluate partial derivative of each weight with respect to MSE or negative log-likelihood at current weight value\n", " \n", "
- \n", " Take a step in direction opposite to the gradient \n", " \n", "
- \n", " Rinse and repeat\n", " \n", "
\n", "
\n", "
\n", "
\n", "
\n", "Essence of the entire learning process behind deep learning algorithms\n", "
" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "
Neural network and backpropagation
" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "\n", " MULTILAYER PERCEPTRONS (MLPs)\n", "
\n", "![](\"https://s3.amazonaws.com/media-p.slid.es/uploads/655061/images/3516930/neural_net2.jpg\"/)
\n",
"\n",
"- \n",
"
- \n", " Most generic form of a neural net is the \"multilayer perceptron\"\n", " \n", "
- \n", " Input undergoes a series of nonlinear transformation \n", " \n", "
- \n", " A final classification layer\n", " \n", "
- \n",
"
- \n", " MLPs are easy entry to understand deep learning models\n", " \n", "
- \n", " Closely related to logistic regression\n", " \n", "
Principle
\n", "\n", "We consider classification problem for **iris dataset** using neural network with one **hidden layer** (5 nodes) \n", "and **activation function** $\\varphi$ (sigmoid, relu, etc)\n", "\n", "\n", "
\n",
"
\n",
"\n",
"- Input layer $$x=(x_1,x_2,x_3,x_4)^T.$$\n",
"\n",
"- Hidden layer \n",
"$$h = (h_1,h_2,h_3, h_4,h_5)^T.$$\n",
"\n",
"- Output layer \n",
"$$z = ( z_1, z_2, z_3)^T.$$\n",
"\n",
"With bias in input and hidden layer $x_0 = 1, h_0=1$, we denote\n",
"\n",
"$$\n",
"{\\bf x} = (1,x^T)^T,\\quad\\quad\\quad\n",
"{\\bf h} = (1,h^T)^T\n",
"$$\n",
"\n",
"\n",
"
"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"\n",
"\n",
"- Input layer $$x=(x_1,x_2,x_3,x_4)^T.$$\n",
"\n",
"- Hidden layer \n",
"$$h = (h_1,h_2,h_3, h_4,h_5)^T.$$\n",
"\n",
"- Output layer \n",
"$$z = ( z_1, z_2, z_3)^T.$$\n",
"\n",
"With bias in input and hidden layer $x_0 = 1, h_0=1$, we denote\n",
"\n",
"$$\n",
"{\\bf x} = (1,x^T)^T,\\quad\\quad\\quad\n",
"{\\bf h} = (1,h^T)^T\n",
"$$\n",
"\n",
"\n",
"
\n"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"Loss function
\n", "\n", "Given a training set $\\{(x^{(1)},y^{(1)}),\\dots,(x^{(m)},y^{(m)})\\} \\subset \\mathbb R^n \\times \\mathbb \\{1,2,\\dots,K\\}$ ($n=4$ and $K=3$ for iris dataset), the model minimizes the **negative log-likelihood** as for Soft-Max\n", "regression in order to find the best parameter matrices $\\widetilde\\Theta^*$ and $\\Theta^*$. \n", "The loss function for the whole training set is given by \n", "\n", "$$\n", "J(\\widetilde\\Theta,\\Theta) = \n", "- \\frac 1{m} \\sum_{{i=1}}^m \\log (\\hat p_k^{(i)}),\\quad\\quad\\quad (k \\mbox{ is such that } y^{(i)} \\mbox{ belongs to class } k)\n", "$$\n", "\n", "\n", "If $n_h$ is the number of nodes in the hidden layer (here $n_h=5$), we write\n", "\n", "$$\n", "\\widetilde\\Theta = [\\widetilde\\Theta_1|\\widetilde\\Theta_2\\dots|\\widetilde\\Theta_{n_h}]^T\\in {\\mathbb R}^{n_h \\times (n+1)},\\quad\\quad\n", "\\Theta = [\\Theta_1|\\Theta_2\\dots|\\Theta_K]^T\\in {\\mathbb R}^{K \\times (n_h+1)},\\quad\\quad\n", "$$" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "We will view the function $J$ as a function of $(\\widetilde\\Theta_1,\\widetilde\\Theta_2,\\dots,\\widetilde\\Theta_{n_h},\\Theta_1,\\Theta_2,\\dots,\\Theta_K)$.
" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "\n", " But how do we compute gradients, with respect to the $\\Theta_j$ and $\\widetilde\\Theta_j$\n", "
\n", "\n", "We recall the **mapping diagram** \n", "\n", "$$\n", "{\\bf x} \\quad\\Longrightarrow\\quad h^{-} = \\widetilde \\Theta {\\bf x} \\quad\\Longrightarrow\\quad h = \\varphi(h^{-}) \\quad\\Longrightarrow\\quad z=\\Theta {\\bf h} \n", "$$\n", " \n", "and the **function dependency diagram** \n", "\n", "$$\n", "(\\widetilde \\Theta, \\Theta) \\longrightarrow ({h^{-}_j}^{(i)})_{\\substack{i=1,\\dots,m\\\\j=1,\\dots,n_h}} \\longrightarrow ({h_j}^{(i)})_{\\substack{i=1,\\dots,m\\\\j=1,\\dots,n_h}} \\longrightarrow (z^{(i)}_l)_{\\substack{i=1,\\dots,m\\\\l=1,\\dots,K}} \\longrightarrow J.\n", "$$" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "- For $j=1,\\dots,K$, we proceed as in soft-max regression (but with $h$ as input)\n", "$$\\nabla_{\\Theta_j} J =\\sum_{i=1}^m \\frac {\\partial J}{\\partial z_j^{(i)}}{\\bf h}^{(i)} = - \\frac 1m \\sum_{i=1}^m ({\\mathbb 1}_{y^{(i)}=j} - \\hat p_j^{(i)}) {\\bf h}^{(i)}.\n", "$$\n", "Observe dependance on $\\widetilde\\Theta$ through the ${\\bf h}^{(i)}$ then on $\\Theta$ through the $\\hat p_k^{(i)}$.\n", "\n", "\n" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "- For $j = 1,\\dots,n_h$ and $\\tilde\\theta = \\widetilde\\Theta_{j}$, we proceed as in soft-max regression: **chain rule** with variables $({h_j^{-}}^{(i)})_{\\substack{i=1,\\dots,m\\\\j=1,\\dots,n_h}}$ and $h^{-} = \\widetilde \\Theta {\\bf x}$ implies \n", "$$\\nabla_{\\tilde\\theta} J= \\sum_{i=1}^m \\sum_{l=0}^{n_h}\\frac {\\partial J}{\\partial {h_l^{-}}^{(i)}} \\nabla_{\\tilde\\theta} {h_l^{-}}^{(i)}= \\sum_{i=1}^m \\frac {\\partial J}{\\partial {h_j^{-}}^{(i)}} {\\bf x}^{(i)}.\n", "$$\n", "Then $\\frac {\\partial J}{\\partial {h_j^{-}}^{(i)}} =\\frac {\\partial J}{\\partial h_j^{(i)}} \\sigma'({h_j^{-}}^{(i)})$ and\n", "$$\n", "\\frac {\\partial J}{\\partial h_j^{(i)}} \n", "= \\sum_{l=1}^K \\frac {\\partial J}{\\partial z_l^{(i)}} \\frac {\\partial z_l^{(i)}}{\\partial h_j^{(i)}}\n", "= \\sum_{l=1}^K \\frac {\\partial J}{\\partial z_l^{(i)}} \\Theta_{j,l}.\n", "$$" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "The gradients $\\nabla_{\\Theta} J$ and $\\nabla_{\\widetilde\\Theta} J$ are completely determined knowing \n", " $$\n", " {\\partial J}/{\\partial z_j^{(i)}} \\quad\\quad i=1,\\dots,m,\\quad j=1,\\dots k \\\\\n", " {\\partial J}/{\\partial h_j^{(i)}} \\quad\\quad i=1,\\dots,m,\\quad j=1,\\dots n_h\n", " $$\n", "
\n", "\n", "- Batch gradient descent;\n", "- stochastic gradient descent;\n", "- mini-Batch stochastic gradient descent;\n", "\n", "can all be implemented." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "## Backpropagation##\n", "
\n",
"\n"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
""
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"\n",
"\n"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"source": [
"$$\n",
"J(\\theta)=-\\frac{1}{m} \\sum_{i=1}^{m}\\left[y^{(i)} \\log \\left(h_{\\theta}\\left(x^{(i)}\\right)\\right)+\\left(1-y^{(i)}\\right) \\log \\left(1-h_{\\theta}\\left(x^{(i)}\\right)\\right)\\right]+\\frac{\\lambda}{2 m} \\sum_{j=1}^{n} \\theta_{j}^{2}\n",
"$$\n",
"\n",
"$$\n",
"J(\\Theta)=-\\frac{1}{m} \\sum_{i=1}^{m} \\sum_{k=1}^{K}\\left[y_{k}^{(i)} \\log \\left(\\left(h_{\\Theta}\\left(x^{(i)}\\right)\\right)_{k}\\right)+\\left(1-y_{k}^{(i)}\\right) \\log \\left(1-\\left(h_{\\Theta}\\left(x^{(i)}\\right)\\right)_{k}\\right)\\right]+\\frac{\\lambda}{2 m} \\sum_{l=1}^{L-1} \\sum_{i=1}^{s_{l}} \\sum_{j=1}^{s t+1}\\left(\\Theta_{j, i}^{(l)}\\right)^{2}\n",
"$$\n",
"\n",
"Training a Neural Network\n",
"\n",
"- Randomly initialize the weights\n",
"- Implement forward propagation to get $hΘ(x(i))$ for any $x^{(i)}x$ \n",
"- Implement the cost function\n",
"- Implement backpropagation to compute partial derivatives\n",
"- Use gradient checking to confirm that your backpropagation works. Then disable gradient checking.\n",
"- Use gradient descent or a built-in optimization function to minimize the cost function with the weights in theta."
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"