{ "cells": [ { "cell_type": "markdown", "metadata": { "deletable": true, "editable": true }, "source": [ "# Linear Algebra and Optimisation" ] }, { "cell_type": "markdown", "metadata": { "deletable": true, "editable": true }, "source": [ "###### COMP4670/8600 - Introduction to Statistical Machine Learning - Tutorial 1B" ] }, { "cell_type": "markdown", "metadata": { "deletable": true, "editable": true }, "source": [ "$\\newcommand{\\trace}[1]{\\operatorname{tr}\\left\\{#1\\right\\}}$\n", "$\\newcommand{\\Norm}[1]{\\lVert#1\\rVert}$\n", "$\\newcommand{\\RR}{\\mathbb{R}}$\n", "$\\newcommand{\\inner}[2]{\\langle #1, #2 \\rangle}$\n", "$\\newcommand{\\DD}{\\mathscr{D}}$\n", "$\\newcommand{\\grad}[1]{\\operatorname{grad}#1}$\n", "$\\DeclareMathOperator*{\\argmin}{arg\\,min}$\n", "\n", "Setting up python environment ([do not use pylab](http://carreau.github.io/posts/10-No-PyLab-Thanks.ipynb.html))" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": false, "deletable": true, "editable": true }, "outputs": [], "source": [ "import matplotlib.pyplot as plt\n", "import numpy as np\n", "import scipy as sp\n", "import scipy.optimize as opt\n", "import time\n", "\n", "%matplotlib inline" ] }, { "cell_type": "markdown", "metadata": { "deletable": true, "editable": true }, "source": [ "Consider the following cost function $f(X)$ defined\n", "over the space of real $n \\times p$ matrices\n", "\$$\n", " f(X) = \\frac{1}{2} \\trace{X^T C X N} + \\mu \\frac{1}{4} \\Norm{N - X^T X}^2_F\n", "\$$\n", "where $X \\in \\RR^{n \\times p}$, $n \\ge p$, and the matrix $C$ is symmetric, \n", "such that $C = C^T$. The scalar $\\mu$ is assumed to be larger than the $p$th smallest \n", "eigenvalue of $C$. The matrix $N$ is diagonal with distinct positive entries\n", "on the diagonal.\n", "The trace of a square matrix $A$ is denoted as $\\trace{A}$, and\n", "the Frobenius norm of an arbitrary matrix $A$ is defined as $\\Norm{A}_F = \\sqrt{\\trace{A^T A}}$.\n", "\n" ] }, { "cell_type": "markdown", "metadata": { "deletable": true, "editable": true }, "source": [ "## Frobenious Norm\n", "\n", "Implement a Python function frobenius_norm which accepts an arbitrary matrix $A$ and returns\n", "$\\Norm{A}_F$ using the formula given. (Use numpy.trace and numpy.sqrt.)\n", "1. Given a matrix $A \\in \\RR^{n \\times p}$, what is the complexity of your implementation of frobenius_norm\n", "using the formula above?\n", "2. Can you come up with a faster implementation, if you were additionally told that $p \\ge n$ ?\n", "3. Can you find an even faster implementation than in 1. and 2.? " ] }, { "cell_type": "markdown", "metadata": { "deletable": true, "editable": true }, "source": [ "### Solution description" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": false, "deletable": true, "editable": true }, "outputs": [], "source": [ "# Solution goes here" ] }, { "cell_type": "markdown", "metadata": { "deletable": true, "editable": true }, "source": [ "## Cost Function $f(X)$ with matrix argument\n", "\n", "Implement the cost function defined as $f(X)$ above as a function cost_function_for_matrix\n", "in Python.\n", "\n", "Hint: As good programmers, we do not use global variables in subroutines.\n" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": false, "deletable": true, "editable": true }, "outputs": [], "source": [ "# Solution goes here" ] }, { "cell_type": "markdown", "metadata": { "deletable": true, "editable": true }, "source": [ "## Cost Function $f(X)$ with vector argument\n", "\n", "Many standard optimisation routines work only with vectors. Fortunately, as vector spaces,\n", "the space of matrices $\\RR^{n \\times p}$ \n", "and the space of vectors $\\RR^{n p}$ are isomorphic. What does this mean?\n", "\n", "Implement the cost function $f(X)$ given $X$ as a vector and call it cost_function_for_vector.\n", "Which extra arguments do you need for the cost function?\n" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": false, "deletable": true, "editable": true }, "outputs": [], "source": [ "# Solution goes here" ] }, { "cell_type": "markdown", "metadata": { "deletable": true, "editable": true }, "source": [ "## Construction of a random matrix $C$ with given eigenvalues\n", "\n", "A diagonal matrix has the nice property that the eigenvalues can be directly read off\n", "the diagonal. Given a diagonal matrix $C \\in \\RR^{n \\times n}$ with distinct eigenvalues, \n", "how many different diagonal matrices have the same set of eigenvalues?\n", "\n", "Given a diagonal matrix $C \\in \\RR^{n \\times n}$ with distinct eigenvalues,\n", "how many different matrices have the same set of eigenvalues?\n", "\n", "Given a set of $n$ distinct real eigenvalues $\\mathcal{E} = \\{e_1, \\dots, e_n \\}$, \n", "write a Python function random_matrix_from_eigenvalues which takes a list of\n", "eigenvalues $E$ and returns a random symmetric matrix $C$ having the same eigenvalues." ] }, { "cell_type": "markdown", "metadata": { "deletable": true, "editable": true }, "source": [ "### Solution description" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": false, "deletable": true, "editable": true }, "outputs": [], "source": [ "# Solution goes here" ] }, { "cell_type": "markdown", "metadata": { "deletable": true, "editable": true }, "source": [ "## Minimising the cost function $f(X)$\n", "\n", "Use the minimisation functions fmin or fmin_powell provided in the\n", "Python package scipy.optimize to minimise the cost function cost_function_for_vector.\n", "\n", "Hint: Use the argument args in the minimisation functions fmin or fmin_powell \n", "to provide the extra parameters to\n", "your cost function cost_function_for_vector.\n" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": false, "deletable": true, "editable": true }, "outputs": [], "source": [ "# Solution goes here" ] }, { "cell_type": "markdown", "metadata": { "deletable": true, "editable": true }, "source": [ "## Gradient of $f(X)$\n", "\n", "Calculate the gradient for the cost function $f(X)$ given the\n", "inner product on the space of real matrices $n \\times p$ is defined as\n", "\$$\n", " \\inner{A}{B} = \\trace{A^T B}\n", "\$$\n", "\n", "Implement a function gradient_for_vector which takes $X$ as a vector, and\n", "returns the gradient of $f(X)$ as a vector.\n" ] }, { "cell_type": "markdown", "metadata": { "deletable": true, "editable": true }, "source": [ "### Solution description" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": false, "deletable": true, "editable": true }, "outputs": [], "source": [ "# Solution goes here" ] }, { "cell_type": "markdown", "metadata": { "deletable": true, "editable": true }, "source": [ "## Minimising the cost function $f(X)$ using the gradient\n", "\n", "Use the minimisation functions fmin_cg or fmin_bfgs provided in the\n", "Python package scipy.optimize to minimise the cost function cost_function_for_vector utilising the gradient gradient_for_vector.\n", "\n", "Compare the speed of convergence to the minimisation with fmin or fmin_powell.\n" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": false, "deletable": true, "editable": true }, "outputs": [], "source": [ "# Solution goes here" ] }, { "cell_type": "markdown", "metadata": { "deletable": true, "editable": true }, "source": [ "## Minima of $f(X)$\n", "\n", "Compare the columns $x_1,\\dots, x_p$ of the matrix $X^\\star$ which minimises $f(X)$ \n", "\$$\n", " X^\\star = \\argmin_{X \\in \\RR^{n \\times p}} f(X)\n", "\$$\n", "\n", "with the eigenvectors related to the smallest eigenvalues of $C$.\n" ] }, { "cell_type": "markdown", "metadata": { "deletable": true, "editable": true }, "source": [ "### Solution description" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": false, "deletable": true, "editable": true }, "outputs": [], "source": [ "# Solution goes here" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": false, "deletable": true, "editable": true }, "outputs": [], "source": [] } ], "metadata": { "kernelspec": { "display_name": "Python 3", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.5.2" } }, "nbformat": 4, "nbformat_minor": 0 }