{"id":33,"date":"2017-09-26T15:52:45","date_gmt":"2017-09-26T15:52:45","guid":{"rendered":"http:\/\/www.nullplug.org\/ML-Blog\/?p=33"},"modified":"2017-10-19T07:37:18","modified_gmt":"2017-10-19T07:37:18","slug":"machine-learning-overview","status":"publish","type":"post","link":"http:\/\/www.nullplug.org\/ML-Blog\/2017\/09\/26\/machine-learning-overview\/","title":{"rendered":"Machine Learning Overview"},"content":{"rendered":"

\n Science is knowledge which we understand so well that we can teach it to a computer; and if we don’t fully understand something, it is an art to deal with it. Donald Knuth<\/a>\n<\/p><\/blockquote>\n

Introduction<\/h2>\n

First Attempt at a Definition<\/h4>\n

One says that an algorithm learns<\/em> if its performance improves with additional experience.<\/p>\n

This is not a precise definition, so let’s try to make it so.<\/p>\n

Definition<\/h4>\n

An algorithm will be a function1<\/a><\/sup> $f\\colon D\\to T$ and whose individual values can be calculated by a computer (i.e., a Turing machine<\/a>) in a finite amount of time using a finite amount of memory. We can refer to $D$ as the space of inputs or samples or examples and $T$ as the outputs or labels.<\/p>\n

For the following definition we will want to be able to form a sum indexed by the elements of $D$. For this purpose we could suppose that our input is finite or that the domain is a measure space and that the algorithm will be a measurable function. For simplicity and convenience, we will pretend that $D$ is finite. That is if $D$ is infinite, then we have actually implicitly restricted to to a finite subset (e.g., $D=\\Bbb R$ should really be interpreted as the finite subset of floating point numbers expressed in some fixed number of bits). This poses no real restriction in applications (all real world problem domains are effectively finite).<\/p>\n

Definition<\/h4>\n

A performance measure of an algorithm will be a function $P\\colon D\\times T \\to \\Bbb R$. For two algorithms $f_1$ and $f_2$, we will say that $f_1$ performs better than<\/em> $f_2$ (relative to $P$) if $$\\sum_{d\\in D} P(d,f_1(d)) > \\sum_{d\\in D} P(d, f_2(d)).$$ We similarly define ‘performs worse than’ and ‘performs at least as well as’, etc.<\/p>\n

Alternatively, we may be presented a cost<\/em> function $C\\colon D\\times T\\to \\Bbb R$ which we want to minimize<\/em>. One can postcompose any performance measure (resp. cost function) with an order reversing map to obtain a cost function (resp. performance measure). This allows us to pass between the two notions.<\/p>\n

Definition<\/h4>\n

A machine learning algorithm<\/em> is an algorithm $f_-\\colon 2^E \\times D\\to T$, that learns with respect to a specified performance measure $P$ (defined below). Here $2^E$ is the set of all subsets of $E$. We call an element $S\\in 2^E$ (i.e., a subset $S\\subseteq E$) a set of training data<\/em>. For such an $S$ and $f_-$, let $f_S=f_-(S,-) \\colon D\\to T$ denote the resulting algorithm (which we will say is trained<\/em> on $S$).<\/p>\n

Example<\/h4>\n

Consider the problem of finding a linear function $f\\colon D\\subset \\Bbb R\\to \\Bbb R$ which closely approximates a fixed function $F\\colon D\\subset \\Bbb R\\to \\Bbb R$. We can regard the function $F$ as a subset $S$ of $E=D\\times \\Bbb R$ by $F\\mapsto S= \{(s,F(s)) | s\\in D\}$2<\/a><\/sup>. We can define a cost<\/em> function $C\\colon D\\times \\Bbb R\\to \\Bbb R$ by $$C(d,t)=(F(d)-t)^2.$$ We can reformulate problem of minimizing the cost of $C(d,f(d))$ as maximizing the performance function $P(d,t)=\\frac{1}{1+C(d,t)}$. The method of Linear Regression<\/a> will define a machine learning algorithm $f_-\\colon 2^E\\times D\\to \\Bbb R$.<\/p>\n

One can play with this problem using this demo<\/a>.<\/p>\n

Second Attempt at a Definition<\/h4>\n

A machine learning algorithm $f\\colon 2^E\\times D\\to T$ learns<\/em> (relative to a performance measure $P$) if for all proper subset inclusions $S_1\\subset S_2\\subseteq E$, $f_{S_2}$ performs better than $f_{S_1}$.<\/p>\n

This is at least clearly defined, but it does not cover many examples of learning algorithms. For example, the method of linear regression will perform poorly when given a small training sample containing outliers (those $d\\in D$ such that $F(d)$ takes on an unlikely value under some assumed probability distribution associated to $F$). So, the act of adjoining outliers to our training data will typically decrease the performance of this machine learning algorithm.<\/p>\n

Final Definition<\/h4>\n

A machine learning algorithm $f\\colon 2^E\\times D\\to T$ learns<\/em> (relative to a performance measure $P$) if for each pair of natural numbers $m<n$, the average of the performances of $f_{S}$ over the subsets $S\\subseteq E$ of cardinality $n$ is better than the average of the performances over the subsets of cardinality $m$.<\/p>\n

Crucial remark<\/h4>\n

Without a specified performance measure, we have no obvious goal in machine learning. We can only evaluate machine learning algorithms relative to a performance measure3<\/a><\/sup> and an algorithm that performs well with respect to one measure may perform poorly with respect to another. So the field of machine learning depends on first finding a good performance measure for the task at hand and then<\/em> finding a machine learning algorithm that performs well with respect to this measure.<\/p>\n

Remarks<\/h4>\n

Now that we have come to a definition of a learning algorithm that learns that seems to cover at least one standard example, I will unveil some unfortunate truths:<\/p>\n