{ "metadata": { "name": "" }, "nbformat": 3, "nbformat_minor": 0, "worksheets": [ { "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "View the assignment description [here](http://www.cs.ubc.ca/~nando/540-2013/lectures/homework1.pdf)" ] }, { "cell_type": "heading", "level": 3, "metadata": {}, "source": [ "Exercise 1" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "$\\newcommand{\\vect}[1]{\\boldsymbol{\\mathbf{#1}}}$\n", "The cost function is defined by:\n", "$$J(\\vect x_u) = \\sum _{i=1} ^n c_{ui} \\left( p_{ui} - \\vect x_u \\vect y_i \\right)^2 +\n", "\\lambda \\| \\vect x_u \\| _2 ^2$$\n", "where $\\vect x_u \\in \\mathbb R^{1 \\times f}$ and $\\vect y_i \\in \\mathbb R^{f \\times 1}$." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "The first term can be rewritten as\n", "$$\\sum _{i=1} ^n c_{ui} \\left( \\vect p_u - \\vect x_u \\vect Y \\right)_i \\left( \\vect p_u - \\vect x_u \\vect Y \\right)_i$$\n", "where $\\vect p_u \\in \\mathbb R^{1 \\times n}$ and $\\vect Y \\in \\mathbb R^{f \\times n}$,\n", "so that $\\left( \\vect p_u - \\vect x_u \\vect Y \\right) \\in \\mathbb R^{1 \\times n}$." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Using the definition of the dot product we can then rewrite the first term as\n", "$$\\left( \\vect p_u - \\vect x_u \\vect Y \\right)\n", "\\left[ \\begin{array}{c}\n", "c_{u1}\\left( \\vect p_u - \\vect x_u \\vect Y \\right)_1 \\\\\n", "\\vdots \\\\\n", "c_{un}\\left( \\vect p_u - \\vect x_u \\vect Y \\right)_n \\end{array} \\right]$$" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "And finally by using the definition of matrix multiplication the first term become\n", "$$\\left( \\vect p_u - \\vect x_u \\vect Y \\right)\n", "\\vect C_u\n", "\\left( \\vect p_u - \\vect x_u \\vect Y \\right)^T$$\n", "where $\\vect C_u = \\left[ \\begin{array}{ccc}\n", "c_{u1} & 0 & 0 \\\\\n", "0 & \\ddots & 0 \\\\\n", "0 & 0 & c_{un} \\end{array} \\right]$." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "The second term can be rewritten as\n", "$$\\lambda \\| \\vect x_u \\| _2 ^2 = \\lambda\\sum_{i=1}^n x_{ui}^2 \n", "= \\lambda \\vect x_u \\vect x_u^T$$" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "So we have showed that\n", "$$J(\\vect x_u) =\n", "\\left( \\vect p_u - \\vect x_u \\vect Y \\right)\n", "\\vect C_u\n", "\\left( \\vect p_u - \\vect x_u \\vect Y \\right)^T\n", "+ \\lambda \\vect x_u \\vect x_u^T$$" ] }, { "cell_type": "heading", "level": 3, "metadata": {}, "source": [ "Exercise 2" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "To find $\\hat{\\vect x}_u$ we differentiate $J(\\vect x_u)$ w.r.t. $\\vect x_u$ and set it equal to zero.\n", "$$J(\\vect x_u) = \\vect p_u \\vect C_u \\vect p_u^T - 2\\vect p_u \\vect C_u \\vect Y^T \\vect x_u^T\n", "+ \\vect x_u \\vect Y \\vect C_u \\vect Y^T \\vect x_u^T\n", "+ \\lambda \\vect x_u \\vect x_u^T$$" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "$$\\frac \\partial {\\partial\\vect x_u} J(\\vect x_u) = \n", "-2 \\vect p_u \\vect C_u \\vect Y^T + 2 \\vect x_u \\vect Y \\vect C_u \\vect Y^T \n", "+ 2 \\lambda \\vect x_u = 0$$" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "$$\\hat{\\vect x}_u = \\vect p_u \\vect C_u \\vect Y^T \\left( \\vect Y \\vect C_u \\vect Y^T \n", "+ \\lambda I\\right)^{-1}$$" ] } ], "metadata": {} } ] }