{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"---\n",
"title : Online Convex Optimization with Haskell\n",
"---"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"This page illustrates the basics of Online Convex Optimization(OCO) with\n",
"a Haskell implementation [^source]. More precisely, we will use the Online\n",
"Gradient Descent (OGD) algorithm @zinkevich2003online to build a\n",
"L2-constrained online regressor. In turn, we will apply this regressor\n",
"to the classic [`iris`](https://stat.ethz.ch/R-manual/R-devel/library/datasets/html/iris.html)\n",
"@henderson1981building dataset that ships with the standard R\n",
"distribution. \n",
"\n",
"[^source]: [Here is the source for this page in Jupyter notebook format.](./ogd.ipynb)\n",
"\n",
"This page goes from the generic to the specific. We’ll start with a\n",
"generic, abstract learning algorithm encoded with a polymorphic\n",
"implementation, and finish with experiments.\n",
"\n",
"The Online Convex Programming [^dantzig] @zinkevich2003online framework is \n",
"the following:\n",
"\n",
"[^dantzig]: The terms “Optimization” and “Programming” are interchangeable\n",
"in this context, owing to the military history of Linear Programming in the\n",
"western bloc. \n",
"\n",
"Given a known convex set $F \\subset \\mathbb{R}^n$, at every round\n",
"$t=0,\\ldots$ a learner: \n",
"$\\quad$ Selects an action $w^t \\in F$ \n",
"$\\quad$ Observes a convex loss function\n",
"$c^t : F \\rightarrow \\mathbb{R}^n$ \n",
"$\\quad$ Incurs a loss $c^t(w^t)$\n",
"\n",
"This broad setting may be specialized to various tasks such as regression,\n",
"classification, clustering, ranking, collaborative filtering, structured\n",
"prediction, principal component analysis, and more. The *action* $w$\n",
"can sometimes be thought of as the *parameter* of the model - although\n",
"there will sometimes be a distinction. Let’s take a look at\n",
"the standard algorithm for OCO in the abstract; we’ll choose a modeling\n",
"strategy for $F$ and $c^t$ later.\n",
"\n",
"# Online Gradient Descent\n",
"\n",
"This algorithm is a non-adaptive constrained online gradient descent\n",
"that uses a projection step. More formally, the original OGD algorithm\n",
"works by picking $w^0$ arbitrarily in $F$ and choosing:\n",
"\n",
"$$\n",
"w^{t+1} = P(w^t - \\eta_t \\nabla c^t (w^t))\n",
"$$ {\\#eq:update}\n",
"\n",
"Where $P(w) = \\text{argmin}_{y \\in F} \\left\\| x - y \\right\\|$ is the\n",
"projection operator on $F$.\n",
"\n",
"As long as we can encode a problem by specifying a set $F$ such that we\n",
"can implement a tractable projection operator $P$ and specify a convex\n",
"function $c^t$ such that we can implement its gradient $\\nabla c^t$ at\n",
"as a function of $w^t$, we can use the OGD algorithm. Then, it remains\n",
"to choose a sequence $\\eta_t$ of learning rates [^rate].\n",
" \n",
"[^rate]: The rate $\\eta_t$ is essentially the sole\n",
"hyperparameter of the *algorithm*. Often, some variables involved in the\n",
"*problem* construction (more precisely, in the choice of $F$ or $c^t$)\n",
"may be reffered to as hyperparameters as well.\n",
"\n",
"Let’s start encoding this gradient step in Haskell right away before\n",
"discussing its behavior. We’ll make the non-experimental code as generic\n",
"as reasonably feasible, and the typeclasses from the\n",
"[linear](https://hackage.haskell.org/package/linear) Haskell package\n",
"will help. These typeclasses allow us to use the code from this post\n",
"seamlessly on vectors, association lists or any custom data structure\n",
"that represent vector spaces[^imports].\n",
"\n",
"[^imports]:\n",
" `Linear.Vector`, exports `Additive`, a Typeclass exposing vector \n",
" space operation for various vector-like memory representations.\n",
" `Linear.Metric` exports `Metric`, a typeclass exposing dot products,\n",
" norms and the like."
]
},
{
"cell_type": "code",
"execution_count": 1,
"metadata": {},
"outputs": [],
"source": [
"import Linear.Vector (Additive, (^-^), (^/), (*^), (^*))\n",
"import Linear.Metric (Metric, norm, dot)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Let’s begin by writing out useful type synonyms for the types of\n",
"$\\nabla c^t$, $P$ and $\\eta_t$, respectively naming them\n",
"`LossDerivative`, `Projection` and `LearningRate`. We’ll use those\n",
"throughout the rest of the code."
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {},
"outputs": [],
"source": [
"-- | Derivative of a loss function w.r.t an action.\n",
"type LossDerivative v a =\n",
" v a -> -- ^ action/parameter \n",
" v a -- ^ descent direction and magnitude\n",
"\n",
"-- | Projection operator.\n",
"type Projection v a = \n",
" v a -> -- ^ vector to project\n",
" v a -- ^ projection\n",
"\n",
"-- | Learning rate schedule.\n",
"type LearningRate a = \n",
" Int -> -- ^ Round counter\n",
" a -- ^ Rate value"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"We are now ready to write the actual OGD gradient step. We need a\n",
"datatype to maintain the state of the algorithm: we’ll call it\n",
"`Ogdstate`."
]
},
{
"cell_type": "code",
"execution_count": 3,
"metadata": {},
"outputs": [],
"source": [
"-- | Algorithm state for OGD. Encodes both the round count and the last action.\n",
"data Ogdstate v a = Ogdstate \n",
" { t :: Int -- ^ round counter\n",
" , weights :: v a -- ^ parameter/action weights\n",
" } deriving (Show)\n",
"\n",
"-- | Smart constructor\n",
"initialOGDState :: v a -> Ogdstate v a\n",
"initialOGDState = Ogdstate 1"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The code for the OGD update step in @eq:update is rather simple:"
]
},
{
"cell_type": "code",
"execution_count": 4,
"metadata": {},
"outputs": [],
"source": [
"-- | The OGD algorithm.\n",
"ogd :: (Additive v, Floating a) =>\n",
" LearningRate a -> -- ^ Learning rate schedule\n",
" Projection v a -> -- ^ Projection operator\n",
" Ogdstate v a -> -- ^ Last state/action \n",
" LossDerivative v a -> -- ^ Derivative of the loss at this round\n",
" Ogdstate v a -- ^ New state/action\n",
"ogd rate projection (Ogdstate t w) dc = Ogdstate {\n",
" t = t + 1,\n",
" weights = projection (w ^-^ ( rate t *^ dc w)) \n",
" }"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"We have implemented the `ogd` gradient descent step in its most\n",
"general form. Before moving on with an application to a concrete\n",
"problem, we still have to finish covering the essentials of the original\n",
"OGD paper by discussing the choice of $\\eta_t$.\n",
"\n",
"OGD-based learners work by minimizing their *regret* at round $T$\n",
"against all adversaries in a comparison\n",
"class[^class]. In other words, OGD-based learners achieve good\n",
"performance with respect to the single best action *in hindsight*\n",
"(meaning: observed a-posteriori). The original OGD paper\n",
"\\[@zinkevich2003online\\] defines the\n",
"regret [^regret] as:\n",
"\n",
"[^class]: There are various ways to refer to the “comparator”.\n",
" Some texts use the game-theory influenced term of\n",
" *adversary*, while some others refer to a *comparison class*. This page\n",
" uses the term of *best action in hindsight* or *best parameter in\n",
" hindsight*. \n",
"\n",
"[^regret]: This is what is reffered to as the *external* regret.\n",
"\n",
"$$\n",
"R_F(T) = C_T - C_{\\text{best}}\n",
"$$ {\\#eq:regret}\n",
"\n",
"Where:\n",
"\n",
"$$\n",
"C_T = \\sum_{t=1}^{t=T} c^t (x^t) \\\\\n",
"C_{\\text{best}} = \\min_{w \\in F} \\sum_{t=1}^{t=T} c^t (w)\n",
"$$\n",
"\n",
"If $F$ is bounded, closed, nonempty, and the norm of the gradient of $c$\n",
"is bounded on $F$, the main theorem from the paper gives the following\n",
"regret bound for a static\n",
"adversary [^dynamic]:\n",
"\n",
"[^dynamic]: Using the fixed learning rate\n",
" $\\eta_t = \\eta$, we can minimize a notion of dynamic regret. For this\n",
" specific bound, the comparison class is the set $A(T,L)$ of slowly\n",
" moving actions. This is defined in terms of the path length of a\n",
" sequence, which just sum of the distance of displacement between\n",
" subsequent rounds. The comparison class is the set of sequences of\n",
" actions whose path length is smaller than $L$:\n",
" $$ R_A(T,L) = \\sum_{t=1}^{t=N} c^t (x^t) - \\min_{(w_a)^{t=1 \\ldots T} \\in\n",
" A(T,L)} \\sum_{t=1}^{t=N} c^t (w_a^t) $$ {\\#eq:regretDynamic} The fixed\n",
" learning rate gives us the following bound:\n",
" $$ R_A(T,L) \\leq \\frac{7 \\left\\|F\\right\\|^2 }{4 \\eta} + \\frac{L \\left\\|F\\right\\| }{\\eta} + \\frac{ T\n",
" \\eta \\left\\|\\nabla c \\right\\|^2}{2} $$ {\\#eq:boundDynamic} The\n",
" implementation we’d need for this rate is `const`.\n",
"\n",
"$$\n",
"R_F(T) \\leq \\frac{\\left\\|F\\right\\|^2 }{2 \\eta_T} + \\frac{\\left\\|\\nabla c \\right\\|^2}{2} \\sum_{t=1}^{T} \\eta_t\n",
"$$ {\\#eq:bound:generic}\n",
"\n",
"Where $\\left\\|F\\right\\|$ is the diameter of $F$ and\n",
"$\\left\\|\\nabla c\\right\\|$ is the norm of the maximum value of the\n",
"gradient of $c$ in $F$. Notice the summation: we have to use a rate with\n",
"a convergent series. A simple choice is $\\eta_t= \\frac{1}{\\sqrt{t}}$,\n",
"whose series is easily upper bounded by $2\\sqrt(T)-1$. Replacing the\n",
"summation illustrates the sublinearity of the bound:\n",
"\n",
"$$\n",
"R_F(T) \\leq \\frac{\\left\\|F\\right\\|^2 \\sqrt{T}}{2} + \\left( \\sqrt{T} - \\frac{1}{2} \\right)\n",
"\\left\\|\\nabla c \\right\\|^2\n",
"$$ {\\#eq:bound:static}\n",
"\n",
"Assuming $\\left\\|F\\right\\|$ and $\\left\\|\\nabla c\\right\\|$ to be\n",
"independent of $T$, this bound is essentially the reason why OGD is a\n",
"useful algorithm. Indeed, notice that the average regret $R_F(T)/T$\n",
"vanishes with $T$. In other words, the performance with respect to the\n",
"best action in hindsight is upper-bounded by a quantity that diminishes\n",
"with with every round.\n",
"\n",
"We’ll use the scaled rate $\\eta_t = \\frac{\\eta}{\\sqrt{t}}$, which\n",
"implies a more tunable bound. Its implementation is simple:"
]
},
{
"cell_type": "code",
"execution_count": 5,
"metadata": {},
"outputs": [],
"source": [
"-- | Inverse squared learning rate.\n",
"rootRate :: (Floating a) => a -> LearningRate a\n",
"rootRate eta t = eta / sqrt (fromIntegral t)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"This rate gives rise to a slight modification of @eq:bound:static,\n",
"showcasing the $\\eta$ hyperparameter:\n",
"\n",
"$$\n",
"R_F(T) \\leq \\frac{\\left\\|F\\right\\|^2 \\sqrt{T}}{2\\eta} + \n",
"\\frac{\\eta \\left\\|\\nabla c \\right\\|^2 \\left( 2\\sqrt{T} - 1 \\right) }{2} \n",
"$$ {\\#eq:bound:tuned}\n",
"\n",
"Enough with discussing OGD in the abstract - we will now choose a model.\n",
"\n",
"# Linear Regression\n",
"\n",
"We use a classical task, namely linear regression. The online \n",
"regression set-up is the following:\n",
"\n",
"$\\forall t=0,\\ldots$ the learner: \n",
"$\\quad$ Observes a feature vector $x^t \\in \\mathbb{R}^n$ \n",
"$\\quad$ Selects a prediction $\\widehat{y^t} \\in \\mathbb{R}$ \n",
"$\\quad$ Observes the regression target $y^t \\in \\mathbb{R}$ \n",
"$\\quad$ Incurs a loss $l(\\widehat{y^t},y^t)$ convex in both its\n",
"arguments.\n",
"\n",
"We can already write a type for the derivative of that loss function\n",
"$l$:"
]
},
{
"cell_type": "code",
"execution_count": 6,
"metadata": {},
"outputs": [],
"source": [
"-- | Differential of a regression loss\n",
"type RegressionLossDerivative v a =\n",
" v a -> -- ^ x^t\n",
" a -> -- ^ y^t\n",
" LossDerivative v a -- ^ c^t"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"We can also immediately provide a more regression-friendly wrapper for the previously implemented `ogd` interface:"
]
},
{
"cell_type": "code",
"execution_count": 7,
"metadata": {},
"outputs": [],
"source": [
"-- | Regression fit call\n",
"type FitReg v a =\n",
" v a -> -- ^ Feature vector x^t\n",
" a -> -- ^ Regression target y^t\n",
" Ogdstate v a -> -- ^ Old learner state\n",
" Ogdstate v a \n",
"\n",
"-- | Generates a fitter for one regression data point using OGD.\n",
"fitOGDReg :: (Additive v, Floating a) =>\n",
" LearningRate a -> -- ^ Learning rate\n",
" Projection v a -> -- ^ Projection operator\n",
" RegressionLossDerivative v a -> -- ^ Regression loss derivative\n",
" FitReg v a -- ^ Fitting function\n",
"fitOGDReg rate projection differential x y state =\n",
" ogd rate projection state $ differential x y"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"This code clearly shows that this online regression set-up is just disguised OCO.\n",
"It's still rather polymorphic though, and we still need to construct some\n",
"parameters for this `fitOGDReg` function.\n",
"\n",
"### Linear predictor and Gaussian losses, a.k.a picking $c^t$\n",
"\n",
"We make the classical restrictive design choices on the learner. First,\n",
"we choose a constrained linear model, with a parameter vector in a set\n",
"$F \\subset \\mathbb{R}^n$. Second, we commit to choose $w^t$ before\n",
"observing $x^t$. Under those restictions, our online regression\n",
"framework is:\n",
"\n",
"$\\forall t=0,\\ldots$ the learner \n",
"$\\quad$ Selects an action $w^t \\in F$ \n",
"$\\quad$ Observes a feature vector $x^t \\in \\mathbb{R}^n$ \n",
"$\\quad$ Predicts $\\widehat{y^t} = {w^{t}}^T x$ \n",
"$\\quad$ Observes regression target $y^t \\in \\mathbb{R}$ \n",
"$\\quad$ Incurs loss $c^t(w^t) = l( {w^{t}}^T x,y^t)$\n",
"\n",
"First, we implement our linear predictor $\\widehat{y^t} = {w^{t}}^T x$,\n",
"which gives rise to the `predictReg` prediction function:"
]
},
{
"cell_type": "code",
"execution_count": 8,
"metadata": {},
"outputs": [],
"source": [
"-- | Prediction function\n",
"predictReg :: (Metric v, Floating a) =>\n",
" v a -> -- ^ Feature vector\n",
" Ogdstate v a -> -- ^ Learner\n",
" a -- ^ Prediction\n",
"predictReg x (Ogdstate _ w) = w `dot` x"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Second, we pick the convex loss we’re interested in to be the “Gaussian”\n",
"square loss function.\n",
"\n",
"$$\n",
"c^t(w) = \\left\\| y^t - w^{T} x^t \\right\\|^2 \\quad y \\in \\mathbb{R}, x \\in \\mathbb{R}^n \\\\\n",
"$$\n",
"\n",
"In practice, OGD only needs the gradient of that function. Because we’re\n",
"using a linear predictor, that is simply:\n",
"\n",
"$$\n",
"\\nabla c^t (w) = x^t \\left( w^T x^t - y^t \\right) \\\\\n",
"$$"
]
},
{
"cell_type": "code",
"execution_count": 9,
"metadata": {},
"outputs": [],
"source": [
"-- | Derivative of the square loss function.\n",
"mseDiff :: (Metric v, Floating a) => RegressionLossDerivative v a\n",
"mseDiff x y w = x ^* ( w `dot` x - y)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"That’s it, we now have an interface for for feeding an instance to a\n",
"regression model (`FitReg v x`) and for predicting a value\n",
"(`predictReg`).\n",
"\n",
"### The ridge constraint, a.k.a picking $F$\n",
"\n",
"We’ll consider the $\\ell_2$ ball of radius $\\lambda$ as a constraint set\n",
"[^l].\n",
"\n",
"[^l]: We’re not really going to reap the\n",
" systematic benefits of this $\\ell_2$ ball (which mostly [come about with\n",
" a large number of\n",
" features](https://en.wikipedia.org/wiki/Tikhonov_regularization)) in our\n",
" experiments. An appropriately chosen L2 norm will be helpful to control\n",
" initial gradient jumps, however.\n",
"\n",
"$$\n",
"F = \\left\\{ x \\in \\mathbb{R} \\; \\middle| \\; \\left\\|x\\right\\| \\leq \\lambda \\right\\}\n",
"$$\n",
"\n",
"This choice of $F$ is a breeze to implement. The $\\ell_2$ projection is\n",
"straightforward:\n",
"\n",
"$$\n",
"P(w) = \\begin{cases}\n",
"w & \\text{if}\\ \\left\\|w\\right\\| \\leq \\lambda \\\\\n",
"\\lambda \\frac{w}{\\left\\|w\\right\\|} & \\text{otherwise}\n",
"\\end{cases}\n",
"$$"
]
},
{
"cell_type": "code",
"execution_count": 10,
"metadata": {},
"outputs": [],
"source": [
"-- | Argument name for Lambda.\n",
"newtype Lambda a = Lambda a deriving (Show)\n",
"\n",
"-- | Projection on a L2 Ball.\n",
"l2Projection :: (Metric v, Ord a, Floating a) =>\n",
" Lambda a -> -- ^ radius\n",
" Projection v a -- ^ projection operator\n",
"l2Projection (Lambda lam) w \n",
" | q <= lam = w\n",
" | otherwise = lam *^ w ^/ q\n",
" where q = norm w"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Now that we have all the necessary ingredients, we can write\n",
"`fitOGDReg`, an interface wrapper that helps build an online ridge\n",
"regressor."
]
},
{
"cell_type": "code",
"execution_count": 11,
"metadata": {},
"outputs": [],
"source": [
"-- | Online ridge regressor via OGD.\n",
"fitRidge :: (Metric v, Ord a, Floating a) =>\n",
" LearningRate a -> -- ^ Rate schedule\n",
" Lambda a -> -- ^ Constraint set radius\n",
" FitReg v a\n",
"fitRidge rate lambda = fitOGDReg rate (l2Projection lambda) mseDiff"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Let’s conclude on the modeling part by using everything we know to make\n",
"@eq:bound:tuned more concrete. The diameter of $F$ depends on our choice\n",
"of $\\lambda$ (namely $\\left\\|F\\right\\|=2\\lambda$) and the magnitude of\n",
"$\\left\\|\\nabla c\\right\\|$ depends on the regression data:\n",
"\n",
"$$\n",
"\\left\\|\\nabla c\\right\\| = \\max_{w \\in F,t} \\left\\|x^t \\left( w^T x^t - y^t \\right)\\right\\|\\\\ \n",
"\\quad \\leq \\left\\|x\\right\\| \\left(\\lambda \\left\\|x\\right\\| + \\left\\|y\\right\\| \\right)\n",
"$$\n",
"\n",
"where $\\left\\|x\\right\\| = \\max_t \\left\\|x^t\\right\\|$ and\n",
"$\\left\\|y\\right\\| = \\max_t \\left\\|y^t\\right\\|$ are data-dependent\n",
"quantities. Substituting, we have the following data-dependent regret\n",
"bound for this regression task:\n",
"\n",
"$$\n",
"R_F(T) \\leq \\frac{2 \\lambda^2 \\sqrt{T}}{\\eta} + \n",
"\\frac{\n",
" \\eta \\left( 2\\sqrt{T} - 1 \\right) (\\lambda \\left\\|x\\right\\|^2 +\n",
" \\left\\|x\\right\\|\\left\\|y\\right\\| )^2\n",
"}{2} \n",
"$$ {\\#eq:bound:tunedRidge}\n",
"\n",
"\n",
"The learner is now fully implemented. Next, we use this learner with a toy dataset.\n",
"\n",
"# Experiments with `iris`\n",
"The rest of the code snippets need some extra extensions and imports."
]
},
{
"cell_type": "code",
"execution_count": 12,
"metadata": {},
"outputs": [],
"source": [
"{-# LANGUAGE QuasiQuotes DataKinds TypeApplications LambdaCase #-}\n",
"{-# LANGUAGE DeriveGeneric OverloadedStrings OverloadedLabels #-}\n",
"{-# LANGUAGE ScopedTypeVariables NoImplicitPrelude ViewPatterns #-}\n",
"{-# LANGUAGE ParallelListComp RecordWildCards #-}\n",
"\n",
"import Protolude\n",
"import Linear.Metric\n",
"import Data.Sequence.Lens\n",
"import Control.Monad.Primitive\n",
"import Control.Lens hiding ((:>))\n",
"import Data.Sequence hiding (replicate,length)\n",
"import System.Random\n",
"import Data.Coerce\n",
"import Data.Generics.Labels ()\n",
"import System.Random.Shuffle\n",
"import System.Command.QQ.Predef\n",
"import System.Command.QQ\n",
"import System.Command.QQ.Eval\n",
"import Data.Text.Internal.Lazy as LT\n",
"import Graphics.Rendering.Chart\n",
"import Graphics.Rendering.Chart.Backend.Cairo\n",
"import Graphics.Rendering.Chart.Plot\n",
"import Data.Default.Class\n",
"import Data.Colour\n",
"import Data.Colour.Names\n",
"import qualified Data.Vector.Generic as V\n",
"import qualified Data.Vector as Ve"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Let’s play with this learner using a subset of the `iris` dataset, which\n",
"is available with the standard R distribution, and on hackage as part of\n",
"`Numeric.Datasets`. We’ll try to learn petal width in an online fashion, \n",
"based on the other numerical attributes from the dataset. Let’s peek at\n",
"the dataset first."
]
},
{
"cell_type": "code",
"execution_count": 13,
"metadata": {
"tags": [
"input-output-hidden"
]
},
"outputs": [],
"source": [
"import IHaskell.Display\n",
"import Text.LaTeX hiding (dot)\n",
"import Text.LaTeX.Base.Parser\n",
"import IHaskell.Display.Hatex\n",
"import IHaskellPrelude (String)\n",
"import IHaskell.IPython.Types\n",
"pyJax :: IO IHaskellPrelude.String -> IO Display\n",
"pyJax pyBlock = do\n",
" out <- parseLaTeX . (toS :: String -> Protolude.Text ) <$> pyBlock\n",
" display $ fromRight (panic \"python error\") out\n",
" \n",
"rscript = quoter $ callCommand \"Rscript\" [\"-e\"]\n",
"rOut :: IO IHaskellPrelude.String -> IO ()\n",
"rOut m = putStrLn =<< m"
]
},
{
"cell_type": "code",
"execution_count": 14,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
" Sepal.Length Sepal.Width Petal.Length Petal.Width \n",
" Min. :4.300 Min. :2.000 Min. :1.000 Min. :0.100 \n",
" 1st Qu.:5.100 1st Qu.:2.800 1st Qu.:1.600 1st Qu.:0.300 \n",
" Median :5.800 Median :3.000 Median :4.350 Median :1.300 \n",
" Mean :5.843 Mean :3.057 Mean :3.758 Mean :1.199 \n",
" 3rd Qu.:6.400 3rd Qu.:3.300 3rd Qu.:5.100 3rd Qu.:1.800 \n",
" Max. :7.900 Max. :4.400 Max. :6.900 Max. :2.500 \n",
" Species \n",
" setosa :50 \n",
" versicolor:50 \n",
" virginica :50"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"rOut [rscript| summary(iris) |]"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Of course, we’re not really supposed to look at data advance after all,\n",
"as we are considering an online learning process. In practice, we'd have\n",
"to pick values for $\\eta$ and $\\lambda$ using all the a-priori information\n",
"Wavalible. We’ll proceed in the following way:\n",
"\n",
"$\\lambda$: The norm of the unit vector in the dimension at hand\n",
" should suffice. $\\lambda = 1$.\n",
"\n",
"$\\eta$: Notice that @eq:bound:tunedRidge does involve some parameters that depend on the\n",
" dataset. We might be tempted to minimize the value of the bound at\n",
" the end of the learning process by picking the right $\\eta$. We’d\n",
" need values for $T$, $\\left\\|x\\right\\|$, $\\left\\|y\\right\\|$, and\n",
" $\\lambda$. We can pick $T$ = 150, if we take the length of our\n",
" online learning process to be the entire dataset. We can also pick\n",
" $\\left\\|x\\right\\| = \\left\\|y\\right\\| = 1$ by assuming the dataset to\n",
" be normalized (which we will enforce below). If the data source\n",
" wasn’t normalized a domain expert could help determine those. If we\n",
" minimize that bound in $\\eta$ by finding the roots of the derivative\n",
" of the expression in @eq:bound:tunedRidge, we arrive at the\n",
" following expression:"
]
},
{
"cell_type": "code",
"execution_count": 15,
"metadata": {
"scrolled": true
},
"outputs": [
{
"data": {
"text/latex": [
"$$\\eta = \\frac{2 \\lambda \\sqrt{\\frac{\\sqrt{T}}{2 \\sqrt{T} - 1}}}{\\left\\|{x}\\right\\| \\left(\\lambda \\left\\|{x}\\right\\| + \\left\\|{y}\\right\\|\\right)} = 0.721998072401013$$\n"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"pyJax [python2|\n",
"from sympy import *\n",
"eta,T,lam,x,y = symbols('eta T lambda xnorm ynorm')\n",
"bound = 2*sqrt(T)*lam**2/eta + (x**2*lam+x*y)**2 * eta *(2*sqrt(T)-1)/2\n",
"solved = solve(bound.diff(eta), eta)[1]\n",
"print(\"$$\\eta = %s = %s$$\" % (latex(solved),\n",
" solved.subs({T:150,lam:1,x:1,y:1}).evalf())\n",
" )\n",
"|]"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Good to know we can select $\\eta$ based on a “worst case” bound in a\n",
"more or less principled manner - but as we’ll see below, this value will\n",
"not be so helpful in practice.\n",
"\n",
"We can compute the a-posteriori best average loss feasible, $C_{\\text{best}}$,\n",
"using a `lm` call in R[^truelin]:\n",
"\n",
"[^truelin]: Note the `-1` at the end of the symbolic\n",
" form inside the `lm` call. This is used to remove the intercept from the\n",
" model: For simplicity’s sake, all models in this page are truely linear\n",
" (not affine). Also note that the snippet scales the dataset to the\n",
" $\\left[0,1\\right]$ range. "
]
},
{
"cell_type": "code",
"execution_count": 16,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"\n",
"Call:\n",
"lm(formula = Petal.Width ~ Sepal.Width + Sepal.Length + Petal.Length - \n",
" 1, data = iris)\n",
"\n",
"Residuals:\n",
" Min 1Q Median 3Q Max \n",
"-0.25691 -0.06216 -0.02037 0.03772 0.25544 \n",
"\n",
"Coefficients:\n",
" Estimate Std. Error t value Pr(>|t|) \n",
"Sepal.Width 0.05180 0.02681 1.932 0.05525 . \n",
"Sepal.Length -0.22687 0.07180 -3.160 0.00192 ** \n",
"Petal.Length 1.15314 0.05296 21.773 < 2e-16 ***\n",
"---\n",
"Signif. codes: 0 ‘***’ 0.001 ‘**’ 0.01 ‘*’ 0.05 ‘.’ 0.1 ‘ ’ 1\n",
"\n",
"Residual standard error: 0.08416 on 147 degrees of freedom\n",
"Multiple R-squared: 0.9776,\tAdjusted R-squared: 0.9772 \n",
"F-statistic: 2139 on 3 and 147 DF, p-value: < 2.2e-16\n",
"\n",
"[1] 0.006941823"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"rOut [rscript|\n",
" iris = as.data.frame(reshape::rescaler(iris,type=\"range\"))\n",
" sm = summary(lm(\n",
" formula = Petal.Width ~ Sepal.Width + Sepal.Length + Petal.Length - 1, \n",
" data = iris\n",
" ))\n",
" sm\n",
" mean((sm$residuals)^2)\n",
"|]"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"We’ll use this average squared error when showing the behavior of our\n",
"algorithm (the plots below use it as a dashed line). But first,\n",
"let’s write a state monad for a one-pass learning process that saves all\n",
"predictions into a sequence:"
]
},
{
"cell_type": "code",
"execution_count": 17,
"metadata": {},
"outputs": [],
"source": [
"-- | The \"game state\" that we will use to run our one-pass procedure\n",
"data GameState v a = GameState \n",
" { predicted:: Seq a\n",
" , ogdState :: Ogdstate v a\n",
" } deriving (Show, Generic)\n",
"\n",
"-- | a one pass procedure: given a fitting function and a dataset,\n",
"-- this function returns a state monad that performs one pass of \n",
"-- online learning on the dataset. \n",
"onePass :: \n",
" ( Metric v -- ^ The container for the vector space\n",
" , Traversable t -- ^ The container for the dataset\n",
" , Floating a ) -- ^ The floating point type\n",
" => FitReg v a -- ^ the fitting function\n",
" -> t (v a, a) -- ^ the dataset\n",
" -> State (GameState v a) () -- ^ the output state monad\n",
"onePass fit dataset = for_ dataset $ \\(x,y) -> do\n",
" #ogdState %= fit x y -- descent\n",
" yhat <- uses #ogdState (predictReg x) -- prediction\n",
" #predicted <>= pure yhat -- history update"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Second, we acquire data and preprocess it. We’ll use sepal length, sepal width, and\n",
"petal length to buidld the $x^t$ vectors, and petal width to build targets $y^t$s.\n",
"Note that this snippet shuffles the dataset and normalizes all quantities to\n",
"$\\left[0,1\\right]$."
]
},
{
"cell_type": "code",
"execution_count": 18,
"metadata": {},
"outputs": [],
"source": [
"import Numeric.Datasets.Iris (iris, Iris(..))\n",
"\n",
"normalizeDataset :: [([Double], Double)] -> [([Double], Double)]\n",
"normalizeDataset d = [ (features, target) \n",
" | features <-\n",
" transpose $ scale <$> transpose (fst <$> d)\n",
" | target <- scale (snd <$> d) ]\n",
" where \n",
" scale l = l <&> \\x -> (x - minimum l) / (maximum l - minimum l)\n",
"\n",
"dataset :: [([Double],Double)]\n",
"dataset = shuffle' normalized (length normalized) (mkStdGen 1)\n",
" where\n",
" normalized = normalizeDataset (iris <&> iris2instance)\n",
" iris2instance Iris {..} = \n",
" ([sepalLength, sepalWidth, petalLength], petalWidth)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Here is the plotting function used below. It \n",
"feeds one passes of some dataset to OGD and generates a plot of the\n",
"cumulative average absolute regression error:"
]
},
{
"cell_type": "code",
"execution_count": 19,
"metadata": {
"tags": [
"input-output-hidden"
]
},
"outputs": [],
"source": [
"cumsum :: [Double] -> [Double]\n",
"cumsum = IHaskellPrelude.scanl1 (+)"
]
},
{
"cell_type": "code",
"execution_count": 20,
"metadata": {},
"outputs": [],
"source": [
"plot1pass ::\n",
" (Double, Double, Double) -- ^ a-posteriori best loss, eta, lambda\n",
" -> FitReg [] Double -- ^ fit function\n",
" -> [([Double], Double)] -- ^ dataset\n",
" -> Layout Int Double\n",
"plot1pass (best, eta, lam) fit dataset = layout\n",
" where\n",
" n = length dataset\n",
" (GameState (toList -> predicted) _) =\n",
" execState (onePass fit dataset) $ GameState \n",
" { predicted = Data.Sequence.Empty\n",
" , ogdState = initialOGDState [0,0,0]\n",
" }\n",
" points = plot_points_style .~ filledCircles 1 (opaque black)\n",
" $ plot_points_values .~ [ (x, l / fromIntegral x) \n",
" | x <- [1 .. n] \n",
" | l <- cumsum [ (p-y)^2\n",
" | y <- snd <$> dataset \n",
" | p <- predicted\n",
" ]\n",
" ]\n",
" $ plot_points_title .~ \"Online \\\"ridge\\\" regressor\"\n",
" $ def\n",
" bestline = plot_lines_values .~ [[(1, best), (n, best)]]\n",
" $ plot_lines_title .~ \"A-posteriori unconstrained batch model\"\n",
" $ plot_lines_style .~ dashedLine 1.5 [2,2] (withOpacity black 1)\n",
" $ def\n",
" layout = layout_title .~ \"Average squared regression loss\"\n",
" $ layout_plots .~ [ toPlot points, toPlot bestline ]\n",
" $ def"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"We run the one-pass learning experiment using the value for $\\eta$ we\n",
"selected above and plot the resulting evolution of the normalized\n",
"cumulative absolute error. The red dashed line represents the best\n",
"attainable value $C_{\\text{best}}/T$, as given by the squared residuals\n",
"of the batch linear regression performed above."
]
},
{
"cell_type": "code",
"execution_count": 21,
"metadata": {},
"outputs": [
{
"data": {
"image/png": "iVBORw0KGgoAAAANSUhEUgAAAcIAAAEsCAIAAADfNCTgAAAABmJLR0QA/wD/AP+gvaeTAAAgAElEQVR4nO3deUAU9f8/8NfssoAiKocIgooHoAii4lmpiIlHHqmo2EWHffzot+ujZIclalopaZmZfFIr+fkxD7Sy1Iwk1EqtNBW8UhMPVJZFUJRjj3n//lhdlz1hZmEH9/n4p93ew7zfM6+dl/N+z3tmOMYYAQCAUDJnNwAAoGFDGgUAEAVpFABAFKRRAABRkEYBAERBGq2GKb8c5S3jOI7j5P6Pf33T2e0BPV3egh7uHMe5xy48oXN2YxyMFX421JPjOLfwWQc0DWrlcBfSqDGm3J6Zc1s/A4wv+WFz1g0nNwgApM/N2Q2QElaoz6IcxxExvnRX5k83xo9vVjeVadRqhbt73axb6uph2+uiirppNuczbP7W717kuSYdOuFwbJhwNnoPK9yeuaeckcxv1OSh3hzxpbs2/1h6p7Ay+//aunGczGfCxpI7NyxU7Xkp1I3jZN6PfH6NERGpL+xa9NzDUSHNG3k0at662yMv/vdgMX9n1Xf7VjO/+WHhxNiQpu7NJm+9mbvm+dH9u7YP8m3i4e7ZtGVYv/Gz1h27abgfgr+WvXBC91bejbxDek5evDt7nlnH1nqNZhtX8sd/pw+Nae3T2N3dyyeoXfSDI5/97Midfp6u4Mf542OCmliuSJc7v7s7x3Huvd47qSMi0v7+WoSC4ziP+BWXeSIira0Nsbzt5XYar7v60zuJ3Vo1adQ0pOfkxXuUNrvywqqwvXuFrNPGTrZexEp+mDNu1KhRY/71xSntnV9W/s73nxncJbhZI49GzUOiHn5u8Y8X1CZb+p/M7QuTerVp5tnIL2xIytf5Ne6yW1+5sPYDETG4g7+yapgXR8T5JG0688XIJhwR5zNxYwmvL67c+0p7ORHXfMKd/1W19+VQORHXbOy6Ip4xzdk1Y4LkHBEnb+TbwsdTxhFxjbrO/LmEZ4y/9t8EDyKSNfH3b8wREZHn2PWqb59oynHyRj6BwcEtmig4IiJZwPh1BTrGGKv8a0EfL84QKM6rVbCvjIgUPRYc1zJmp0YTpduSA2VExLk3bdmqRRMFxxF5Jm4sZ4yxij9SYxvbqEh7bF43BREper57Ql/xwVnhbkTkPuiTS/qm2toQy9teYrPxFYfm97K57SahE1CFvd0rYJ02drKNorsVycNe3a9mjGnOrB4VKL/XMiIizi143Nrz2nsLcx5eXgq5Z9MmHhxHRJz3kJX5Oks/6tqsXFj7gTGk0bv4K58NbcwRcU3HrivWFqQPacQRcc0nbLh+JympD8wKdyPifCZuKmGMVe17pb2cSOY7aVMJz/iSr59oKSOSBYz8JK+MZzrVnpRu7hxxHn0XndIafs3EyVs/umzveWXhuT+PXao8/eOmvedKNYwxxjRXv/9XRzciziNu+QUd40s2J/nJiEgePPbTQ9euX8yZN7C5jO4d53ZqrE7z++ud3Ijcot74vYIxxrRlFw5uWbnlmIYx/vrGib4yIpK3mbjqSGHJpb0L4n2NK7qXRnu/f8pyGtXa2BCL2340d7ONxvMlmyfpm9RqzPKDl5X/ZL31ULNqTTKNnZAqbO9eAeu0sZNtFJlkOr5k6+MB+nBMWHWkqEx5aMWjreREJGv13I4yo1Z5P7Tgjxs69T+fDGnCEXGew1Yrzf/1rNXKBbYfkEYN+IL/JjTmiDivEZ8X8kx3/qP+7hwR1zzRkEc1h9+KciOS+SRtLuWrfp3RQU4kC3jy25uMsaqf/h0kIyKZf+TAwYMHDx48OL57sAdHxHmO+FzFG04iPB9eednorKHy0q/rPnjjhWefSJqQOH50ryA5EcnbvJijZuqcF9vIicgt6u2/9D/Wih+mBBqdLtmpsfrW6fKXDfTgiHNrGTvu+ZnzPlyzdd+ZUn0+Uv/8Qms5Ebl1TT1yp6JdzwdaPBvts+i05TRqa0OYpW233fiqu9se+eaf+ibd/v7pFjU4GxVQhbXdK2CdWus72cb+N8l0VVlTg2REpOg2P1e/wJ0URvJ2/9mnNrSq2aTNNxljTJv7TncFESl6vJNnY8/UZOWVwtoPjGFMW4+/8l3mvgpGpIiIDr52PE+pa9O1vXzfKe2NrM27SiYm+XJEbl0nTYxelPfXjR+3/lTc6sC2fB3JgkY/9rA3EemKVaWMiHjViT27T1Rbc2lJKaMm+i+yoKiogLvj0ZV/LRoS/+YvpSaDmayqsooRX3q9hCcieVBIkJyIiNwCgwNkdO3u0vZq9DPuucnaPLXg7e8nL/jp8qGtqw5tJSJO1jR62rpdy0f5lF4v5YlI3rJV4N2KWhlXZNSyu//lWbUH2tjckHttMNp2243XlRTrtz24bYi+Se6t2wbJqMjysK+gKuztXgHr5Kzv5EAbRdWr010vLmVEJAsKDtTXKgsMDpTRKeKvq64bWidrERLsSUREHh7uRERMp9PZfciQ7ZWTsPZztmp0EbjERERE/NXvMn+pZESkObxoaEx0dHS3cStOaYmI3fxp8647F5XknSdO6uHO8aW7Nixe+22+juQhYyfHNSYikvv6N+eIOI/BK69UPxOs+nVGh3t72U1h+IdLve+/H/1WynOKLi98d75My3jl6mEehgVlzX19ZESkK7xyTX95RXP1cqHRQV7TGvW45g/N/vGfglO/fve/9LQ3k/u04Pibx1a9979/eJmPn76iawVX9RVpr15RVssmcrk+06grq4iIqOrKJeOMZntD7jHadtuNd7vTpLv/lBCxkuulNXkSWc2rsLd7BaxTZn0n29j/JrXJff2ac0TEXy24k9L5a/pPMl9/33th5WR30hfH1TyP2Vm5I9rvmpBGiYj4K9syf620fJyymz9t/uH6nTwaNiGptzvHl3zz0edntSQPHf/YQ/pzAkXPoYP9ZcTU+z5O/Tq/kohIe+Psz2tmjfu/r4osr1h3s7SMEZF7h94PtG0i117c9s0f9658KmIGPthcRqQ9/uV7GceKSi/v/eD9LcbJq1Y1suv7vvj02+PqNn1HPjY1Zf67U3o15oj4G9dLebeYAQ80lxFpT3yxYPWhK8UXctLez6yWRmUtggLkHJH27J6fz2vY7aOfLt95w6gG2xtike3Gu8UM6NdMRqQ9tjHjjzIiXrnjy+8Kajnt3nYVdnevgHXa2Mk2isyqSBjkJyPS5K5+54tjxbdVf616N+OMlkgWMOjhbora7QPz9ttauZsj2u+iHDc+0IBdXBHfiCPiPAcsO39v5FJ7YmGsgoi4po+uuzvYqLuzKBGRW6fXD6oNS2vOfv5oKzeOiDg3rxatgnwbyzki8hi6qpA3u2CqX9Wq4c04Ik7uEzlkzLCYlk29GnNEJGv5/K4qZn4puXFgkI+MiBSxC+9cMLdVY3W6i8vj3Ik4mbt3i+AgHw8ZR8TJ272w+zZjrNL8srhPtYFI3YX0hKYcERGnaNLMy82tUWMPjgxjo3Y2xNK222u8oUmch3/7iNbN3Bs18uTI7thoraqws3trv04bO9nW/je7mH46fUSA6cV0edCYz89pLbRKeyatr4KI3GLmHrVwwac2KxfYfmAMZ6NERNu2/FbJiPN8cNLYNvf2iDx8/ITuCo5YWfbmncX60y9ZyNjJA/XzX9w6T5zU497pgVuHZzbu35n2r6Exrb350uIyuV/HnsOffWvZawk+lntdstbPrN7w9uioFu63/jmUeyv2rc0LBxn3hT26vfH1t/PHxwQ29mjSqnviO1s+TfLjiEjW3Ed/2boWNXLNek18fsKgmHZ+inJl0W2Ff8d+E97YsHNxfGMi8ujx5jdfzxvX9U5FC7/OeD5UXq2lbZ77LGPmkDBfT4VHsw4j3t6aMbWt0QL2NsQi2403NKkRK78lj5ryxf97pfZT0+1UYW/31nqdNnayzf1vWkX41C37v3nnqbjOgd4eCg/voM6Dkhd+9+vGZ9rLzReu9T6xsXIHtd8lOTuPg1Xa8/uzcov0Z0J82ckvJrWRE3EKy6cdjqzXcPHX4qnf/cJZuxfuP7hSL13aQx+OnpCp8/Zv6aO4VXi1tJJnnGfk1EUvRCNqDoDdC46CTr10ySOGPTkitk1jteqKssIjsFP/Sa998csvy4b6WR4kgNrB7gVH4RheaQcAIALORgEAREEaBQAQBWkUAEAUpFEAAFGQRgEAREEaBQAQBWkUAEAUpFEAAFGQRgEAREEaBQAQBWkUAEAUpFEAAFHsplGmyp47LDqic0R0wuwsJbNTxCt/XjA2pl2bNq07xi86rK2rVgMASIa9NFqRM2961oD1R0/mZg7f/+KcrNu2ivhLX055fl//jNwLFy/8tfaxdg54WjcAgMTZSaOaozuzA8YndfEk9/CkiW2zdxzWWC+qurBl7Ylhr/9fTBOOZN6tW1t5eQYAwP3EThrlr15WtgwJlBER5xscWHa5QG29qPzsyfN+t7Y/1b9rROcHn1r++w08yRQA7n9235dg/FRnxog4G0U8X3XsmOyDn470U++cHv/Me32OvN/bxithTd6wnZKSkpaWZviqVCqVSqXha0BAQEBAAEodXnr+/Pnbt28L+1uUovQ+K719+3a7du2otmy/qkm9/9XI/kvO6hhjfMHKIWEv7VFbL6rInR/bKUX/3teq7c+0euSLYtMX/VZjt3aoB7m5uc5uAjCGQEiDsCjY6dQrYobFFW7ZeLyS1Kc3bLoQNzxWwRce3rH3XIWFIs+IYQmNDuw+UU7sxsHdh7wjwr0xOgoA9zt7V+obDZq7Ij4nqUtY5LgdfT6en+BF2qPpU+fuVPEWihQ9X1sx5s/kru3bd5t+ZuJnb/az0aPX4zhu7ty5jtkUAABncOYr7TgOL9Rzvry8vKioKGe3AhAISRAWBancxaRSqdLT01UqlbMb4nKMh9jBiRAIKRAWBamk0YyMjGnTpmVkZDi7IS4HR69EIBBS0CDTqGFsNDk5OT09PTk52bntAQCoLYyNAgCIIpVOPQBAAyWVTj04i/FNHeBECIQUCIuC3ZtB6xY69U6nVCpxcUMKEAgpEBYFdOoBAERBGgUAEAVjowAAomBs1NVhPE4iEAgpEBYFzBsFABAFnXoAAFHQqQcAEAVX6gEAREEadXW4eUYiEAgpEBYFjI26Ohy9EoFASAFuBgUAcAJ06gEARJFcpx5vEwGAhkVynfqMjIyZM2eWl5fPmDHDKU1yNbh5RiIQCCm4T+5iKi4uzszMTExM9PPzc0qrAABqRXJpFACgYZHc2CgAQMMiubFRAICGBROeXB1mfUsEAiEFdXQXE1Nlzx0WHdE5IjphdpaS2SxSZ08P8fYPCQkJCWnTdebPavvVo1PvdDh6JQKBkIK6uYupImfe9KwBm4++GXHhw2Fj5mQdSk/wsloUR9R4zKrcdWM9alo9OvUA0NDZORvVHN2ZHTA+qYsnuYcnTWybveOwpgZFAACuw04a5a9eVrYMCZQREecbHFh2uUBtu6hi50tR7UI7PfTUsv0lONEEABdg90q9ca+bMSLORpEidvYvZ5e19dFd2DZj1ONvROalD2lse+0cd299KSkpaWlphq9KpdJ4nCIgIMD4BgOUOqrUy8srLy9Paq1ywVIiMgRCOq1ytVIvLy+qPTsT4DUHZnWbFbgtZ0YHGbuSPjTu5FvHlw1Q2Csi0v75Zo9XfLbseTVMbqNuTL8HgIbPTqdeETMsrnDLxuOVpD69YdOFuOGxCr7w8I695yosFLmVnD+jVBORrmjfxl2lHTsF2sihAAD3B3sTnhoNmrsiPiepS1jkuB19Pp6f4EXao+lT5+5U8eZFfMH2lLgOrYKDQ2Jf/nvU6vce8bZbPSY8AUBDh3vqAQBEwV1Mrs54xB2cCIGQAmFRQBp1dTh6JQKBkIIGmUYxNgoADR2e8AQAIAo69QAAoqBT7+qM7+IAJ0IgpEBYFDDhCQBAFHTqAQBEQRoFABAFY6MAAKJgwpOrUyqVuLghBQiEFAiLAjr1rg43z0gEAiEFuIsJAMAJJNqpV6lUmZmZiYmJ/v7+9dwkAIBakWinPiMjY9q0aRkZGc5uCACAHRLt1CcnJ6enpycnJ9d7i1wOLmtIBAIhBbiLCQDACSTaqQcAaCiQRgEARJHo2CgAQEMh0QlPUG9w84xEIBBSgLuYQAjcPCMRCIQU4C4mAAAnQKceAEAUdOoBAESxm0aZKnvusOiIzhHRCbOzlKwGRZoTaQ818Rz48UW+LhoMDobLGhKBQEiBsCjYS6MVOfOmZw1Yf/Rkbubw/S/Oybptr0j3z5q3fw4Z1EZeo+oxNup0OHolAoGQgjpJo5qjO7MDxid18ST38KSJbbN3HNbYLOKvfPXWNzGpU8NrlkWJMYY0CgANmp00yl+9rGwZEigjIs43OLDscoHaRhFTfff254FvzOjuUbeNBgCQDrtX6o0vpTNGxFkvupU9/0N6ecuAJtz+mlbPcffWl5KSkpaWZviqVCqN53AFBAQYn2+jFKUoRanDS0lQv97OM5Y0B2Z1mxW4LWdGBxm7kj407uRbx5cNUFguemNDwOyRn15xVxBVlVwpdQse+m721qntrJ/v4glPUqDEzTPSgEBIgbAo2OnUK2KGxRVu2Xi8ktSnN2y6EDc8VsEXHt6x91yFeVHvHrN/u1KQn5+ff2bLlA79UvfYzKEgEcb/OIMTIRBSICwK9vJco0FzV8TnJHUJixy3o8/H8xO8SHs0fercnSreQhEAgOtx8mObiSg1NRUX650oLy8vKirK2a0ABEIShEUBN4MCAIiCwUtXh8saEoFASIGwKOAJT64OR69EIBBSICwK6NQDAIiCTj0AgChIowAAomBs1NVh1rdEIBBSICwKGBt1dbgHUSIQCCmok5tBAQDANnTqAQBEkXqnXqVSZWZmJiYm+vv710+TAABqReqd+oyMjGnTpmVkZDi7IfctjMdJBAIhBcKi4ORHk9itvbi4WH826ufnVz+tAgCoFTzhCQBAFKmPjQIASJzUx0YBACQOE55cHW6ekQgEQgpwFxMIgZtnJAKBkALcxQQA4ARIowAAomBsFABAFIyNujqMx0kEAiEF9+ddTAAAEtdgOvUqlSo9PV2lUtVxiwAAaqfBdOozMjJmzpxZXl4+Y8aMOm0SAECtODmN1lxycrKXl1diYqKzGwIAUI3dTj1TZc8dFh3ROSI6YXaWktksqtzz9kOd24WGtmkdMejlzf9oHNlQPz+/qVOn4jlPDoebZyQCgZACYVGwl0YrcuZNzxqw/ujJ3Mzh+1+ck3XbVpF79xe2Hv4nP//imW0jj82Yu7PcbvWY8OR0OHolAoGQgjq5GVRzdGd2wPjvuniSLDxpYtuBOw5rEvorrBe11M8W4LVanpPV4PIVrtQDQENnJ9XxVy8rW4YEyoiI8w0OLLtcoLZdpP4ppUdYq8B+GZ2WLRjeuE6bDgAgBXYvMRmfLjJGxNkucn/4g8NnFt84lDb55U9+S3i/v5ftteuf3KyXkpKSlpZm+KpUKo1PsAMCAoxnxqLUUaVElJeXJ7VWuWApGQVCOq1ytVIShtmk3v9qZP8lZ3WMMb5g5ZCwl/aoa1DEmO7c0gFdZh3U2Fy53dqhHhQWFjq7CcAYAiENwqJgp1OviBkWV7hl4/FKUp/esOlC3PBYBV94eMfecxUWiuTK44cvlDMi/uaRTdvOtg0PkQvM7VB/TM5MwVkQCCkQFgV7l4EaDZq7Ij4nqUtY5LgdfT6en+BF2qPpU+fuVPHmRez6b4vHRAa3Cg7p8uTPPT7++MlWnJ2140o9ADR4uKceAEAUPG8UAEAUpFFXJ/zqJDgUAiEFwqLQYJ7wBHUER69EIBBSICwKDeYJT3oqlSozMzMxMdHf37+OmgQAUCsNrFOfkZExbdq0jIwMZzcEAOCOBtapT05OTk9PT05OrrMWAQDUDiY8uTolXo8uDQiEFAiLAtIoAIAoDWxsFABAahrY2KgB3nAHABLRwCY8GeANdwAgEQ21U29yyR4np4Jh1rdEIBBS4Fp3MZm84c4wnxT5tLZw9EoEAiEFLnEXkzWG1y+vXbsWnX0AqE8N5j31tulPTgmvsweAenefpFEDQz4FAKgfDXVsFBwFd85IBAIhBcKigLuYAABEaagTnvRwXR4AnK5hd+qtPTfPkF7rKM8ifQOAQcOe8GTturzhHicicuD8J8NDo3EPFQAYNOwr9dauyxunV+M8K/Lh+YbsaTF913blhuWJyImP9Mfz2SQCgZACgVFgzlP/tS9ZsoSIlixZIuzPDX15/deioqKVK1cWFRUJW7lheZGtEik3N9cp9YIJBEIKhEXByWmUiFJTU+u6IkO+M+RBkwwojEn6q+3KzQdwxTRGMBy9EoFASEGDTKP1U5H56Z5DTgCt5U1hK3dIZhcAR69EIBBSgDRqlfnpnmNPAGt1WmotXRpWYrJAXadXHL0SgUBIQR2lUb5od+rQqPBO4VFD3vyxkLdVpMvf8p+EqLbBrVq1iRm/+NfrvLV13q27vjr11jgqQ1lLyhZPS62dqxpWYrKAtfTqKIWFhY5dIQiDQEiBsCjYS6Pl2S9EPLDwWAWrOrV0UMTUXbdsFOku/vL9b5fKeaa58vUzYVFv/qmxU7dTL3CxGmQokZnLYnq1eyKsX+D06dMm47n61s6fP98pfX8AsMZOIlPvfzWy/5JzOsYYf2VlQtjLe9U1KGK86vNHgp7+vspO3c5Oo9ZOAA0cMoQqLBebV61v7fz58y02yVlDqwBgJ5FVbp3sn7jxtv7ztqcCx391qwZF6hMfxIUnf1Nsp1fv9DRqYG000+TEUNjKheViayetJk01tM3kzFpkmwGg5uxOvze+zYgxIs5eEbue/XryuoilP4z2NVrWCo67t0xKSkpaWprhq1KpNH4SdUBAgPG0WIeX6qfxL126dObMmcePH/fx8RkyZIiPj8/YsWPXrVtnuGdJwJoNc/VPnTq1fv16/Wpr8rfGdxYYlz744IM6nU7fqtGjR2/btk2pVMbHx8+ZM6d3796LFy9OS0vT/3/BbUYpSl2zlIQ95Ml2ltX33M/qGGN8wcohYS/tUdsuunVo8eCosatP2+nPM8akdDZqYLHj7KjL+o6dZq9v1d9//21xEoLh/9u+7l9UVLR48eKioiKMCTgdLjFJQR1dYto9PVx/HenkkkHhz++8xXTXDm3fc7bcUlHV32vGRQ1694+yGtYtvTSqV0fz4Z0yzd6ks2/4F8Lkq7UxgVoNESAXi4EJT1JQVxOelFlvDYls37FD58Gv/3BVx1jVrudDBi2/qDMvqvrp30Fujf2C9do/u9VOOtWfDjtxwpMrML/Qb/J1zpw5xndS6f//6NGjjdOr4athtRbTa13Pzbq/IY1KAabfgy0m58KGrya/G5MxAWtDBCbp1ZBVTWY+IJ/WHNKoFCCNghC1+t0Y8qNJerV2H5fJXFeLIwaOSrJ2J/9KPKcjjUqBsCg07AflgXi1ui5pmHVgeERhWFgYmT341eRFrUqlctq0aYbHvxpmEdDdp8E+9dRTmZmZ8fHx2dnZdh8YaP5AQv3/KSoqmjNnjvnaTB4+W1RU1KJFC8Ofi3x2ogMJuUAMjiYwCg5P5zWnbwDGRu97Js+yMhkxMB+QtX1dy3zEwOKwr2FtJrVbu8hm+2QW83DBBnTqwfksDhGYZFXjMQGTkQSLw77mU8GMS61dczNP4nYbU5/ptU5HRUAwpFGQHGsDr9ZGYMXUYn7NzeLJrLXG1PAM2lEszqPArWtOh049SF09P9+6hieztT2Dtp3gavWo79qOiuCkta7hbNTV4eYZhxB20mo+vCtsSoPtnG773gq7w8G1WqyhnxELOxxwpd7VKfEmNUewMXXBy8srPj5+xIgRiYmJa9eutThXITk5+caNG0Rke0qDtTfRWqzdUCndfbGjxdoNUxfo7qsV9XMbhC1m+KqfL2FYvobTMJxO2OGANArgeMbvrK1JgvPz85swYUJQUFBAQIB58qXqL7itee36Sg1tsFi7yXQ0w4tvhS1m8g+GtfRqyKrk1NfiOozDz4prTt8AjI06F2Z9S4SzAlHDoefajlDXcBDZ7oCDyZBCDRcTrEFOv2fGD9sDgHpnfuIsZjEbywsYcDAfUrA4kmBt5KHeznnRqXd1GBiVCBcJRK0GHMyHFGq4GNXsfjkyy7a4iwkA7k8iRxJq+AAzwc8C5pjzutUc58zaAcDVFBcX2z4b9fPzE7BapFEAAFFkzq2e47i5c+c6tw0AAGLgSr2rw/R7iUAgpEBYFJx8NgpOZ/yiRHAiBEIKhEUBaRQAQBSMjQIAiIKxUQAAUdCpd3W4rCERCIQUCIsCOvWuDkevRCAQUiAsCujUAwCIgk49AIAodtMoU2XPHRYd0TkiOmF2lpLZLNKd+vzp/p1bNvboPj9XV3dtBgCQEHtptCJn3vSsAeuPnszNHL7/xTlZt20VcX69nlv67dev9ajxUAHGRp0Os74lAoGQgjqZfq85ujM7YHxSF09yD0+a2DZ7x2GNjSJZi+j+vTr4enA1rp4xhjTqXDh6JQKBkII6SaP81cvKliGBMiLifIMDyy4XqGtQBADgOux2v40vpTNGxNWoqKY47t4fpaSkpKWlGb4qlUrjfxkCAgKM5yKg1FGlRJSXlye1VrlgKRkFQjqtcrVSEsb2U53V+1+N7L/krI4xxhesHBL20h61vSLtyff69Zx3TGv/kdF2a4d6gFfaSQQCIQXComCnU6+IGRZXuGXj8UpSn96w6ULc8FgFX3h4x95zFZaKBGZycCaTM1NwFgRCCgRGwV6e5ZVZbw2JbN+xQ+fBr/9wVcdY1a7nQwYtv6izUKS7vGZ8u+CWzTzcm7YMDh23+pLO5qprUDsAgNQ5+SUiRJSamoqL9QDQcOFmUAAAUXAzKACAKHjCk6sTPskDHAqBkAJhUUCn3tUp8SY1aUAgpEBYFNCpBwAQRe7EPvW8efP0tefn5x85coSImjdvjs/1/FmtVpeXl0unPS77uaz7xtAAAA7LSURBVLS0tEOHDtJpj2t+FtgncOJkK30DUlNTU1NT9R8YY/hcz59zc3Od3gZ8JqJp06Y5vQ34LOwuJifPG9XXnp+fn5+fHxoaGhoais/1/Llx48bl5eXSaY/Lfvb29o6NjZVOe1zzs7CzUUmkUQCAhgsTngAARMGEJwAAUTDhCQBAFKRRV4ebZyQCgZACYVHA2Kirw9ErEQiEFOBmUAAAJ0CnHgBAFHTqAQBEQafe1eGpQhKBQEiBsCjgLiYAAFEwNgoAIArGRgEARMHYKACAKOjUuzrM+pYIBEIKcBcTCIGjVyIQCCnAXUwAAE7g/E69SqVKT09XqVTOboiL+vTTT53dBCBCIKRBWBQcO3OTqbLnPfHyVxfU7q0Tl65bMCSAs1k3xzHGli5dOnPmzCVLlsyYMcNxLYGawuxdiUAgpEBYFBx6NlqRM2961oD1R0/mZg7f/+KcrNt2/4LjuMLCwvT09OTkZEe2BACgvjgyjWqO7swOGJ/UxZPcw5Mmts3ecVhj708YY4sWLZo6daqfn58DWyKelC98oW2CSbx5kiXl/SaFtjmyH1H19WMh6x+9sHliY6Kq75JD1w4/m5nkZaNuCfdiXKdtUl6bw0m5eWibMFL4ATv2Sr1x/YwR2RwaJSLiOLuLOI3rtE3Ka3M4KTcPbRPG6W1zZBqVBbVuWXj5Kk8dZKy44FrT4FYKm8tL9t83AICac+TYqCJmWFzhlo3HK0l9esOmC3HDY22nUQCA+4CDJzwV/TTn8ZfXn6/yaDvhw3ULhwY6f1oqAEDdku7IMQBAg4DTRQAAUZBGAQBEQRoFABAFaRQAQBSkUQAAUZBGAQBEQRoFABDFKWmUqbLnDouO6BwRnTA7S4l5q/VJnT09xNs/JCQkJKRN15k/qwnhqFe6U58/3b9zy8Ye3efn6vT/y3z/IyJ1zzwQYg4NVv/Ks1+IeGDhsQpWdWrpoIipu245oQ0uq2r3tLDHt1Ya/R+Eoz7plMf2/n7617l9e847pmWMWdr/iEg9MA+EiEPDCWejAh5LCnUH4ahXshbR/Xt18PUwPJLIfP+XIyL1wCwQ5mp+aDghjfJXLytbhgTKiIjzDQ4su1ygrv9GuLKKnS9FtQvt9NBTy/aXMITDycz3fyUi4ixCDw3njI3W9rGk4DCK2Nm/nP3nzPlTu2Y1WfP4Gz+VIxzOZr7/ERFnEHFoOCGNGh5LSlSjx5KCI3HNgtv6KIg82454dmSTvCMFDOFwKvPDwQMRcQoRh4YT0igeS+pErOT8GaWaiHRF+zbuKu3YKdAT4XAq88OhMSLiDKIOjbq+IGYJr8x6a0hk+44dOg9+/YerOmc0wVVpc5eP7hwS1KpVYOvo0am7rugYwlGvdJfXjG8X3LKZh3vTlsGh41Zf0lnY/4hI3TMLhFrEoYHnjQIAiIK7mAAAREEaBQAQBWkUAEAUpFEAAFGQRgEAREEaBQAQBWkUAEAUpFEAAFGQRgEAREEaBQAQBWkUAEAUpFEAAFGc8fR7Zc6iyX06dYwID4uKn/bFsVuWF2PK1Y/0nHNEe+9D7dxYlzhw8Ynf3+r39LYqK2s2btS5JXGDl+Xz4tYMNtz8+okWHj3eydM5ZnVlf65btacmr3ur4e9H4M/MIRy9LWZMf978pU+GPPDuSduhsNmqGq2h1qwehvoNd2xlDlTvaVR78qMJz2bHfnrwzOm/T2a95vnJuH9vsf0D4nxGpa2ZEubmoAYwHd/coSu0VIWuVo/Nqu3y9bk2hyn9cfOBsF78N5l5DslUrOzPdav3FNr9d6+G4a6HX4WNyi1ui6U4OvhYENAqsKS+06jm4Kr0G08seiW2GUfkFjR0fuqDez7ZcIHnL33ycNfEF6dOHDf8gZ7DF/5Wdu8XxEq+e/W51We0ZGmZytP/mxbfLTo6qkvfx1b8ZXxiK/Ns7uvlpmji28yDI/3fjpv+zLjRI174Ku9b/QqJ3fht0cguHbvEDpi8/K9yIiJW+ut7j0SFRfUcmPTKE70HL8vnzauovmYD4yo2FJSb/pXZmrU2l2dFWbOHdO3SLbZHTO9/b1Xx1b8yVvbn8sm9IiI6hUcPm/3DNd6kdsn99tn1HzYd6v/aJ094fbv5mFke5S998nDUqOeeSkwcPfCB0Qt/KWFktoHVdsiWM9+9v/yPU188Ozgu4e3dFWYxshJuWzvt3mJ36fIW9B36aQFPRLrTix66GzKTX2DFyYx/D4yK7NotplfSZ3/rrNVS7a9sbMtt4zjm71888sFePWI6d+o1eeXR8toeC+Y/b+OIVOaufHJAz6iOXUYs/KWEkeZgtbpYyffV9rDZZhKR+vTaf8X3iGgbPqTaActf+mRI7JMpTw2MCQvt+tjnB3YvGNcvqn1o3xk79W+PNt0/ltpp/biWpnp7TKretf8mtHj8mwrDd13+soHBU36o0l1cHuc7ePk5DWMVe16OejRDpStcNSL27b80jL/7wXwZzYlF8UMX591mjJUfnd9/4Ad/a63Uq7u4PK5Z/yWn1YzdW6Hm8Nvdus3YW8rzN/e/HuPV/6PzVYfe6t7zjQNljN36M7Wnd/+PzqsFVaE1+6tKszVrbC1/+tqakV1n7a9ijPEVZWXqompfNZq/5nTv+tLuYp6V5y6O6/j0thvGtUsPX7RuXPhz229pz30Y1/X1300bqbu4PK7pA4tPVjGmPr1kUOybf1aYbmCpyR7gC1YO7X3n1bjme1ttMdw2d5phMQNt7jt9ElZc1jHGtKfefzBeHzKTX2Dewj6RU7Zd0zLGKq9fv81bqaXaXxUprW9LtTjyN4uvqxlj7Nbvbz4wes01vlbHQqXZz1tnvMO9us769QbP3zzwRq+YN//UmNdlvIfNNlN3cXlc096pf9zk+evfJoc9mqHijVferO/8w7eYNn/Fw/7tHs+4oGHlv6V0jfvwH52F/WN+GJofdJrCVSNi33bgL9KxbHUPVCpVZmZmYmKiv7+/o0rNu5uG/+PWcWBcWzcieceIYOVlpcUTqurLFBaW7z5y6vr0Eds5IqoovR13hacwuZXNkXeMH9ze+C0ATHngoG7oO/2acRz1TBrT6SAx5cHf+SELY5sQUbfxozrtJVa0V0AV5n9VcM10zbaXv+o9qK/X+zOmyCc9MmLMyIdCm3Uz/tpWuf+AOmFef1+OKHJyYujwX05qu5lvoED5+fn5+fmhoaGhoaG1/Wx5jaxo++bjcdPjvOSeY8f5j9z05/xe/UwaKu84eEhHdyLqkDDIbcb+Y61MNvCU16RqO4RuGq3dQowshdsRO83kF3jt9t6bw1OHtZQTkYePDxG7YqmW6n9V5D3U2rbod8XdJulK9n/06gdZl3Xu8uJ/ikbm66id1ZaYHQsF10x/3tVrCRs5sXdTjqPYSSMUKQeuaVocNamrtdGu22eymcQTycNHjOvmzXF8bO92iy4refIzHBdu4cPGdPUiuXtMtH9U10dauxEX1a2j8q+rOuZhun9OXAk1PQwtBlTKbHXqMzIypk2blpGR4cBSv8guzXP/PGnoOt0+cuhcWHSEGxGRXK4Pg0wm43krw3vVl+EZ8xmVlpWTk5OTk3Pw2B+LBto4IDh3d3ezN/u5KfT/kHBu7pb/RRFWRQ3/ysbyjXvMzvkl/YnOml9TEwYvOMJV/6olVv0thZy1DRTgyy+/HDRo0Jdffings0Ws8PtNOVe+fT4yNLT9wEVHzn+96aBad+LD4Z06duzYecLqCzwRkVajfwk402o0jMhsAxWme+Aei3vb0t6o5U6TcRzP6w9gne7uxRT7v1ILtZj8lY1tMW5S+c7UGceGfpnz696cba/1kWlNxkprcCzY/Xkb2KnLEk6hUHBExMnlctNd4abQ/+BlcvmdpWRyGdMvZGH/mLSzVgedFNhKo8nJyenp6cnJyQ4sVfSd8q+m/++1pX+U8kSagh2z5/7y0LRJbYUN0XItBwxusX3FhvNqItKVnDz6T0Wt/jygb1/5vuxzGiJt/u6fTuuIC+jTi8vaeqiM0e0jW74/pRVYhflfVZqt2c6GlBf8U9y0a8KTKe/OeEh17HRxta9/e/fr575r/b7rjCqOr8/M79W/swOvOjz99NM///zz008/LeCzRVe3bf47acv5C/n5+fn5F/9aFLpz02/ayP/sPHX27NmTm6e0lRGR7tz3Gw/cYOzm719t1/Xp1/VB0w1UV98hFY0aedy6WcZb3nuWWsEF1HKnyVq2Drz697kqIu2lPXvOWLoyxgUMGNhs5+c/XNMRUWVx8W1Wo1rKrW5LNZqbN2XBoS3dib+yfdtB2y+rt/STM/15V6M7s33z7zcZKzu0cYe2T1+/W2Z1Ge1hs8202Rab7TTbP5GtzA5Dcce1E9j6Ifn5+U2dOtXBpW6RMzavUb80vVeHEp5zD3l4xtbPJrTkSNhJuzzylYx3X506ssu7zI3c20z+aHNM+0Y1/3O3bjOWDUt+9uG9rVo082nWRk7k1n3mstGTn+7a2TM4pn+HcC9PDzdBVVho2EDTNXO2lt/079KPJszJvkGk8+j8wqfD6Y+3jL6O8IkZ8dlzU6b27ljKe3RIWr52hDcV1H73WWHcPa/tZ4u+3Xxq4IwH7+w1WcjIMcEfbfqlMm6wp9EybuHRmhWPdJ9SUBn63Kqveng2D6++gU3Kts023gNNm5Uk9V72TLduzYe+9/NS070d3cFCM9xiUmq10zjfsa8+9tVL8cNCgoKCmwRbHMmRR76yZtbLUwd1fk3u3jjqla/+NyXMfi2s7I+PJlrZlt3/ubdc05GvTF6XMmxMGz+vNt72Ls9b+smZ/ryr7Y3wyIrlI7o/W1DV7rnP1vfwlZnWxTUbZLyHTTbT0g6uEfMouHGm7TTflq6RQuurF3ilnQltRQVr1EhB6r8/HpV0ed7BxX0d1Z+ouzU3ePylT4ZOuvnxvjc7Wxt1BpAwZ0yTkzKm+u6VsYsPazS3NK0mfLC2j+MyXd2tGQCcCmejAACi4J56AABRkEYBAERBGgUAEAVpFABAFKRRAABRkEYBAERBGgUAEAVpFABAFKRRAABRkEYBAET5/y6pMveg40tHAAAAAElFTkSuQmCC",
"image/svg+xml": [
"\n",
"\n"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"experiment meta fit = plot1pass meta fit dataset\n",
"bestLoss = 0.006941823 -- from the R snippet above\n",
"plot meta = toRenderable . experiment meta\n",
"\n",
"-- using the rate from the python snippet above\n",
"let meta@(_,eta,lam) = (bestLoss, 0.721, 1) in\n",
" plot meta $ fitRidge (rootRate eta) (Lambda lam)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"As hinted at previously, it turns out that the value for $\\eta$ coming\n",
"from the bound above is not optimal for this dataset in terms of the\n",
"acheivable a-posteriori performance. Indeed, the bound we’ve been\n",
"manipulating is not tight, and it is in fact so not tight that we\n",
"couldn’t really plot it alongside the regret here without squeezing the\n",
"axis too hard for legibility. Indeed, there exist values of $\\lambda$\n",
"that perform better; see for instance the behavior of $\\lambda=2.5$:"
]
},
{
"cell_type": "code",
"execution_count": 22,
"metadata": {},
"outputs": [
{
"data": {
"image/png": "iVBORw0KGgoAAAANSUhEUgAAAcIAAAEsCAIAAADfNCTgAAAABmJLR0QA/wD/AP+gvaeTAAAgAElEQVR4nO3deUAU9f8/8NfsAQgIcggIqHiiCHihaXnfGmopXl1U1seP/dRKUD9lKZL2ScmjrKTMSr5+KgUttTRT8SyvPKG8FQ9UllVQ5Npj3r8/Vtdld9mFnYUd3Ofjj1p2Zud9vHZezsx73jscY4wAAMBWEkdXAACgbkMaBQAQBGkUAEAQpFEAAEGQRgEABEEarYApvhteX8JxHMdJ/Z//6Z6j6wM62uz5nVw4jnPpvOAfraMrY2cs76vBbhzHyVrPPKiuUxuHh5BGDTHFrxm7i3V3gPEFv6Vvv+vgCgGA+MkcXQExYXm6LMpxHBHjC7dl7Lg7erR3zRSmVqnkLi41s22xq4W210QRNVNtzmdI8obNU3nOs0Ub7I51E45GH2F5v2bsKWEk8Rs+YXB9jvjCbem/Fz5YWJb5/5rKOE7iM2ZtwYMJC+V7poXJOE5S/+lvbjEiItWVbQsnDogMbVDPtV6Dxh2envrlodv8g00/PLdK+Pm3BWM7h3q5eE/YcC9r1esjekY3b+Tr6eri5hXYqvvomWtO3dPPh+BvZS4Y0zG4fr36oTETFu3MnGdyYlt5iSaNKzjy5RuD2zf2cXdx8fBp1CzqqdhXvzrx4DxPm/t78uj2jTzNF6TNSu7ownGcS5f/ntYSEWkOzwqXcxzn2u/z6zwRkcZSQ8y3vcRK5bU3d3wQ1yHYs55XaMyERXsUFk/lbSvCcvfask0LnVz5Ilbw25xRw4cPH/mvb89oHnyzcrZ+9Er/diHe9VzrNQiNHDBx0e9XVEYtfTvj1wXjuzTxdqvn12pg4k85VT5lr3zjttUfiIjBA/yNlUM8OCLOZ/y689/GenJEnM/YtQW8bnHZ3reaS4m4BmMevFW+980wKRHn/eyafJ4x9YVVIxtJOSJOWs+3oY+bhCPi6kUn7CrgGeNvfTnIlYgknv7+7hwREbk9+71y4wteHCet5xMUEtLQU84REUkCRq/J1TLGWNnx+U94cPpAcR7BIb4SIpJ3mv+3hjErJRop3BQfJCEizsUrMLihp5zjiNzi1pYwxljpkbmd3S0UpDk1r4OciOQxH/6jK/jQzNYyInLp+9k1XVUtNcR82wssVr70aHIXi203Cp0NRVjrXhu2aaGTLSx6WJC01YwDKsaY+vzXw4Okj2pGRMTJQkatvqx5tDLn6uEhl7p5ebpyHBFx9QeuyNGa+1JXZ+O21R8YQxp9iL/x1WB3jojzenbNbU1u6sB6HBHXYMyPdx4kJdXBma1lRJzP2HUFjLHyfW81lxJJfMetK+AZX/DTC4ESIklA7GfZRTzTKvckdnDhiHPttvCMRv9tJk7a+JlP9l5W5F3869S1srO/r9t7sVDNGGNMffOXf7WUEXGufZZf0TK+IH28n4SIpCHPfnH01p2ru+f1biChR/u5lRIrUh/+TxsZkSzyncOljDGmKbpyaP2K9afUjPF31o71lRCRtMnYlSfyCq7tnd/P17CgR2m060dnzKdRjYWGmG37yax0C5XnC9LH6aoUPHL5oeuKS9vf6+FdoUrGsbOlCMvda8M2LXSyhUVGmY4v2PB8gC4cY1aeyC9SHP38mWApEUmCJ24pMqhV/R7zj9zVqi59NtCTI+LchnytMP3Xs1obt7H+gDSqx+d+OcidI+I8hn2TxzPt5WU9XTgirkGcPo+qj70XKSOS+IxPL+TL/5jeQkokCXhx4z3GWPmOfzeSEJHEP6J3//79+/fv369jiCtHxLkN+0bJ6w8i3AasuG5w1FB27Y81H78z5dUXxo+JGz2iSyMpEUmbTN2tYqrdU5tIiUgW+f5x3Ze19LfXggwOl6yUWLF12pxPertyxMkCO496PWHe0lUb9p0v1OUj1a4pjaVEJIuee+JBQdteDzJ7NPrEwrPm06ilhjBzbbdc+fKHbY949y9dlYp/eblhFY5GbSiisu61YZuayjvZQv8bZbry7ZMaSYhI3iE5S7fCgxRG0mZv71Ppa+U9Lv0eY4xpsj7oKCcieacPsi30TFU2XmZb/YExXNPW4W9szthXyojk4VEht/7OVmibRDeX7jujubs9fVvB2PG+HJEsetzYqIXZx+/+vmHH7eCDm3K0JGk04rkB9YlIe1tZyIiIV/6zZ+c/FbZcWFDIyFP3h6RRZGTAw+vRZccXDuz37v5Co4uZrLysnBFfeKeAJyJpo9BGUiIikgWFBEjo1sO1rZXoZ3jmJmny0vz3f5kwf8f1oxtWHt1ARJzEK2rymm3Lh/sU3inkiUgaGBz0sKBgw4IMavbw/zyr8IM2FhvyqA4GbbdceW3BbV3bQ5qG6qrk0rhpIwnlm7/sa1MR1rrXhm1ylXdykIVFFYvT3rldyIhI0igkSFeqJCgkSEJniL+jvKOvnaRhaIgbERG5uroQETGtVmv1R4Ysb5xsqz9nqUQngSEmIiLib27O2F/GiEh9bOHg9lFRUR1GfX5GQ0Ts3o70bQ8GlaRtx47r5MLxhdt+XLR6Y46WpKHPTujjTkQk9fVvwBFxrv1X3Kh4JFj+x/QWj3pZJtf/w6Xa9+WyPwt5Tt5uyubLRRrGK74e4qpfUdLA10dCRNq8G7d0wyvqm9fzDHbyqpaowzXoMfv3S7ln/tj8v9SUd+OfaMjx906t/O//LvESHz9dQbdyb+oK0ty8oaiQTaRSXaZRlZUTEVH5jWuGGc1yQx4xaLvlysseVOnhPyVErOBOYVV+iazqRVjrXhu2Kam8ky30v1FpUl+/BhwR8TdzH6R0/pbulcTX3/dRWDnJg/TFcVXPY1Y2bo/6OyekUSIi/samjD/KzO+n7N6O9N/uPMijrcaM7+rC8QU/L/vmgoakYaOf66E7JpDHDO7vLyGm2vfp3J9yyoiINHcv7Fo1c9T/+yHf/Ia19wqLGBG5tOj6ZFNPqebqpp+PPBr5lLfv/VQDCZHm7+/+m3Yqv/D63o8/Wm+YvKpVIruz79svNv6tatIt9rlJickfvtbFnSPi794p5GXtez3ZQEKk+efb+V8fvXH7yu6UjzIqpFFJw0YBUo5Ic2HPrstqVnzyi+Vb7xqUYLkhZlmuvKx9r+7eEiLNqbVpR4qIeMWW7zbnVvO2e8tFWO1eG7ZpoZMtLDIpYlBfPwmROuvrD749dbtYeXzlh2nnNUSSgL4DOsir1wem9be0cZk96u+k7Hd9oA67+nm/ehwR59brk8uPrlxq/lnQWU5EnNczax5ebNQ+WJWISNbmP4dU+rXVF755JljGEREn82gY3MjXXcoRkevglXm8yYCpblMrh3pzRJzUJ2LgyCHtA7083DkikgS+vq2cmQ4luwc18pEQkbzzggcD5pZKrEh7dXkfFyJO4lK/YUgjH1cJR8RJm03ZWcwYKzMdFvepcCFSeyV1kBdHRMTJPb09ZLJ67q4c6a+NWmmIubZbq7y+Spyrf/Pwxt4u9eq5cWT12mi1irDSvdXfpoVOttT/JoPpZ1OHBRgPpksbjfzmosZMrTTnU7rJiUjWPumkmQGf6mzcxvoDYzgaJSLatP7PMkac21Pjnm3yqEekrUeP6SjniBVlpm+9rTv8koQ+O6G37v4XWdux4zo9OjyQtXhl7YGtKf8a3L5xfb7wdpHUr2XM0Fff+2TWIB/zZ12Sxq98/eP7IyIbuty/dDTrfuf30hf0NTwXdu3wzk8bk0e3D3J39QzuGPfB+i/G+3FEJGngoxu2rkaJnHeXsa+P6du+mZ+8RJFfLPdv2X3MOz9uXdTPnYhcO73780/zRkU/KGjBT2mvh0kr1LTJxK/SEga28nWTu3q3GPb+hrRJTQ1WsNYQsyxXXl+leqzkvjTytW//763q35pupQhr3VvtbVroZIv9b1xE60nrD/z8wUt92gbVd5W71m/Utm/8gs1/rH2ludR05Wr3iYWN26n+TsnReRwqpbl8YHtWvu5IiC86/e24JlIiTm7+sMOe5eoHf80e+j0uHNW98PjBSL14aY4uHTEmQ1vfP9BHfj/vZmEZzzi3iEkLp0QhanaA7gV7wUm9eEnDh7w4rHMTd5XyhqLUNahNz3Gzvt2//5PBfuYvEkD1oHvBXjiGR9oBAAiAo1EAAEGQRgEABEEaBQAQBGkUAEAQpFEAAEGQRgEABEEaBQAQBGkUAEAQpFEAAEGQRgEABEEaBQAQxJFpNCkpieO4pKQkB9YBAEAgq2mUKTOThkSFtw2PGjR7u4JVYZH6n5Qenm69P71q7fkCSUlJjDGkUQCo06yl0dLd897Y3uv7k6ezMoYemDpne7G1RdpLq97fFdq3iR1+qRsAoA6wkkbVJ7dmBowe386NXFqPH9s0c8sxtcVF/I0f3vu5/dxJrZFFAcBJWEmj/M3risDQIAkRcb4hQUXXc1UWFjHl5ve/CXpnekerT+IBAHhcWH1eguGvOjNGxFW+6H5m8lJ6c30vT+5Alco2esJ2YmJiSkqK/k+FQqFQKPR/BgQEBAQEYKndl16+fLm4uNi2z2Iplj5mS4uLi5s1a0bVZflRTaoDMyJ6Lr6gZYzxuSsGtpq2R1Xposyj87s3Cm7atGnTpkFecjffsJGpl7SVb5oxq6VDLcjKynJ0FYAxBEIcbIuClZN6efshffLWr/27jFRnf1x3pc/QznI+79iWvRdLTRd17TT7zxu5OTk5OefXv9ai+9w9GyY1w22pAPC4s5bn6vVN+rzf7vHtWkWM2vLEp8mDPEhzMnVS0lYlb2YRAIDzceQj7TgOD9RzvOzs7MjISEfXAhAIUbAtCg4+68YsJoczvMQODoRAiIFtUcDRKACAIBgDAgAQBGkUAEAQpFEAAEEwxOTsDCd1gAMhEGJgWxSsTgatWRhicjiFQoExYjFAIMTAtijgpB4AQBCkUQAAQZBGAQAEQRp1drgeJxIIhBjYFgWM1Ds77L0igUCIgW1RwEg9AIAgOKkHABAEaRQAQBCkUWeHyTMigUCIgW1RwBCTs8PeKxIIhBhgMigAgAPgpB4AQBCkUQAAQZBGnR3u+hYJBEIMMIsJbIG9VyQQCDHALCYAAAfAST0AgCBIowAAgiCNOjvc9S0SCIQY1O1ZTEqlMjU1ValUOrY+Tgh7r0ggEGJQt2cxpaWlJSQklJSUTJ8+3bFVAgCoFgenUb34+HgPD4+4uDhHVwQAoHrEkkb9/PwmTZrk6FoAAFQbhpicHe76FgkEQgwwiwlsgb1XJBAIMcAsJgAAB8BJPQCAIEijAACCII06O9z1LRIIhBjUyVlM4HDYe0UCgRCDOplGMVIPAHUdRuoBAATBST0AgCBIo84Od32LBAIhBrZFgXPgaTXHObJ0AAC7wBATAIAgVtMoU2YmDYkKbxseNWj2dgWzuKhsz/s92jYLC2vSOLzvm+mX1NaLZ4whjQJAnWYtjZbunvfG9l7fnzydlTH0wNQ524stLXLpOGXDsUs5OVfPb4o9NT1pa0mNVh0AQAyspFH1ya2ZAaPHt3Mjl9bjxzbN3HJMbWGRxCswoB5HRLxGw3MSDF/VBbjrWyQQCDGokdvv+ZvXFYGhQRIi4nxDgoqu56osL1LtSOzUKjioe1qbT+YPdbehQlDLsPeKBAIhBjX0LCbDoXTGiDjLi1wGfHzs/KK7R1MmvPnZn4M+6ulheesc92h7iYmJKSkp+j8VCoVhkwICAgzvRcBSey0louzsbLHVygmXkkEgxFMrZ1tKtmEWqQ7MiOi5+IKWMcbnrhjYatoeVRUWMaa9uKRXu5mH1BY3brV0qAVZWVmOrgIwhkCIg21RsHJSL28/pE/e+rV/l5Hq7I/rrvQZ2lnO5x3bsvdiqZlFUsXfx66UMCL+3ol1my40bR0qtTG3AwDUGdaGger1Tfq83+7x7VpFjNryxKfJgzxIczJ1UtJWJW+6iN35c9HIiJDgkNB2L+7q9OmnLwZzVrYOjmd0gg+OgkCIgW1RwCwmAABBMIsJAEAQ/FAeAIAguEUeAEAQpFFnZ/u9cmBXCIQY2BYFpFFnh71XJBAIMaiTaRRDTABQ12GICQBAEJzUAwAIgjTq7DB5RiQQCDHALCYAAAfA0SgAgCAYqQcAEAQj9QAAguCk3tnhrm+RQCDEoE7efg8Oh71XJBAIMUAaBQBwAAwxAQAIgiEmAABBcFLv7DB5RiQQCDHALCYAAAfA0SgAgCAYYgIAEER0Q0xKpTIjIyMuLs7f398hVQIAqBbRndSnpaVNnjw5LS3N0RVxFrjrWyQQCDGwLQoOPho1FR8f7+HhERcX5+iKOAuFQoExYjFAIMTAtiiILo36+flNmjTJ0bUAAKgqDDEBAAgiuiEmAIC6RXRDTFDLcD1OJBAIMcAsJgAAB8DRKACAIBhiAgAQBENMAACC4KTe2WHyjEggEGKAh4iALbD3igQCIQZIowAADoA0CgAgCEbqAQAEwUi9s8PkGZFAIMQAs5gAABwA10YBAARBGgUAEARDTAAAglhNo0yZmTQkKrxteNSg2dsVzNIi/sqG6YOjwkJDQpp2iEv5s6AKlz0ZY0ijjoW7vkUCgRCDmrn9vnT3vDe29/r+5OmsjKEHps7ZXmxpkSSwf9LW09dyrxxM8lo56eNjGhsqBLUMe69IIBBiUCNpVH1ya2bA6PHt3Mil9fixTTO3HFNXvkjb+Kmnu4fW40gW1LNn69s3bvE2VAgAoG6xkkb5m9cVgaFBEiLifEOCiq7nqqqwSH3mu7Tzg57pLre5WkqlMjU1ValU2rwFAIDaYfX2e8MbOxkj4qwtYncy/xO/JnzJbyN8DdatBMc9WicxMTElJUX3Oi0tLSEh4dKlSy+99JLunYCAAMM7YxUKheHhN5bavJSIsrOzxVYrJ1xKBoEQT62cbSnZhlmkOjAjoufiC1rGGJ+7YmCraXtUlhfdP7qof+SzX58tt7xdxnQ33le2SH80WoXNgCB5eXmOrgIwhkCIg21RsHJSL28/pE/e+rV/l5Hq7I/rrvQZ2lnO5x3bsvdiqblFqvPfvBS/tf+3aRNbu9iY1R/QPa3ez89P2GbAOqMjU3AUBEIMbIuC1emYLH/HnOff/P5yuWvTMUvXLBgcpPn9Xy0+iv5zx5TGnNEi312Tw4akqQJ93IiIXAcvP7nqWU9LZWMyKADUfZhTDwAgCGYxAQAIgh/Kc3YKhQJX5cQAgRAD26KAnyZxdrbf5AF2hUCIgW1RQBoFABAEaRQAQBAMMQEACIIhJmeHYQ2RQCDEoIZuv69BuG8UAB4DuDYKACAI0igAgCBIowAAgmCk3tnhrm+RQCDEwLYoYKTe2WEOokggEGLweE4GxdNEAEDkxJ5G09LSJk+enJaW5uiKAACY5+CTeqvi4+M9PDzi4uIcXREAAPPEPsSEp4nUNFyPEwkEQgycehaTUqnMyMiIi4vz9/e3ywYBAKpI7NdGq0h/CRVDUgBQy8R+bbSK9JdQV69enZCQUFJSMn36dEdXCgCcwmNyUq93+/Zt3dk9LqcCQO0Q+xBTdWFIqroweUYkEAgxwCwmsAUmz4gEAiEGj+csJgAAkaszaRRD8AAgTnUmjVZrVihyLgDUmjozxBQfH5+amhofH1+VlTETv+pwPU4kEAgxcOpZTEZw2xMA1JrHM43qYZIoANS0OnNt1DY4uweAmvaYTAatDH5nDwBqWp0ZYrINJjVZhckzIoFAiAFmMYEtMHlGJBAIMcAspkrpbyPF/aQAYHeP+bVRnbS0NN2v5xERfkYPAOyrjqVR/Q1MRFT1O5kMB5ow4gQA9lXH0qhtx5W6gSbda/0L0MH1OJFAIMTAtig4OI1yHDd37tyqD9bb67gSt+XrYe8VCQRCDDAZtBqWLFmSkJCwePFiXCQFAIHq2Em9EZsPKnFbPgDYS92+4cnmuZ64LR8A7KVup9Fq/XqeKdxGSpg8IxoIhBjYFoW6PRlU4EElfriEsPeKBgIhBjWURpkyM2lIVHjb8KhBs7crmMVF2jPfvNyzbaC7a8fkLG2VimeM1eicesv0B7NVPCzF0SsAmLKWRkt3z3tje6/vT57Oyhh6YOqc7cWWFnF+XSYu2fjTrE51ZOBKfzBbxcNS/WrIpwCgZyXhqU9uzQwYvbmdG0lajx/btPeWY+pBPeWVL4rq2VB7ZidHqlqouh0ZDdxXdgOAfrXVq1cnJCTk5+c3bNhQvxruRQVwTlbSKH/zuiIwJkhCRJxvSFDRjlwVkdzaojpHP81Jlwrz8/PnzJljOkVKv5ounyoUismTJ+tX08+weumll+pQPsVd3yKBQIhBDc1iMrw/njEirkqLqorjHn0oMTExJSVF/6dCoTC83BsQEGDYwhpaqkuFU6ZMmTNnTteuXfft23fw4MFXXnlFnxD1n33qqacKCwtTUlJ0l1YzMjJiY2N5nu/ateuiRYtSUlIuXbr06quv7t69W59PHdIiq0uJKDs7W2y1cs6l+hVEVSunWkq2YRapDsyI6Ln4gpYxxueuGNhq2h6VtUWa0//tHjPvlMbyhplu/pL1lWqX/qKn7s/FixcT0eLFiy1/ymg1/Uaq+HEAqNOsJbKSnW+0fnLBqVJWfnpx39avb73PtLeO/rrnQom5RYyxOp5GjegS4tmzZ1esWJGfn295NX3ytfzx/Px8y1sDgLrFaiLjFdvfGxjRvGWLtv3/89tNLWPl214P7bv8qtbMIu31VaObhQR6u7p4BYaEjfr6mtZy2aJPozoCDyqNPq7/U59PkVgB6jQn/WmSahH41Hv9xxljGRkZ/fr127Vrl364X5dVExISkpOTDcf9a40Cz64QBwRCDGyMggNTuK4Cc+fOdWAdalNll1B1L5KTk6niUWrt1CorK6t2CgLLEAgxsC0KeKRd7TG6O9Xox6Rv374dEBBQ2U2pACBadWS+0WPBMG9aWGp0U6r+LlSqznNTAKDWII2Kji6fGh2c6p+bgqNUALFBGhUpo4NT/XNTTI9SjaaiUjUPWjGsIRIIhBjYFoU69iwmJ1TFS6hGD/ur+kEr9l6RQCDEoE6mUacaYrKLyi6hVvegFdcEAOxF6sAjwXnz5uE41Gbu7u4xMTGRkZHNmzd/7rnn/Pz8YmJi3N3djd5PS0ubNm1aUFBQq1at0tLS9uzZk5iYqP/Ty8srPT09LCzM3d1deJWUSmVaWpq9tmZ3uurpm1xSUmL6p2nlzX7KUW2srDKOrRU4+L5RB5buJIwm+CcnJxv+OWLECDI3pcrq/FezTCdo1USLTGd/Wa6zfjWjJpv9U195/daquFpNtNRUZZXRB9dsh2C+XE1DGnUWRhP/dX+eO3cuJSXF8FdUzKZXqxnKqIgq5hrLe3Vl6VI/T6GKddavpm+y4awHoz9N/4Gp4mrCM1deXl4Vg2haGaMZHLZlW6Oetxo1s02u6dxdWSl22TirWhRMieKkPicn58SJE0TUoEEDvK6h18HBwf7+/ufOndO9r1AoZDKZn59fkyZNiEitVkdFRU2cONHX19fDwyM+Pr579+49evRYsmRJUlLS1atXlyxZUlxcHBwcvHHjRqlUevjw4fXr1x85ciQxMVH/fv369T09Pd3d3bt27ert7d2mTZv169fPmjXrzJkzy5cvd3FxiY6OXrp06dWrVzdv3hwREbFs2bJZs2aZvn/27NmUlJT9+/e/9957Li4uW7duTUpKCgoK2rVr16xZszp27BgfH9+jRw+ZTFaVOo8ePbpjx449evS4evVqTExMixYtdP3g7u4+YMCAoqIimUzm7u6u7582bdp07NgxNjbWz89v5MiRzZs39/f3v3btWkxMTHBwsK7f9G188sknY2JiJk6cqGuLvqVGddZqtZcvX9b3W1BQUGpqakFBgZubmy5Ge/bsWb16dYsWLYze18VOo9EsXbq0oKDAx8fHbJ11bfHy8vLw8Bg5cmTv3r0N66brH/37ly5dmj9/vr5u+joXFRWtX79eHxej9/V13rBhgy5qujbq+/nkyZOGnzp37ty0adP072u12m3btgUEBMjlctNYV/39yvrZzc0tJSXFxcVl27Ztpv1cWlpq+L01er+oqGj58uW6svLy8urqZNC5c+fSw1mheF3Lr7OysiyvExsbe+7cudjYWCIaNGiQ/r9ElJycbPq+4WdnzpyZmpo6depU3Wvd0ZDO4sWLZ86cafZ93Xb69u2bmpqqWyc2NlapVOrXt9ouwzrXTn/q6jZ16lSzde7bt69hv+mOE4loxowZK1asmDFjhtn3p0yZonut7x971dmwboZ1NoyL0fv6uuliqm+jvp+NYq1UKg3f1/eA2VhX/f3K+lm3fnh4uNl+NvreGr2v/9TixYttmwwqip8mycnJycnJCQsLCwsLw+tafn3//n1PT88qru/t7X348OGuXbteu3YtOzt70qRJRUVFhu/fvXvXwnbq16//5ZdfNmnS5OrVq/rPmr5/9erVNWvWvPDCCx07dnR4/9jltVG/jRkzJj09PTIy8vDhwwsWLJg9e3bXrl137tw5ZcoUw/cHDBiwY8eO2bNnv/32219++WVkZGR0dHTN1fPUqVOGMTV6X19n2+pw/PhxXUybNGliNtZVfN+obkbbHz58+NmzZ037uXHjxmb7X/d+eHj45s2bdWXdvHkzMjKy2qlMDGkUHCg7O9uG7w3YheGPhxkGQvd+v379MjMzbf5pMbCBbbsD0qizw++ziQQCIQa2RQFpFABAEGvPqa9hHMfhDnwAqNMwGRQAQBAHH40CANR1SKPOzvZnc4NdIRBiYFsUkEadHfZekUAgxKBOplEMMQFAXYchJgAAQXBSDwAgCNKos8PMGZFAIMTAtihgFhMAgCAYYgIAEARDTAAAguDaKACAIEijzg53fYsEAiEGdfL2e3A47L0igUCIQZ1MoxhiAoC6DkNMAACC4KQeAEAQpFFnh8kzIoFAiAFmMQEAOACORgEABMFIPQCAIBipBwAQBCf1zg53fYsEAiEGdfL2e3A47L0igUCIAdIoAIADYIjJ2X3xxReOrvnuVnYAAA3ESURBVAIQIRDiYFsU7HvnJlNmznvhzR+uqFwaxy1ZM39gAGexbNw3KgKIgkggEGJgWxTsejRaunveG9t7fX/ydFbG0ANT52wvtufGAQBEyZ5pVH1ya2bA6PHt3Mil9fixTTO3HFNX4VNKpTI1NVWpVNqxJsKJ+VID6mYzkVdPtMTcb2Komz3PI8p/ei70+2eupI91JyrfHB+2euiFjPEeFsrmOMbYkiVLEhISFi9ePH36dHvVRDgxn2HZt25i3prdibl6qJttxPAFtu/t94blM0Zk8dIoERHHPVglISEhISHBrpURSl83EbJv3cS8NbsTc/VQN9s4vG72TKOSRo0D867f5KmFhN3OveUVEiy3uL5o/30DAKg6e14blbcf0idv/dq/y0h19sd1V/oM7Ww5jQIAPAbsfMNT/o45z7/5/eVy16Zjlq5ZMDgId/cDwONOvFeOAQDqBBwuAgAIgjQKACAI0igAgCBIowAAgiCNAgAIgjQKACAI0igAgCAOSaNMmZk0JCq8bXjUoNnbFbhvtTapMt8Ire8fGhoaGtokOmGXihCOWqU9883LPdsGurt2TM7S6t4y7X9EpOaZBkLIrsFqX0nmlPAnF5wqZeVnlvQNn7TtvgPq4LTKd05u9fyGMoN3EI7apFWc2nv47B9J3WLmndIwxsz1PyJSC0wDIWDXcMDRqG0/Swo1BOGoVZKGUT27tPB11f8kkWn/lyAitcAkEKaqvms4II3yN68rAkODJETE+YYEFV3PVdV+JZxZ6dZpkc3C2vR46ZMDBQzhcDDT/i9DRBzF1l3DMddGq/uzpGA38s6z91+4dP7ymW0zPVc9/86OEoTD0Uz7HxFxBAG7hgPSqP5nSYmq9LOkYE+cd0hTHzmRW9Nhr8Z6Zp/IZQiHQ5nuDq6IiEMI2DUckEbxs6QOxAoun1eoiEibv2/ttsKWbYLcEA6HMt0d3BERRxC0a9T0gJg5vGL7ewMjmrds0bb/f367qXVEFZyVJmv5iLahjYKDgxpHjZi77YaWIRy1Snt91ehmIYHeri5egSFho76+pjXT/4hIzTMJhErAroHfGwUAEASzmAAABEEaBQAQBGkUAEAQpFEAAEGQRgEABEEaBQAQBGkUAEAQpFEAAEGQRgEABEEaBQAQBGkUAEAQpFEAAEEc8ev3it0LJzzRpmV461aR/SZ/e+q++dWY4uunY+ac0Dx6UT1318T1XvTP4fe6v7ypvJItG1bq4uI+/T/J4YVtGSy499MLDV07fZCttc/miv5as3JPVR73VsXvj41fM7uwd1tMGH+9+WufDXzyw9OWQ2GxVlXaQrVVuhvqGm7fwuyo1tOo5vSyMa9mdv7i0Pmz505vn+X22ah/r7f8BeJ8hqeseq2VzE4VYFq+gV03aK4IbbV+Nqu669fm1uym8Pf0g6268D9nZNslU7Giv9Z8vSfP6r97VQx3LXwrLBRuti3m4mjnfcGGWoE5tZ1G1YdWpt59YeFbnb05Ilmjwclzn9rz2Y9XeP7aZwOi46ZOGjtq6JMxQxf8WfToG8QKNs+Y+PV5DZlbp+zs/yb36xAVFdmu23OfHzc8sJW4NfD1kMk9fb1dOdJ9dtQbr4waMWzKD9kbdRskdvfPhbHtWrbr3GvC8uMlRESs8I//Ph3ZKjKm9/i3Xuja/5Mc3rSIilvWMyzix9wS40+ZbFljcX2Wv332wOh2HTp3at/13xuUfMU/GSv6a/mELuHhbVpHDZn92y3eqHTRfffZnd/WHe0567MXPDamnzLJo/y1zwZEDp/4UlzciN5Pjliwv4CRSQMrdMj685s/Wn7kzLev9u8z6P2dpSYxqiTcljrt0WoPabPndxv8RS5PRNqzC3s8DJnRN7D0dNq/e0dGRHdo32X8V+e0lZVS4VMW2lJsGMecA4tin+rSqX3bNl0mrDhZUt19wfTrbRiRsqwVL/aKiWzZbtiC/QWM1IcqlMUKfqnQwybNJCLV2dX/6tcpvGnrgRV2WP7aZwM7v5j4Uu/2rcKin/vm4M75o7pHNg/rNn2r7unRxv1jrp6V79fiVGs/k6pz68tBDZ//uVT/tzbnk94hr/1Wrr26vI9v/+UX1YyV7nkz8pk0pTZv5bDO7x9XM/7hC9N11P8s7Dd4UXYxY6zkZHLP3h+f01RSrvbq8j7ePRefVTH2aIPqY+936DB9byHP3zvwn/YePZddLj/6XseYdw4WMXb/r7kx9Xsuu6yyqQiNyafKTLastrT+2VurYqNnHihnjPGlRUWq/Ap/qtXH53SMnrbzNs9Kshb1afnypruGpYsPn79mVOuJv97XXFzaJ/o/h40rqb26vI/Xk4tOlzOmOru4b+d3/yo1bmChUQ/wuSsGd33waFzT3laZDbfFTtOvpqfJ+uCJQZ9f1zLGNGc+eqqfLmRG38DsBU9EvLbploYxVnbnTjFfSSkVPpWvqLwtFeLI37t9R8UYY/cPv/vkiFW3+GrtC2UmX2+tYYd7RM/84y7P3zv4Tpf27/6lNi3LsIdNmqm9uryPV9e5R+7x/J2N8a2eSVPyhhv37pZ87D7T5Hw+wL/Z82lX1Kzkz8ToPksvac30j+luaLrTqfNWDuv8vh2/kfZl6fRAqVRmZGTExcX5+/vba6np6ab+HVnL3n2ayoikLcNDFNcVZg+oKq6Tl1ey88SZO28M+5UjotLC4j43eGolraQ50pb9+jc3fAoAUxw8pB38QXdvjqOY8SPbHCKmOHSYH7igsycRdRg9vM1eYvl7bSjC9FO5t4y3bHn9m/X7dvP4aPpr0nFPDxsZ2yPMu4Phn00VBw6qBs3r6csRRUyICxu6/7Smg2kDbZSTk5OTkxMWFhYWFlbd1+a3yPJ/Tf+7zxt9PKRuz47yj133V3KX7kYVlbbsP7ClCxG1GNRXNv3AqWCjBp7xGFehQ+iewdbNxMhcuO3RaUbfwFvFe+8NnTskUEpErj4+ROyGuVIqfiq//uDK2qLriodV0hYcWDbj4+3XtS7S25fyY3O01KzSmpjsC7m3jL/eFUtpFTu2qxfHUedxw+SJB2+pG540KquxQdftM2om8UTS1sNGdajPcXznrs0WXlfw5KffL2Sth4yM9iCpS/so/8jopxvLiIvs0FJx/KaWuRr3zz83wox3Q7MBFTNLJ/VpaWmTJ09OS0uz41K/iHYNsv46rT91Kj5x9GKrqHAZEZFUqguDRCLh+Uou71Vch2fMZ3jK9t27d+/evfvQqSMLe1vYITgXFxeTJ/vJ5Lp/SDiZi/l/UWwrooqfsrC+e6fZu/envtBW/cfcQf3nn+Aq/qkhVvEphVxlDbTBd99917dv3++++86G12axvF/W7b6x8fWIsLDmvReeuPzTukMq7T9Lh7Zp2bJl2zFfX+GJiDRq3UPAmUatZkQmDZQb98AjZnvbXG9Us9MkHMfzuh1Yq304mGL9W2qmFKNPWWiLYZVKts6dfmrwd7v/2Lt706wnJBqja6VV2Besfr31rJRlDieXyzki4qRSqXFXyOS6L7xEKn2wlkQqYbqVzPSPUT2rtdOJgaU0Gh8fn5qaGh8fb8el8m6v/cvr/2YtOVLIE6lzt8xO2t9j8rimtl2i5QJ79W/46+c/XlYRkbbg9MlLpdX6eEC3btJ9mRfVRJqcnTvOaokLeKILt33D0SJGxSfW/3JGY2MRpp8qM9mylYaU5F667RU96MXED6f3UJ46e7vCn+fqd+/usu37fXcYlf79fUZOl55t7Tjq8PLLL+/atevll1+24bVZNzelnxu//vKVnJycnJyrxxeGbV33pybi7a1nLly4cDr9taYSItJe/GXtwbuM3Tv8w6/aJ7pHP2XcQFXFDimtV8/1/r0i3nzvmasFF1DNTpMENg66ee5iOZHm2p49582NjHEBvXp7b/3mt1taIiq7fbuYVamUkkrbUoH63j1JSFigC/E3ft10yPLD6s195Yy/3hVoz/+afvgeY0VH127RPNHN775JWQY9bNJMi3WxWE+T/okINtkNhe3XDmDpi+Tn5zdp0iQ7L5VFTE9fpZr2RpcWBTznEjpg+oavxgRyZNtBuzTirbQPZ0yKbfchk5FLkwnL0ts3r1f1j8s6TP9kSPyrA/YGN/T28W4iJZJ1TPhkxISXo9u6hbTv2aK1h5urzKYizFSst/GWOUvrr/t34bIxczLvEmld2075Yigdec/gz2E+7Yd9NfG1SV1bFvKuLcYvXz2sPuVWv/sqYXh6Xt3XZm1MP9N7+lMPek0SGjsyZNm6/WV9+rsZrCNrHaX+/OmOr+WWhU1c+UMntwatKzbQs2jTbMMe8PIuGN/1k1c6dGgw+L+7lhj3dlQLM9WQtU+sVqdxvs/OeO6Haf2GhDZqFOIZYvZKjjTirVUz35zUt+0sqYt75Fs//O+1VtZLYUVHlo2tpC073360nlfsWxPWJA4Z2cTPo0l9a8Pz5r5yxl/vCr3ROqJ0+bCOr+aWN5v41fedfCXGZXHefQ172KiZ5jq4SkyjIOOM62nalugIW8urFXiknRFNaSmrV09OqnOfDh9/fd6hRd3sdT5Rc1uu8/hrnw0ed+/Tfe+2reyqM4CIOeI2OTFjys1vPbvomFp9Xx085uPVT9gv09XclgHAoXA0CgAgCObUAwAIgjQKACAI0igAgCBIowAAgiCNAgAIgjQKACAI0igAgCBIowAAgiCNAgAIgjQKACDI/wc++BjdsRB9wAAAAABJRU5ErkJggg==",
"image/svg+xml": [
"\n",
"\n"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"let meta@(_,eta,lam) = (bestLoss, 2.5, 1) in\n",
" plot meta $ fitRidge (rootRate eta) (Lambda lam)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Note the role the $\\ell_2$ ball\n",
"plays here. Make it too large, and the initial iterations become\n",
"jumpy enough to degrade the overall performance: "
]
},
{
"cell_type": "code",
"execution_count": 23,
"metadata": {},
"outputs": [
{
"data": {
"image/png": "iVBORw0KGgoAAAANSUhEUgAAAcIAAAEsCAIAAADfNCTgAAAABmJLR0QA/wD/AP+gvaeTAAAgAElEQVR4nO3deUAU9f8/8NfssoAiKocIgooHoAii4lmpiIlHHqmo2EWHffzot+ujZIclalopaZmZfFIr+fkxD7Sy1Iwk1EqtNBW8UhMPVJZFUJRjj3n//lhdlz1hZmEH9/n4p93ew7zfM6+dl/N+z3tmOMYYAQCAUDJnNwAAoGFDGgUAEAVpFABAFKRRAABRkEYBAERBGq2GKb8c5S3jOI7j5P6Pf33T2e0BPV3egh7uHMe5xy48oXN2YxyMFX421JPjOLfwWQc0DWrlcBfSqDGm3J6Zc1s/A4wv+WFz1g0nNwgApM/N2Q2QElaoz6IcxxExvnRX5k83xo9vVjeVadRqhbt73axb6uph2+uiirppNuczbP7W717kuSYdOuFwbJhwNnoPK9yeuaeckcxv1OSh3hzxpbs2/1h6p7Ay+//aunGczGfCxpI7NyxU7Xkp1I3jZN6PfH6NERGpL+xa9NzDUSHNG3k0at662yMv/vdgMX9n1Xf7VjO/+WHhxNiQpu7NJm+9mbvm+dH9u7YP8m3i4e7ZtGVYv/Gz1h27abgfgr+WvXBC91bejbxDek5evDt7nlnH1nqNZhtX8sd/pw+Nae3T2N3dyyeoXfSDI5/97Midfp6u4Mf542OCmliuSJc7v7s7x3Huvd47qSMi0v7+WoSC4ziP+BWXeSIira0Nsbzt5XYar7v60zuJ3Vo1adQ0pOfkxXuUNrvywqqwvXuFrNPGTrZexEp+mDNu1KhRY/71xSntnV9W/s73nxncJbhZI49GzUOiHn5u8Y8X1CZb+p/M7QuTerVp5tnIL2xIytf5Ne6yW1+5sPYDETG4g7+yapgXR8T5JG0688XIJhwR5zNxYwmvL67c+0p7ORHXfMKd/1W19+VQORHXbOy6Ip4xzdk1Y4LkHBEnb+TbwsdTxhFxjbrO/LmEZ4y/9t8EDyKSNfH3b8wREZHn2PWqb59oynHyRj6BwcEtmig4IiJZwPh1BTrGGKv8a0EfL84QKM6rVbCvjIgUPRYc1zJmp0YTpduSA2VExLk3bdmqRRMFxxF5Jm4sZ4yxij9SYxvbqEh7bF43BREper57Ql/xwVnhbkTkPuiTS/qm2toQy9teYrPxFYfm97K57SahE1CFvd0rYJ02drKNorsVycNe3a9mjGnOrB4VKL/XMiIizi143Nrz2nsLcx5eXgq5Z9MmHhxHRJz3kJX5Oks/6tqsXFj7gTGk0bv4K58NbcwRcU3HrivWFqQPacQRcc0nbLh+JympD8wKdyPifCZuKmGMVe17pb2cSOY7aVMJz/iSr59oKSOSBYz8JK+MZzrVnpRu7hxxHn0XndIafs3EyVs/umzveWXhuT+PXao8/eOmvedKNYwxxjRXv/9XRzciziNu+QUd40s2J/nJiEgePPbTQ9euX8yZN7C5jO4d53ZqrE7z++ud3Ijcot74vYIxxrRlFw5uWbnlmIYx/vrGib4yIpK3mbjqSGHJpb0L4n2NK7qXRnu/f8pyGtXa2BCL2340d7ONxvMlmyfpm9RqzPKDl5X/ZL31ULNqTTKNnZAqbO9eAeu0sZNtFJlkOr5k6+MB+nBMWHWkqEx5aMWjreREJGv13I4yo1Z5P7Tgjxs69T+fDGnCEXGew1Yrzf/1rNXKBbYfkEYN+IL/JjTmiDivEZ8X8kx3/qP+7hwR1zzRkEc1h9+KciOS+SRtLuWrfp3RQU4kC3jy25uMsaqf/h0kIyKZf+TAwYMHDx48OL57sAdHxHmO+FzFG04iPB9eednorKHy0q/rPnjjhWefSJqQOH50ryA5EcnbvJijZuqcF9vIicgt6u2/9D/Wih+mBBqdLtmpsfrW6fKXDfTgiHNrGTvu+ZnzPlyzdd+ZUn0+Uv/8Qms5Ebl1TT1yp6JdzwdaPBvts+i05TRqa0OYpW233fiqu9se+eaf+ibd/v7pFjU4GxVQhbXdK2CdWus72cb+N8l0VVlTg2REpOg2P1e/wJ0URvJ2/9mnNrSq2aTNNxljTJv7TncFESl6vJNnY8/UZOWVwtoPjGFMW4+/8l3mvgpGpIiIDr52PE+pa9O1vXzfKe2NrM27SiYm+XJEbl0nTYxelPfXjR+3/lTc6sC2fB3JgkY/9rA3EemKVaWMiHjViT27T1Rbc2lJKaMm+i+yoKiogLvj0ZV/LRoS/+YvpSaDmayqsooRX3q9hCcieVBIkJyIiNwCgwNkdO3u0vZq9DPuucnaPLXg7e8nL/jp8qGtqw5tJSJO1jR62rpdy0f5lF4v5YlI3rJV4N2KWhlXZNSyu//lWbUH2tjckHttMNp2243XlRTrtz24bYi+Se6t2wbJqMjysK+gKuztXgHr5Kzv5EAbRdWr010vLmVEJAsKDtTXKgsMDpTRKeKvq64bWidrERLsSUREHh7uRERMp9PZfciQ7ZWTsPZztmp0EbjERERE/NXvMn+pZESkObxoaEx0dHS3cStOaYmI3fxp8647F5XknSdO6uHO8aW7Nixe+22+juQhYyfHNSYikvv6N+eIOI/BK69UPxOs+nVGh3t72U1h+IdLve+/H/1WynOKLi98d75My3jl6mEehgVlzX19ZESkK7xyTX95RXP1cqHRQV7TGvW45g/N/vGfglO/fve/9LQ3k/u04Pibx1a9979/eJmPn76iawVX9RVpr15RVssmcrk+06grq4iIqOrKJeOMZntD7jHadtuNd7vTpLv/lBCxkuulNXkSWc2rsLd7BaxTZn0n29j/JrXJff2ac0TEXy24k9L5a/pPMl9/33th5WR30hfH1TyP2Vm5I9rvmpBGiYj4K9syf620fJyymz9t/uH6nTwaNiGptzvHl3zz0edntSQPHf/YQ/pzAkXPoYP9ZcTU+z5O/Tq/kohIe+Psz2tmjfu/r4osr1h3s7SMEZF7h94PtG0i117c9s0f9658KmIGPthcRqQ9/uV7GceKSi/v/eD9LcbJq1Y1suv7vvj02+PqNn1HPjY1Zf67U3o15oj4G9dLebeYAQ80lxFpT3yxYPWhK8UXctLez6yWRmUtggLkHJH27J6fz2vY7aOfLt95w6gG2xtike3Gu8UM6NdMRqQ9tjHjjzIiXrnjy+8Kajnt3nYVdnevgHXa2Mk2isyqSBjkJyPS5K5+54tjxbdVf616N+OMlkgWMOjhbora7QPz9ttauZsj2u+iHDc+0IBdXBHfiCPiPAcsO39v5FJ7YmGsgoi4po+uuzvYqLuzKBGRW6fXD6oNS2vOfv5oKzeOiDg3rxatgnwbyzki8hi6qpA3u2CqX9Wq4c04Ik7uEzlkzLCYlk29GnNEJGv5/K4qZn4puXFgkI+MiBSxC+9cMLdVY3W6i8vj3Ik4mbt3i+AgHw8ZR8TJ272w+zZjrNL8srhPtYFI3YX0hKYcERGnaNLMy82tUWMPjgxjo3Y2xNK222u8oUmch3/7iNbN3Bs18uTI7thoraqws3trv04bO9nW/je7mH46fUSA6cV0edCYz89pLbRKeyatr4KI3GLmHrVwwac2KxfYfmAMZ6NERNu2/FbJiPN8cNLYNvf2iDx8/ITuCo5YWfbmncX60y9ZyNjJA/XzX9w6T5zU497pgVuHZzbu35n2r6Exrb350uIyuV/HnsOffWvZawk+lntdstbPrN7w9uioFu63/jmUeyv2rc0LBxn3hT26vfH1t/PHxwQ29mjSqnviO1s+TfLjiEjW3Ed/2boWNXLNek18fsKgmHZ+inJl0W2Ff8d+E97YsHNxfGMi8ujx5jdfzxvX9U5FC7/OeD5UXq2lbZ77LGPmkDBfT4VHsw4j3t6aMbWt0QL2NsQi2403NKkRK78lj5ryxf97pfZT0+1UYW/31nqdNnayzf1vWkX41C37v3nnqbjOgd4eCg/voM6Dkhd+9+vGZ9rLzReu9T6xsXIHtd8lOTuPg1Xa8/uzcov0Z0J82ckvJrWRE3EKy6cdjqzXcPHX4qnf/cJZuxfuP7hSL13aQx+OnpCp8/Zv6aO4VXi1tJJnnGfk1EUvRCNqDoDdC46CTr10ySOGPTkitk1jteqKssIjsFP/Sa998csvy4b6WR4kgNrB7gVH4RheaQcAIALORgEAREEaBQAQBWkUAEAUpFEAAFGQRgEAREEaBQAQBWkUAEAUpFEAAFGQRgEAREEaBQAQBWkUAEAUpFEAAFHsplGmyp47LDqic0R0wuwsJbNTxCt/XjA2pl2bNq07xi86rK2rVgMASIa9NFqRM2961oD1R0/mZg7f/+KcrNu2ivhLX055fl//jNwLFy/8tfaxdg54WjcAgMTZSaOaozuzA8YndfEk9/CkiW2zdxzWWC+qurBl7Ylhr/9fTBOOZN6tW1t5eQYAwP3EThrlr15WtgwJlBER5xscWHa5QG29qPzsyfN+t7Y/1b9rROcHn1r++w08yRQA7n9235dg/FRnxog4G0U8X3XsmOyDn470U++cHv/Me32OvN/bxithTd6wnZKSkpaWZviqVCqVSqXha0BAQEBAAEodXnr+/Pnbt28L+1uUovQ+K719+3a7du2otmy/qkm9/9XI/kvO6hhjfMHKIWEv7VFbL6rInR/bKUX/3teq7c+0euSLYtMX/VZjt3aoB7m5uc5uAjCGQEiDsCjY6dQrYobFFW7ZeLyS1Kc3bLoQNzxWwRce3rH3XIWFIs+IYQmNDuw+UU7sxsHdh7wjwr0xOgoA9zt7V+obDZq7Ij4nqUtY5LgdfT6en+BF2qPpU+fuVPEWihQ9X1sx5s/kru3bd5t+ZuJnb/az0aPX4zhu7ty5jtkUAABncOYr7TgOL9Rzvry8vKioKGe3AhAISRAWBancxaRSqdLT01UqlbMb4nKMh9jBiRAIKRAWBamk0YyMjGnTpmVkZDi7IS4HR69EIBBS0CDTqGFsNDk5OT09PTk52bntAQCoLYyNAgCIIpVOPQBAAyWVTj04i/FNHeBECIQUCIuC3ZtB6xY69U6nVCpxcUMKEAgpEBYFdOoBAERBGgUAEAVjowAAomBs1NVhPE4iEAgpEBYFzBsFABAFnXoAAFHQqQcAEAVX6gEAREEadXW4eUYiEAgpEBYFjI26Ohy9EoFASAFuBgUAcAJ06gEARJFcpx5vEwGAhkVynfqMjIyZM2eWl5fPmDHDKU1yNbh5RiIQCCm4T+5iKi4uzszMTExM9PPzc0qrAABqRXJpFACgYZHc2CgAQMMiubFRAICGBROeXB1mfUsEAiEFdXQXE1Nlzx0WHdE5IjphdpaS2SxSZ08P8fYPCQkJCWnTdebPavvVo1PvdDh6JQKBkIK6uYupImfe9KwBm4++GXHhw2Fj5mQdSk/wsloUR9R4zKrcdWM9alo9OvUA0NDZORvVHN2ZHTA+qYsnuYcnTWybveOwpgZFAACuw04a5a9eVrYMCZQREecbHFh2uUBtu6hi50tR7UI7PfTUsv0lONEEABdg90q9ca+bMSLORpEidvYvZ5e19dFd2DZj1ONvROalD2lse+0cd299KSkpaWlphq9KpdJ4nCIgIMD4BgOUOqrUy8srLy9Paq1ywVIiMgRCOq1ytVIvLy+qPTsT4DUHZnWbFbgtZ0YHGbuSPjTu5FvHlw1Q2Csi0v75Zo9XfLbseTVMbqNuTL8HgIbPTqdeETMsrnDLxuOVpD69YdOFuOGxCr7w8I695yosFLmVnD+jVBORrmjfxl2lHTsF2sihAAD3B3sTnhoNmrsiPiepS1jkuB19Pp6f4EXao+lT5+5U8eZFfMH2lLgOrYKDQ2Jf/nvU6vce8bZbPSY8AUBDh3vqAQBEwV1Mrs54xB2cCIGQAmFRQBp1dTh6JQKBkIIGmUYxNgoADR2e8AQAIAo69QAAoqBT7+qM7+IAJ0IgpEBYFDDhCQBAFHTqAQBEQRoFABAFY6MAAKJgwpOrUyqVuLghBQiEFAiLAjr1rg43z0gEAiEFuIsJAMAJJNqpV6lUmZmZiYmJ/v7+9dwkAIBakWinPiMjY9q0aRkZGc5uCACAHRLt1CcnJ6enpycnJ9d7i1wOLmtIBAIhBbiLCQDACSTaqQcAaCiQRgEARJHo2CgAQEMh0QlPUG9w84xEIBBSgLuYQAjcPCMRCIQU4C4mAAAnQKceAEAUdOoBAESxm0aZKnvusOiIzhHRCbOzlKwGRZoTaQ818Rz48UW+LhoMDobLGhKBQEiBsCjYS6MVOfOmZw1Yf/Rkbubw/S/Oybptr0j3z5q3fw4Z1EZeo+oxNup0OHolAoGQgjpJo5qjO7MDxid18ST38KSJbbN3HNbYLOKvfPXWNzGpU8NrlkWJMYY0CgANmp00yl+9rGwZEigjIs43OLDscoHaRhFTfff254FvzOjuUbeNBgCQDrtX6o0vpTNGxFkvupU9/0N6ecuAJtz+mlbPcffWl5KSkpaWZviqVCqN53AFBAQYn2+jFKUoRanDS0lQv97OM5Y0B2Z1mxW4LWdGBxm7kj407uRbx5cNUFguemNDwOyRn15xVxBVlVwpdQse+m721qntrJ/v4glPUqDEzTPSgEBIgbAo2OnUK2KGxRVu2Xi8ktSnN2y6EDc8VsEXHt6x91yFeVHvHrN/u1KQn5+ff2bLlA79UvfYzKEgEcb/OIMTIRBSICwK9vJco0FzV8TnJHUJixy3o8/H8xO8SHs0fercnSreQhEAgOtx8mObiSg1NRUX650oLy8vKirK2a0ABEIShEUBN4MCAIiCwUtXh8saEoFASIGwKOAJT64OR69EIBBSICwK6NQDAIiCTj0AgChIowAAomBs1NVh1rdEIBBSICwKGBt1dbgHUSIQCCmok5tBAQDANnTqAQBEkXqnXqVSZWZmJiYm+vv710+TAABqReqd+oyMjGnTpmVkZDi7IfctjMdJBAIhBcKi4ORHk9itvbi4WH826ufnVz+tAgCoFTzhCQBAFKmPjQIASJzUx0YBACQOE55cHW6ekQgEQgpwFxMIgZtnJAKBkALcxQQA4ARIowAAomBsFABAFIyNujqMx0kEAiEF9+ddTAAAEtdgOvUqlSo9PV2lUtVxiwAAaqfBdOozMjJmzpxZXl4+Y8aMOm0SAECtODmN1lxycrKXl1diYqKzGwIAUI3dTj1TZc8dFh3ROSI6YXaWktksqtzz9kOd24WGtmkdMejlzf9oHNlQPz+/qVOn4jlPDoebZyQCgZACYVGwl0YrcuZNzxqw/ujJ3Mzh+1+ck3XbVpF79xe2Hv4nP//imW0jj82Yu7PcbvWY8OR0OHolAoGQgjq5GVRzdGd2wPjvuniSLDxpYtuBOw5rEvorrBe11M8W4LVanpPV4PIVrtQDQENnJ9XxVy8rW4YEyoiI8w0OLLtcoLZdpP4ppUdYq8B+GZ2WLRjeuE6bDgAgBXYvMRmfLjJGxNkucn/4g8NnFt84lDb55U9+S3i/v5ftteuf3KyXkpKSlpZm+KpUKo1PsAMCAoxnxqLUUaVElJeXJ7VWuWApGQVCOq1ytVIShtmk3v9qZP8lZ3WMMb5g5ZCwl/aoa1DEmO7c0gFdZh3U2Fy53dqhHhQWFjq7CcAYAiENwqJgp1OviBkWV7hl4/FKUp/esOlC3PBYBV94eMfecxUWiuTK44cvlDMi/uaRTdvOtg0PkQvM7VB/TM5MwVkQCCkQFgV7l4EaDZq7Ij4nqUtY5LgdfT6en+BF2qPpU+fuVPHmRez6b4vHRAa3Cg7p8uTPPT7++MlWnJ2140o9ADR4uKceAEAUPG8UAEAUpFFXJ/zqJDgUAiEFwqLQYJ7wBHUER69EIBBSICwKDeYJT3oqlSozMzMxMdHf37+OmgQAUCsNrFOfkZExbdq0jIwMZzcEAOCOBtapT05OTk9PT05OrrMWAQDUDiY8uTolXo8uDQiEFAiLAtIoAIAoDWxsFABAahrY2KgB3nAHABLRwCY8GeANdwAgEQ21U29yyR4np4Jh1rdEIBBS4Fp3MZm84c4wnxT5tLZw9EoEAiEFLnEXkzWG1y+vXbsWnX0AqE8N5j31tulPTgmvsweAenefpFEDQz4FAKgfDXVsFBwFd85IBAIhBcKigLuYAABEaagTnvRwXR4AnK5hd+qtPTfPkF7rKM8ifQOAQcOe8GTturzhHicicuD8J8NDo3EPFQAYNOwr9dauyxunV+M8K/Lh+YbsaTF913blhuWJyImP9Mfz2SQCgZACgVFgzlP/tS9ZsoSIlixZIuzPDX15/deioqKVK1cWFRUJW7lheZGtEik3N9cp9YIJBEIKhEXByWmUiFJTU+u6IkO+M+RBkwwojEn6q+3KzQdwxTRGMBy9EoFASEGDTKP1U5H56Z5DTgCt5U1hK3dIZhcAR69EIBBSgDRqlfnpnmNPAGt1WmotXRpWYrJAXadXHL0SgUBIQR2lUb5od+rQqPBO4VFD3vyxkLdVpMvf8p+EqLbBrVq1iRm/+NfrvLV13q27vjr11jgqQ1lLyhZPS62dqxpWYrKAtfTqKIWFhY5dIQiDQEiBsCjYS6Pl2S9EPLDwWAWrOrV0UMTUXbdsFOku/vL9b5fKeaa58vUzYVFv/qmxU7dTL3CxGmQokZnLYnq1eyKsX+D06dMm47n61s6fP98pfX8AsMZOIlPvfzWy/5JzOsYYf2VlQtjLe9U1KGK86vNHgp7+vspO3c5Oo9ZOAA0cMoQqLBebV61v7fz58y02yVlDqwBgJ5FVbp3sn7jxtv7ztqcCx391qwZF6hMfxIUnf1Nsp1fv9DRqYG000+TEUNjKheViayetJk01tM3kzFpkmwGg5uxOvze+zYgxIs5eEbue/XryuoilP4z2NVrWCo67t0xKSkpaWprhq1KpNH4SdUBAgPG0WIeX6qfxL126dObMmcePH/fx8RkyZIiPj8/YsWPXrVtnuGdJwJoNc/VPnTq1fv16/Wpr8rfGdxYYlz744IM6nU7fqtGjR2/btk2pVMbHx8+ZM6d3796LFy9OS0vT/3/BbUYpSl2zlIQ95Ml2ltX33M/qGGN8wcohYS/tUdsuunVo8eCosatP2+nPM8akdDZqYLHj7KjL+o6dZq9v1d9//21xEoLh/9u+7l9UVLR48eKioiKMCTgdLjFJQR1dYto9PVx/HenkkkHhz++8xXTXDm3fc7bcUlHV32vGRQ1694+yGtYtvTSqV0fz4Z0yzd6ks2/4F8Lkq7UxgVoNESAXi4EJT1JQVxOelFlvDYls37FD58Gv/3BVx1jVrudDBi2/qDMvqvrp30Fujf2C9do/u9VOOtWfDjtxwpMrML/Qb/J1zpw5xndS6f//6NGjjdOr4athtRbTa13Pzbq/IY1KAabfgy0m58KGrya/G5MxAWtDBCbp1ZBVTWY+IJ/WHNKoFCCNghC1+t0Y8qNJerV2H5fJXFeLIwaOSrJ2J/9KPKcjjUqBsCg07AflgXi1ui5pmHVgeERhWFgYmT341eRFrUqlctq0aYbHvxpmEdDdp8E+9dRTmZmZ8fHx2dnZdh8YaP5AQv3/KSoqmjNnjvnaTB4+W1RU1KJFC8Ofi3x2ogMJuUAMjiYwCg5P5zWnbwDGRu97Js+yMhkxMB+QtX1dy3zEwOKwr2FtJrVbu8hm+2QW83DBBnTqwfksDhGYZFXjMQGTkQSLw77mU8GMS61dczNP4nYbU5/ptU5HRUAwpFGQHGsDr9ZGYMXUYn7NzeLJrLXG1PAM2lEszqPArWtOh049SF09P9+6hieztT2Dtp3gavWo79qOiuCkta7hbNTV4eYZhxB20mo+vCtsSoPtnG773gq7w8G1WqyhnxELOxxwpd7VKfEmNUewMXXBy8srPj5+xIgRiYmJa9eutThXITk5+caNG0Rke0qDtTfRWqzdUCndfbGjxdoNUxfo7qsV9XMbhC1m+KqfL2FYvobTMJxO2OGANArgeMbvrK1JgvPz85swYUJQUFBAQIB58qXqL7itee36Sg1tsFi7yXQ0w4tvhS1m8g+GtfRqyKrk1NfiOozDz4prTt8AjI06F2Z9S4SzAlHDoefajlDXcBDZ7oCDyZBCDRcTrEFOv2fGD9sDgHpnfuIsZjEbywsYcDAfUrA4kmBt5KHeznnRqXd1GBiVCBcJRK0GHMyHFGq4GNXsfjkyy7a4iwkA7k8iRxJq+AAzwc8C5pjzutUc58zaAcDVFBcX2z4b9fPzE7BapFEAAFFkzq2e47i5c+c6tw0AAGLgSr2rw/R7iUAgpEBYFJx8NgpOZ/yiRHAiBEIKhEUBaRQAQBSMjQIAiIKxUQAAUdCpd3W4rCERCIQUCIsCOvWuDkevRCAQUiAsCujUAwCIgk49AIAodtMoU2XPHRYd0TkiOmF2lpLZLNKd+vzp/p1bNvboPj9XV3dtBgCQEHtptCJn3vSsAeuPnszNHL7/xTlZt20VcX69nlv67dev9ajxUAHGRp0Os74lAoGQgjqZfq85ujM7YHxSF09yD0+a2DZ7x2GNjSJZi+j+vTr4enA1rp4xhjTqXDh6JQKBkII6SaP81cvKliGBMiLifIMDyy4XqGtQBADgOux2v40vpTNGxNWoqKY47t4fpaSkpKWlGb4qlUrjfxkCAgKM5yKg1FGlRJSXlye1VrlgKRkFQjqtcrVSEsb2U53V+1+N7L/krI4xxhesHBL20h61vSLtyff69Zx3TGv/kdF2a4d6gFfaSQQCIQXComCnU6+IGRZXuGXj8UpSn96w6ULc8FgFX3h4x95zFZaKBGZycCaTM1NwFgRCCgRGwV6e5ZVZbw2JbN+xQ+fBr/9wVcdY1a7nQwYtv6izUKS7vGZ8u+CWzTzcm7YMDh23+pLO5qprUDsAgNQ5+SUiRJSamoqL9QDQcOFmUAAAUXAzKACAKHjCk6sTPskDHAqBkAJhUUCn3tUp8SY1aUAgpEBYFNCpBwAQRe7EPvW8efP0tefn5x85coSImjdvjs/1/FmtVpeXl0unPS77uaz7xtAAAA7LSURBVLS0tEOHDtJpj2t+FtgncOJkK30DUlNTU1NT9R8YY/hcz59zc3Od3gZ8JqJp06Y5vQ34LOwuJifPG9XXnp+fn5+fHxoaGhoais/1/Llx48bl5eXSaY/Lfvb29o6NjZVOe1zzs7CzUUmkUQCAhgsTngAARMGEJwAAUTDhCQBAFKRRV4ebZyQCgZACYVHA2Kirw9ErEQiEFOBmUAAAJ0CnHgBAFHTqAQBEQafe1eGpQhKBQEiBsCjgLiYAAFEwNgoAIArGRgEARMHYKACAKOjUuzrM+pYIBEIKcBcTCIGjVyIQCCnAXUwAAE7g/E69SqVKT09XqVTOboiL+vTTT53dBCBCIKRBWBQcO3OTqbLnPfHyVxfU7q0Tl65bMCSAs1k3xzHGli5dOnPmzCVLlsyYMcNxLYGawuxdiUAgpEBYFBx6NlqRM2961oD1R0/mZg7f/+KcrNt2/4LjuMLCwvT09OTkZEe2BACgvjgyjWqO7swOGJ/UxZPcw5Mmts3ecVhj708YY4sWLZo6daqfn58DWyKelC98oW2CSbx5kiXl/SaFtjmyH1H19WMh6x+9sHliY6Kq75JD1w4/m5nkZaNuCfdiXKdtUl6bw0m5eWibMFL4ATv2Sr1x/YwR2RwaJSLiOLuLOI3rtE3Ka3M4KTcPbRPG6W1zZBqVBbVuWXj5Kk8dZKy44FrT4FYKm8tL9t83AICac+TYqCJmWFzhlo3HK0l9esOmC3HDY22nUQCA+4CDJzwV/TTn8ZfXn6/yaDvhw3ULhwY6f1oqAEDdku7IMQBAg4DTRQAAUZBGAQBEQRoFABAFaRQAQBSkUQAAUZBGAQBEQRoFABDFKWmUqbLnDouO6BwRnTA7S4l5q/VJnT09xNs/JCQkJKRN15k/qwnhqFe6U58/3b9zy8Ye3efn6vT/y3z/IyJ1zzwQYg4NVv/Ks1+IeGDhsQpWdWrpoIipu245oQ0uq2r3tLDHt1Ya/R+Eoz7plMf2/n7617l9e847pmWMWdr/iEg9MA+EiEPDCWejAh5LCnUH4ahXshbR/Xt18PUwPJLIfP+XIyL1wCwQ5mp+aDghjfJXLytbhgTKiIjzDQ4su1ygrv9GuLKKnS9FtQvt9NBTy/aXMITDycz3fyUi4ixCDw3njI3W9rGk4DCK2Nm/nP3nzPlTu2Y1WfP4Gz+VIxzOZr7/ERFnEHFoOCGNGh5LSlSjx5KCI3HNgtv6KIg82454dmSTvCMFDOFwKvPDwQMRcQoRh4YT0igeS+pErOT8GaWaiHRF+zbuKu3YKdAT4XAq88OhMSLiDKIOjbq+IGYJr8x6a0hk+44dOg9+/YerOmc0wVVpc5eP7hwS1KpVYOvo0am7rugYwlGvdJfXjG8X3LKZh3vTlsGh41Zf0lnY/4hI3TMLhFrEoYHnjQIAiIK7mAAAREEaBQAQBWkUAEAUpFEAAFGQRgEAREEaBQAQBWkUAEAUpFEAAFGQRgEAREEaBQAQBWkUAEAUpFEAAFGc8fR7Zc6iyX06dYwID4uKn/bFsVuWF2PK1Y/0nHNEe+9D7dxYlzhw8Ynf3+r39LYqK2s2btS5JXGDl+Xz4tYMNtz8+okWHj3eydM5ZnVlf65btacmr3ur4e9H4M/MIRy9LWZMf978pU+GPPDuSduhsNmqGq2h1qwehvoNd2xlDlTvaVR78qMJz2bHfnrwzOm/T2a95vnJuH9vsf0D4nxGpa2ZEubmoAYwHd/coSu0VIWuVo/Nqu3y9bk2hyn9cfOBsF78N5l5DslUrOzPdav3FNr9d6+G4a6HX4WNyi1ui6U4OvhYENAqsKS+06jm4Kr0G08seiW2GUfkFjR0fuqDez7ZcIHnL33ycNfEF6dOHDf8gZ7DF/5Wdu8XxEq+e/W51We0ZGmZytP/mxbfLTo6qkvfx1b8ZXxiK/Ns7uvlpmji28yDI/3fjpv+zLjRI174Ku9b/QqJ3fht0cguHbvEDpi8/K9yIiJW+ut7j0SFRfUcmPTKE70HL8vnzauovmYD4yo2FJSb/pXZmrU2l2dFWbOHdO3SLbZHTO9/b1Xx1b8yVvbn8sm9IiI6hUcPm/3DNd6kdsn99tn1HzYd6v/aJ094fbv5mFke5S998nDUqOeeSkwcPfCB0Qt/KWFktoHVdsiWM9+9v/yPU188Ozgu4e3dFWYxshJuWzvt3mJ36fIW9B36aQFPRLrTix66GzKTX2DFyYx/D4yK7NotplfSZ3/rrNVS7a9sbMtt4zjm71888sFePWI6d+o1eeXR8toeC+Y/b+OIVOaufHJAz6iOXUYs/KWEkeZgtbpYyffV9rDZZhKR+vTaf8X3iGgbPqTaActf+mRI7JMpTw2MCQvt+tjnB3YvGNcvqn1o3xk79W+PNt0/ltpp/biWpnp7TKretf8mtHj8mwrDd13+soHBU36o0l1cHuc7ePk5DWMVe16OejRDpStcNSL27b80jL/7wXwZzYlF8UMX591mjJUfnd9/4Ad/a63Uq7u4PK5Z/yWn1YzdW6Hm8Nvdus3YW8rzN/e/HuPV/6PzVYfe6t7zjQNljN36M7Wnd/+PzqsFVaE1+6tKszVrbC1/+tqakV1n7a9ijPEVZWXqompfNZq/5nTv+tLuYp6V5y6O6/j0thvGtUsPX7RuXPhz229pz30Y1/X1300bqbu4PK7pA4tPVjGmPr1kUOybf1aYbmCpyR7gC1YO7X3n1bjme1ttMdw2d5phMQNt7jt9ElZc1jHGtKfefzBeHzKTX2Dewj6RU7Zd0zLGKq9fv81bqaXaXxUprW9LtTjyN4uvqxlj7Nbvbz4wes01vlbHQqXZz1tnvMO9us769QbP3zzwRq+YN//UmNdlvIfNNlN3cXlc096pf9zk+evfJoc9mqHijVferO/8w7eYNn/Fw/7tHs+4oGHlv6V0jfvwH52F/WN+GJofdJrCVSNi33bgL9KxbHUPVCpVZmZmYmKiv7+/o0rNu5uG/+PWcWBcWzcieceIYOVlpcUTqurLFBaW7z5y6vr0Eds5IqoovR13hacwuZXNkXeMH9ze+C0ATHngoG7oO/2acRz1TBrT6SAx5cHf+SELY5sQUbfxozrtJVa0V0AV5n9VcM10zbaXv+o9qK/X+zOmyCc9MmLMyIdCm3Uz/tpWuf+AOmFef1+OKHJyYujwX05qu5lvoED5+fn5+fmhoaGhoaG1/Wx5jaxo++bjcdPjvOSeY8f5j9z05/xe/UwaKu84eEhHdyLqkDDIbcb+Y61MNvCU16RqO4RuGq3dQowshdsRO83kF3jt9t6bw1OHtZQTkYePDxG7YqmW6n9V5D3U2rbod8XdJulK9n/06gdZl3Xu8uJ/ikbm66id1ZaYHQsF10x/3tVrCRs5sXdTjqPYSSMUKQeuaVocNamrtdGu22eymcQTycNHjOvmzXF8bO92iy4refIzHBdu4cPGdPUiuXtMtH9U10dauxEX1a2j8q+rOuZhun9OXAk1PQwtBlTKbHXqMzIypk2blpGR4cBSv8guzXP/PGnoOt0+cuhcWHSEGxGRXK4Pg0wm43krw3vVl+EZ8xmVlpWTk5OTk3Pw2B+LBto4IDh3d3ezN/u5KfT/kHBu7pb/RRFWRQ3/ysbyjXvMzvkl/YnOml9TEwYvOMJV/6olVv0thZy1DRTgyy+/HDRo0Jdffings0Ws8PtNOVe+fT4yNLT9wEVHzn+96aBad+LD4Z06duzYecLqCzwRkVajfwk402o0jMhsAxWme+Aei3vb0t6o5U6TcRzP6w9gne7uxRT7v1ILtZj8lY1tMW5S+c7UGceGfpnz696cba/1kWlNxkprcCzY/Xkb2KnLEk6hUHBExMnlctNd4abQ/+BlcvmdpWRyGdMvZGH/mLSzVgedFNhKo8nJyenp6cnJyQ4sVfSd8q+m/++1pX+U8kSagh2z5/7y0LRJbYUN0XItBwxusX3FhvNqItKVnDz6T0Wt/jygb1/5vuxzGiJt/u6fTuuIC+jTi8vaeqiM0e0jW74/pRVYhflfVZqt2c6GlBf8U9y0a8KTKe/OeEh17HRxta9/e/fr575r/b7rjCqOr8/M79W/swOvOjz99NM///zz008/LeCzRVe3bf47acv5C/n5+fn5F/9aFLpz02/ayP/sPHX27NmTm6e0lRGR7tz3Gw/cYOzm719t1/Xp1/VB0w1UV98hFY0aedy6WcZb3nuWWsEF1HKnyVq2Drz697kqIu2lPXvOWLoyxgUMGNhs5+c/XNMRUWVx8W1Wo1rKrW5LNZqbN2XBoS3dib+yfdtB2y+rt/STM/15V6M7s33z7zcZKzu0cYe2T1+/W2Z1Ge1hs8202Rab7TTbP5GtzA5Dcce1E9j6Ifn5+U2dOtXBpW6RMzavUb80vVeHEp5zD3l4xtbPJrTkSNhJuzzylYx3X506ssu7zI3c20z+aHNM+0Y1/3O3bjOWDUt+9uG9rVo082nWRk7k1n3mstGTn+7a2TM4pn+HcC9PDzdBVVho2EDTNXO2lt/079KPJszJvkGk8+j8wqfD6Y+3jL6O8IkZ8dlzU6b27ljKe3RIWr52hDcV1H73WWHcPa/tZ4u+3Xxq4IwH7+w1WcjIMcEfbfqlMm6wp9EybuHRmhWPdJ9SUBn63Kqveng2D6++gU3Kts023gNNm5Uk9V72TLduzYe+9/NS070d3cFCM9xiUmq10zjfsa8+9tVL8cNCgoKCmwRbHMmRR76yZtbLUwd1fk3u3jjqla/+NyXMfi2s7I+PJlrZlt3/ubdc05GvTF6XMmxMGz+vNt72Ls9b+smZ/ryr7Y3wyIrlI7o/W1DV7rnP1vfwlZnWxTUbZLyHTTbT0g6uEfMouHGm7TTflq6RQuurF3ilnQltRQVr1EhB6r8/HpV0ed7BxX0d1Z+ouzU3ePylT4ZOuvnxvjc7Wxt1BpAwZ0yTkzKm+u6VsYsPazS3NK0mfLC2j+MyXd2tGQCcCmejAACi4J56AABRkEYBAERBGgUAEAVpFABAFKRRAABRkEYBAERBGgUAEAVpFABAFKRRAABRkEYBAET5/y6pMveg40tHAAAAAElFTkSuQmCC",
"image/svg+xml": [
"\n",
"\n"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"let meta@(_,eta,lam) = (bestLoss, 0.721, 100) in \n",
" plot meta $ fitRidge (rootRate eta) (Lambda lam) "
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Why did we find a better value for the rate than the one from our bound?\n",
"Regret bounds describe worst-case behavior. This dataset however is very well behaved -\n",
"and adding stochastic assumptions would lead to a tighter analysis of the\n",
"very same update rule in the form of stochastic [convergence\n",
"rates](https://en.wikipedia.org/wiki/Stochastic_gradient_descent).\n",
"Principled learning rate selection is a difficult problem, for which\n",
"there are many methods, often grouped under the umbrella terms of\n",
"*adaptive* or *parameter-free* methods. As a conclusion to this\n",
"page, here is the summary of the operations that were performed to make\n",
"the algorithm work.\n",
"\n",
"- $\\lambda$ was hand-picked to control the contribution of initial\n",
" jumps to the average objective.\n",
"- $\\eta$ was hand-picked to make the algorithm converge fast. Choosing\n",
" the rate is one of the painful points when running gradient descent\n",
" algorithms. See \\[@duchi2011adaptive\\] and Francesco Orabona’s\n",
" [webpage](http://francesco.orabona.com/research.html).\n",
"- Scaling: The three features and the regression target have been scaled to $[0,1]$. Whithout this\n",
" operation, the algorithm performance would be degraded. That wasn’t\n",
" really crucial here, since the features from `iris` more or less all\n",
" have the same range. It is worth noting however that the convergence\n",
" rate of OGD is greatly reduced when features have different\n",
" magnitudes. See @nag, @sketchingNicolo and\n",
" @duchi2011adaptive for a discussion of this aspect.\n",
" \n",
"\n",
"# References"
]
}
],
"metadata": {
"kernelspec": {
"display_name": "Haskell",
"language": "haskell",
"name": "haskell"
},
"language_info": {
"codemirror_mode": "ihaskell",
"file_extension": ".hs",
"name": "haskell",
"pygments_lexer": "Haskell",
"version": "8.6.5"
}
},
"nbformat": 4,
"nbformat_minor": 5
}