{ "metadata": { "name": "" }, "nbformat": 3, "nbformat_minor": 0, "worksheets": [ { "cells": [ { "cell_type": "code", "collapsed": false, "input": [ "%autosave 10" ], "language": "python", "metadata": {}, "outputs": [ { "javascript": [ "IPython.notebook.set_autosave_interval(10000)" ], "metadata": {}, "output_type": "display_data" }, { "output_type": "stream", "stream": "stdout", "text": [ "Autosaving every 10 seconds\n" ] } ], "prompt_number": 1 }, { "cell_type": "markdown", "metadata": {}, "source": [ "## To be clear\n", "\n", "- Not making programs faster.\n", "- Not making websites smaller.\n", "- `scipy.optimize`: mathematical optimisation, reducing functions, etc.\n", "\n", "##\u00a0What is it\n", "\n", "- You have an objective function `f(x)`. Or multiple variables.\n", "- Given some constraints find big or small value.\n", "\n", "## Applications\n", "\n", "- You have data, and have a numeric way of saying how good something is.\n", "\n", "##\u00a0Why Python?\n", "\n", "- End-to-end nature is great.\n", "- Exploration/viz: IPython, matplotlib\n", "- Batteries included: `scipy.optimize`, `statsmodels`.\n", "- Cython, C bindings, glue to other high performance methods.\n", "\n", "## No structure\n", "\n", "If data is random, using `np.argmin(f)` (brute force) is the best you can do because there is no structure.\n", "\n", "## Complete structured\n", "\n", "Completely linear, or quadratic, functions are easy to solve without numeric methods, let alone brute force, because the structure allows us to do it analytically.\n", "\n", "## Real problems\n", "\n", "Tend to be semi-structured, and often can't be expressed symbolically. Maybe there isn't even a symbolic representation.\n", "\n", "## scipy.optimize\n", "\n", " f = lambda x: np.exp((x-4)**2)\n", " return scipy.optimize.minimize(f, 5)\n", " \n", "But this is extremely customisable, lots of methods. Each with strengths and weaknesses. Default is BFGS. Just change a 'method' keyword in `scipy.optimize.minimize`.\n", "\n", "How to choose solver?\n", "\n", "- If you have a small problem, choose anything (but check the answer!). Why waste time?\n", "- Big problem or top speed: you need to understand your problem; is it convex? is it linear? Is there a specialised algorithm that has a smaller big-O complexity?\n", "- Actual big data - none of this will work.\n", " - Try online methods like SGD\n", "- If you don't understand your problem?\n", " - Genetic algorithms.\n", "\n", "Characteristics of each method\n", "\n", "- Needs derivatives?\n", "- Needs constraints?\n", "\n", "Check error messages! Might say it isn't sure about solution.\n", "\n", "## How do problems vary?\n", "\n", "- **Size**: few to many dimensions\n", "- **Smoothness**: smooth, or e.g. unit step discontinuities\n", "- **Global shape**: many local minima? strictly convex?\n", "\n", "##\u00a0Nelder-Mead\n", "\n", "- No derivatives needed\n", "- No constraints needed\n", "- Few assumptions.\n", "\n", "##\u00a0Simulated annealing\n", "\n", "- No derivatives needed, no constraints needed, few assumptions.\n", "- Expects multiple minima\n", "- Jumps all over, inefficient, but trying hard to find global minima.\n", "- Varies temperature: as search continues jumps around less and less, so focuses on minima in smaller neighbourhood.\n", "\n", "## Newton's Method\n", "\n", "- Needs derivative.\n", "- Uses gradient at current point to jump to new point.\n", "- Fast.\n", "\n", "##\u00a0Linear programs and PuLP\n", "\n", "- http://pythonhosted.org/PuLP" ] }, { "cell_type": "code", "collapsed": false, "input": [ "from pulp import *\n", "\n", "x = LpVariable('x', -10, 10)\n", "y = LpVariable('y', -10, 10)\n", "prob = LpProblem(\"Toy problem\", LpMinimize)\n", "prob += 3*x - y\n", "prob.solve()" ], "language": "python", "metadata": {}, "outputs": [ { "metadata": {}, "output_type": "pyout", "prompt_number": 2, "text": [ "1" ] } ], "prompt_number": 2 }, { "cell_type": "code", "collapsed": false, "input": [ "prob" ], "language": "python", "metadata": {}, "outputs": [ { "metadata": {}, "output_type": "pyout", "prompt_number": 3, "text": [ "Toy problem:\n", "MINIMIZE\n", "3*x + -1*y + 0\n", "VARIABLES\n", "-10 <= x <= 10 Continuous\n", "-10 <= y <= 10 Continuous\n" ] } ], "prompt_number": 3 }, { "cell_type": "code", "collapsed": false, "input": [ "(x.value(), y.value())" ], "language": "python", "metadata": {}, "outputs": [ { "metadata": {}, "output_type": "pyout", "prompt_number": 4, "text": [ "(-10.0, 10.0)" ] } ], "prompt_number": 4 }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Sudoku example from the PuLP docs\n", "\n", "- Binary variable for each possible number in each box.\n", "- Then solve within constraints.\n", "\n", "##\u00a0cvxpy\n", "\n", "- For problems which aren't linear.\n", "- Backed by CVXOPT\n", "- Example code for LASSO $L_1$-penalized least squares problem: minimize sum of square errors whilst minimizing the sum of the coefficients.\n", "\n", "## Feynman solution - just solve it\n", "\n", "- Analytic solution after thinking hard.\n", "- Minimzing $x^2$ seems to have a connection to derivative.\n", "- So find point with gradient = 0.\n", "\n", "##\u00a0But what if getting derivative is impossible?\n", "\n", "- `numdifftools`: numerical approximation. scipy.optimize has some methods.\n", "- Automatic derivative methods, not really in Python, Julia, Stan, ADMB\n", " - Track numerical derivatives to derive analytic solution." ] }, { "cell_type": "code", "collapsed": false, "input": [ "import sympy as S\n", "from math import *\n", "S.var(\"x mu sigma\", real=True)" ], "language": "python", "metadata": {}, "outputs": [ { "metadata": {}, "output_type": "pyout", "prompt_number": 7, "text": [ "(x, mu, sigma)" ] } ], "prompt_number": 7 }, { "cell_type": "code", "collapsed": false, "input": [ "f = 1/(sqrt(2*S.pi)*sigma)*S.exp(-(x-mu)**2/(2*sigma**2))\n", "f" ], "language": "python", "metadata": {}, "outputs": [ { "metadata": {}, "output_type": "pyout", "prompt_number": 8, "text": [ "0.398942280401433*exp(-(-mu + x)**2/(2*sigma**2))/sigma" ] } ], "prompt_number": 8 }, { "cell_type": "code", "collapsed": false, "input": [ "ll = log(f)" ], "language": "python", "metadata": {}, "outputs": [ { "ename": "TypeError", "evalue": "can't convert expression to float", "output_type": "pyerr", "traceback": [ "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m\n\u001b[0;31mTypeError\u001b[0m Traceback (most recent call last)", "\u001b[0;32m\u001b[0m in \u001b[0;36m\u001b[0;34m()\u001b[0m\n\u001b[0;32m----> 1\u001b[0;31m \u001b[0mll\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mlog\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mf\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m", "\u001b[0;32m/Users/ai/Programming/.envs/default/lib/python2.7/site-packages/sympy/core/expr.pyc\u001b[0m in \u001b[0;36m__float__\u001b[0;34m(self)\u001b[0m\n\u001b[1;32m 205\u001b[0m \u001b[0;32mif\u001b[0m \u001b[0mresult\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mis_number\u001b[0m \u001b[0;32mand\u001b[0m \u001b[0mresult\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mas_real_imag\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;36m1\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 206\u001b[0m \u001b[0;32mraise\u001b[0m \u001b[0mTypeError\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m\"can't convert complex to float\"\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m--> 207\u001b[0;31m \u001b[0;32mraise\u001b[0m \u001b[0mTypeError\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m\"can't convert expression to float\"\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m 208\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 209\u001b[0m \u001b[0;32mdef\u001b[0m \u001b[0m__complex__\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mself\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n", "\u001b[0;31mTypeError\u001b[0m: can't convert expression to float" ] } ], "prompt_number": 9 }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Questions\n", "\n", "- How to investigate a big problem?\n", " - Plug it into `cvxpy` and ask it if it's convex\n", " - If just a black box of data, plot it, but only works for low dimensions.\n", " - There are convex optimization methods." ] }, { "cell_type": "code", "collapsed": false, "input": [], "language": "python", "metadata": {}, "outputs": [] } ], "metadata": {} } ] }