Perceptrons, Neurons, and Learning Logic

OK, fine. I'll tell you about perceptrons.

Warning 1: These are the guys most responsible for getting me hooked on this subject. They may hook you too.

And credit where credit's due: I learned pretty much everything written below from the sections on Perceptrons and Sigmoid Neurons in Chapter 1 of Michael Nielsen's fantastic free on-line Neural Networks and Deep Learning book. In fact, if you'd rather skip my post and just go read those sections now, I won't be offended.

I will, however, insist that afterward you check out the frickin' awesome neural network playground visualization tool created by Daniel Smilkov and Shan Carter as part of this larger project. You can fiddle with various parameters and see in real time how your fiddlings affect the way that a neural net learns to separate various non-linearly separable $2$-dimensional data sets. Well worth the $\geq 20$ minutes of your life it will cost you to do so.

Warning 2: It's going to seem for a moment that we're on a different planet, but bear with me. We'll be back on Earth again soon, I swear.

Perceptrons

Suppose you want to make a Yes/No decision based on your own personal weighting of answers to a finite collection of Yes/No questions.

(I want us all to pause for a moment and appreciate the following fact: This is basically how we do make decisions.)

The example Michael Nielsen gives in his book (Attend a cheese festival: Yes or No?) is far better than anything I can come up with, so I won't try. Instead I'll keep things abstract and just refer you there if you want an example.

A perceptron is a simple mathematical gadget that models this type of decision. People usually draw perceptrons like this:

An n-input perceptron

The $n$ nodes on the left (ordered from top to bottom, say, and labeled $x_1, \ldots, x_n$) represent the inputs. Each input will either be a "0" ("No") or a "1" ("Yes"), so there will be $2^n$ possible inputs to the perceptron. Let's call these inputs $x_1, \ldots, x_n$.

The output to the perceptron will also be a "0" or "1." How does the perceptron choose? Well, the perceptron has $n$ weights, $w_1, \ldots, w_n \in \mathbb{R}$, assigned to the $n$ input nodes, along with an overall threshold, $b \in \mathbb{R}$. Its output is then given by:
\[\left\{\begin{array}{cl} 0 & \mbox{if } \sum_{i=1}^n w_ix_i < b, { and}\\
1 & \mbox{if } \sum_{i=1}^n w_ix_i \geq b
\end{array}\right.\]

In other words, if the weighted sum of the inputs achieves or exceeds the threshold, output $1$. If it doesn't, output $0$.

If you read my post about linearly separating data, this should be starting to sound eerily familiar. Explicitly, a perceptron with $n$ inputs answers the following concrete question:

"Let ${\vec x} \in \{0,1\}^n \subset \mathbb{R}^n$ be a binary $n$-tuple, regarded as an $n$-dimensional real vector. On which side of the hyperplane defined by weight vector $\vec{w} := (w_1, \ldots, w_n)$ and shift $b$ does it lie?"

But when we think about it in these terms, the first thing that should jump to our minds is: Why on earth should a perceptron accept only binary inputs? There's nothing stopping it from accepting real-valued inputs. In fact, the geometric interpretation of what a perceptron is doing is somehow more natural when we allow our inputs to be any real numbers and not just $0$s and $1$s.

OK. Hold that thought while I tell you something else completely unrelated but even cooler.

Any logical sentence (or "circuit") can be built by concatenating perceptrons:

This is what blew my mind when I first heard about these guys.

If you've ever studied elementary logic (maybe you took an elementary proofs course or something), you've probably built yourself a truth table or two. If you haven't, don't worry. I'll tell you what they are and what they do.

(And if you're interested in what they have to do with mathematical proofs, you might like these notes written by Michael Hutchings, which I often use as a first reading assignment whenever I teach Intro to Proofs at Boston College.)

At its core, elementary logic is a language or "calculus" that allows us to specify how to take a finite, ordered tuple of $0$s and $1$s (a so-called binary string), perform a collection of operations on it, and obtain another ordered tuple of $0$s and $1$s. The $4$ basic operations in this language are:

1. $*_1$ And $*_2$, 
2. $*_1$ Or $*_2$, 
3. If $*_1$ Then $*_2$,
4. Not $*$

The *s above represent inputs. Note that the first three operations take two inputs, and the last takes one.

The binary output or value of each of the statements above is determined by a so-called truth table (it's a bit like a multiplication table). It tells you, e.g., that the output of the statement "$*_1$ and $*_2$"is $0$ unless both $*_1$ and $*_2$ are $1$. This should make sense to you since a statement like "I love cheese and it's 10 AM" is only true if the statements "I love cheese" and "It's 10 AM" are both true.

So the truth table for ($*_1$ And $*_2$) looks like this:

The inputs $*_1$ and $*_2$ are along the left and the top, and the outputs for the various corresponding combinations are recorded in the interior. You can easily find the truth tables for the other logical operations online (or in Hutchings' notes), so I won't record those here.

OK, great. The point now is that you can model any of these operations using a perceptron. 

I'll do "And," then leave the other three as exercises. Here's the picture:

So e.g. if we let $w_1 = w_2 = 10$, and $b = 15$, then the perceptron will return $1$ iff both inputs are $1$, as desired.

Note that there are (infinitely) many choices of weights $w_1, w_2$ and shift $b$ that work to model this "And" perceptron; all you need is a hyperplane separating the point $(1,1)$ from the points $(0,0), (1,0), (0,1) \in \mathbb{R}^2$. This is pretty easy to do, and also gives you an idea how to solve the exercises above once you find their truth tables online!

Once you've solved the exercises above, you have all the tinker toys you need to build any simple logical statement out of perceptrons (mathematicians also like using quantifiers like "for all" and "there exists," but let's ignore those). Connect the inputs to outputs in the appropriate way, and you've got your statement. For example, here's a perceptron model of the statement

"If ($*_1$ And $*_2$) Then ($*_3$)":

For fun, you might now imagine letting $*_1, *_2, *_3$ represent the truth values of the statements,

1. "You're happy," 
2. "You know it," 
3. "You clap your hands," resp. 

(Credit to Josh Greene for this.)

Then the perceptron circuit will output a $1$ if, e.g., you're sad and you don't know it and you clap your hands, but a $0$ if you're happy and you know it and you don't clap your hands.

And you can go crazy with it. You can, e.g., make a perceptron circuit that looks like this:

N.B.: It looks like our perceptrons have multiple outputs in this picture. They don't. Each perceptron can have multiple inputs but only a single output. The multiple lines emanating from each perceptron in the pic above correspond to sending that perceptron's output to multiple places.

But I hope that the picture of a perceptron circuit I drew poorly above is starting to look a leeeeeetle bit like the pictures of neural networks we've seen in the news.

And Now Back to That Thought we were Holding:

Perceptron circuits are awesome, but they're pretty rigid. Their inputs and outputs are binary. Not to mention that the rule each perceptron uses to decide between outputting a $0$ and a $1$ is a step function: output $1$ if you're on or to one side of a hyperplane, $0$ if you're on the other side.

Perceptrons use step functions

The rigidity and jumpiness of this set-up doesn't seem ideally-suited to learning, does it?

(It's not.)

BUT what if we fuzz things out a bit, like we were doing before? That is, let's allow real-valued inputs and outputs, and replace our step functions with sigmoid functions. In other words, let's replace each perceptron with a sigmoid neuron. In case you haven't already guessed, a sigmoid neuron still has associated to it an $n$-dimensional weight vector $\vec{w} \in \mathbb{R}^n$ and a threshold $b \in \mathbb{R}$. But it allows its $n$-dimensional input vector $\vec{x}$ to live anywhere in $\mathbb{R}^n$, and its output will interpolate between $0$ and $1$ using a sigmoid function. That is, its output will be $\sigma(\vec{w}\cdot \vec{x} - b) \in (0,1)$. Recall that $\sigma(t) = \frac{1}{1+e^{-t}}$.

Sigmoid neurons use sigmoid functions

Sigmoid functions look an awful lot like step functions if you squint hard at them (increasingly so if we use a sigmoid function like $\frac{1}{1+e^{-ct}}$ and let $c \rightarrow \infty$)

Well, by George, we have a neural network. Moreover, it can, in principle learn logic. At least the elementary models of logic I teach in Math 216. 

All we need now is:

1.  a reasonable cost function,
2.  a reasonable way of computing its partial derivatives with respect to the weights and thresholds associated to all of the sigmoid neurons,
3. buttloads of data for it to learn from.

We'll talk more about that next time.

BTW: I should thank the Isaac Newton Institute in Cambridge for its hospitality, since that's where I am at the moment!

Idiot's Guide (written by an actual Idiot)

I still haven't told you what a neural net is or how one works. (Don't worry. We'll get there soon.)

You may be itching to play around with one all the same.

Unfortunately (or maybe fortunately...) you can't build a neural net with paper clips and string in your living room. And I wouldn't recommend writing much code from scratch either, even if you're already an amazing programmer (I'm not).

Luckily, some actual amazing programmers have already done all the hard work for you. Unluckily, finding which people have done it best and actually understanding how to get your hands on what they've done can sometimes feel harder than just doing the damn thing yourself.

(I don't recommend doing the damn thing yourself.)

The purpose of this post is to record roughly what I did to get myself up and running. Maybe provide a link or two or three. The post is almost entirely selfish, because I know I will never remember how to do this unless I write it down somewhere. May as well write it somewhere where it has a chance of helping others too.

User beware: I have close to zero programming experience and even less experience mucking around with Unix (besides using pine as an undergrad--ugh, dates me terribly, I know...). I can't guarantee that the steps below are maximally efficient or even close. All I know is that I can do what I need to do on my computer now. And the recipe I followed is below.

Ingredient list:

1) Python: This is the programming language everything is written in. Don't know anything about this language? That's OK. There are a buttloads of resources on-line for learning the syntax and basic structure, etc. When I'm writing a program and google a python syntax question, I often end up here. I also spent a good amount of time at the beginning going through this set of lecture notes. Or you could take one of the 10,000 MOOCs on it if you want more direction.
2) Jupyter (iPython) Notebook: This is a web-based environment that will allow you to write python code and execute it in the notebook so you can troubleshoot your code while you're writing it instead of after you've done it all wrong.
3) TensorFlow: This is the machine learning package developed by Google. People seem to like it! As do I, so far!
4) Keras: This is a front end for TensorFlow (it can also work with Theano as a back end--this is an alternative to TensorFlow that I have heard good things about but never used) that is (precisely) one zillion times more user-friendly. I was dreading building a neural net using TensorFlow until someone (Mark Hughes) told me about Keras.


Instructions (for a Mac, which is what I have):

0) Open a Terminal (look in your Applications folder if you don't know what I mean)
1) Install Anaconda (a python distribution with a package manager called "conda" that can be used to install various other packages) using the link in the "Anaconda Installation instructions" found on the TensorFlow website here. Keep in mind that there are lots of different versions of python, and the syntax actually varies quite a bit (annoyingly) among them. I went ahead and got the most recent version of python 3.
2) Create a conda environment called tensorflow by typing (where you may replace "3.5" with the python version number you are using):

      $ conda create -n tensorflow python=3.5

3) Activate the tensorflow environment by typing:

$ source activate tensorflow 

(tensorflow)$  # Your prompt should change

4) Install tensorflow using conda:

# Linux/Mac OS X, Python 2.7/3.4/3.5, CPU only:
(tensorflow)$ conda install -c conda-forge tensorflow

5) At this point, I followed an amazingly helpful answer on Quora found here to the question "How can I work with Keras on a Jupyter notebook with TensorFlow as a backend?" One needs to install ipython, Jupyter, and Keras (in that order) inside the tensorflow environment by typing:

(tensorflow) username$ conda install ipython
(tensorflow) username$ pip install jupyter
(tensorflow) username$ pip install keras 

6) Now deactivate and reactivate the tensorflow environment (not sure why you need to do this):

1. 
   
2. (tensorflow)username$ source deactivate tensorflow
3. username$ source activate tensorflow

7)  And open the Jupyter notebook (it will open in a browser: I think Safari is the default, at least that's what opens on my computer):

(tensorflow)username$ jupyter notebook

8)  Once the Jupyter notebook opens, navigate to whichever directory you want to use to store your ipython notebooks and click (upper right) New-->Python3 and you'll be in a Jupyter notebook. You can execute python code by doing a Shift-Return. You might try writing "print('hello, world')" to make sure you've got it. (It should output "hello, world" obvs).

9) To shut everything down, save your notebook, close the browser window, do a Ctrl-c at your terminal and answer "Y" when it asks you whether you want to shut down your Jupyter notebook.

10) You'll be back at the tensorflow prompt, at which point you deactivate tensorflow environment:

1. (tensorflow)username$ source deactivate tensorflow

11) Type "Exit" to close your terminal and you're all done.

12) Now whenever you want to open a Jupyter Notebook and use Keras, TensorFlow you just do:

$ source activate tensorflow 

(tensorflow)$  # Your prompt should change

 then

(tensorflow)username$ jupyter notebook

and once you're all finished with your jupyter notebook:

(tensorflow)username$ source deactivate tensorflow

13) BTW, here's the documentation for Keras. I followed this great tutorial to understand how to build an LSTM (a particular neural network architecture that is good for analyzing sequences--will write more about this later) using Keras. Really cool thing I didn't realize until I did this tutorial: you can use Keras to download interesting data sets (this tutorial uses some imdb movie reviews and classifies them into "positive" or "negative")--I haven't explored which ones.

How a machine learns (Or: It's the derivative, stupid)

Before I start, let me just say how excited I am about this course I'm sitting in on at MIT this week. I'll try my best to sort of repeat the most interesting tidbits I learn in a future post. I'm starting to worry about how long these posts are taking me, though, so for now, let me just provide a link to this frickin' awesome toy model of a self-driving car. Click the "Run Training" button, and in 10 seconds a neural net (using reinforcement learning) teaches the toy car to "drive" (BTW, the code runs in the browser--I mean WOW.) 

I haven't personally explored the reading material on the Resources tab there, but it all looks useful. Also: the Deep Learning book (Goodfellow, Bengio, Courville) mentioned on the Resources tab was independently recommended by mathematical little bro' Jon Bloom. And two independent recommendations implies it must be good. That's like a theorem, right?

(Umm....no 'tisn't. But I do trust JB's recs about this stuff, so feel confident passing them on.)

OK, back to basics. Last time, I talked about a particular type of problem a machine learning algorithm might want to tackle:

One has a bunch of data points in some high-dimensional parameter space $\mathbb{R}^n$ (where the $n$ parameters are whatever some particular human has decided would be useful to determine the answer to some yes/no question like "Is a particular e-mail spam?"), and these data points have been "pre-classified." That is, each data point has already been assigned a "yes/no" label (e.g., a human has gone through the data somehow and labeled each data point manually as "Yes-spam" or "No-not spam"). Here's a picture of what this might look like in a 2-dimensional parameter space (Red = "Y", Pencil = "N"). Sorry this is so low-tech, but I'm just a mathematician:

Now suppose we (humans) guess that the data is linearly separable, that is we guess that the decision boundary between the "Y" region and the "N" region of the parameter space is just a hyperplane determined by some orthogonal vector $\vec{a} \in \mathbb{R}^n$ and shift $b \in \mathbb{R}$. (A reasonable assumption in the silly example pic above.)

The canonical first example of a machine learning algorithm (which you may as well think of a computer program) is one that will use

1. our pre-labeled data and
2. our assumption that the data is linearly separable

to determine the decision boundary. Note that our choice to assume that our decision boundary is a hyperplane tells us that the output of our machine learning algorithm should just be the parameters $\vec{a} \in \mathbb{R}^n$ and $b$ specifying the hyperplane.

OK, so what should the machine do?

Well...what would a human do?

Cost function

That's right! Start by guessing something, then keep trying to improve. Of course, this begs the question, "Improve what?" Without getting too philosophical about it, we need to define some cost function whose input is

1. our pre-labeled data and
2. our current guess $\vec{a} \in \mathbb{R}^n$ and $b \in \mathbb{R}$

and spits out a number that we refer to as the cost associated to the guess $\vec{a}, b$. The cost function should be defined in a reasonable enough way that we really feel it's measuring how well we're doing. (High cost = bad.) It should also treat all data points equally. That is, it should be an average over individual cost functions for each data point. (It also helps if it's easy to compute its partial derivatives with respect to the parameters, but we're getting ahead of ourselves.)

Minor but Important notational digression

Remember we have our space $\mathbb{R}^n$ that parameterizes our data (in our spam example, points $\vec{x}$ in this space represent e-mails). But we also have our space $\mathbb{R}^{n+1}$ that parameterizes the possible separating hyperplanes (points $(b, \vec{a})$ in this space represent shifted hyperplanes in the data-parameterizing space $\mathbb{R}^n$).

At this point, it is notationally convenient to imbed the data-parameterizing space $\mathcal{D} \cong  \mathbb{R}^n$ into $\mathcal{D}' \cong \mathbb{R}^{n+1}$ via the map \[\vec{x} := (x_1, \ldots, x_n) \mapsto \vec{x}' := (1,x_1, \ldots, x_n).\] Doing this imbedding allows us to treat the shift (often called the bias in the literature) $b$ associated to a hyperplane on equal footing with the components $a_i$ of the vector $\vec{a} = (a_1, \ldots, a_n)$ specifying its orthogonal direction.

Now suppose we have a point $\vec{a}' := (a_0, a_1, \ldots, a_n) \in \mathbb{R}^{n+1}$. Then remembering that if $\vec{x} \in \mathcal{D}$ then $\vec{x}' = (1, \vec{x})$ denotes its imbedding as the $1$ level in $\mathcal{D}'$, the hyperplane in $\mathcal{D}$ determined by $\vec{a}'$ is the set of points $\vec{x} \in \mathcal{D}$ for which $\vec{a}' \cdot \vec{x}' = 0$ (this is the hyperplane specified by orthogonal vector $(a_1, \ldots, a_n)$ and shift $-a_0$).

Cross-entropy cost function

A commonly used cost function for a problem of this type is the cross-entropy cost function. Before describing it, let me come clean and admit that because of my lack of prior training in statistics I don't yet feel in my bones why this is the "right" choice. I will say that Chapter 2: Classification and Logistic Regression in Andrew Ng's CS229 lecture notes here helped me, as did the discussion of the cross-entropy cost function in Chapter 3 of Michael Nielsen's Deep Learning book (esp. the animations). I may try to write more about this later when I'm smarter.

Relative ignorance disclosed, I proceed:

Remember that for each data point $\vec{x}$, we have a "Y/N" label. Let's turn these into "1/0" labels. That is, for each data point $\vec{x}$, define
\[y(\vec{x}) = \left\{\begin{array}{cl} 1 & \mbox{if the label on } \vec{x} \mbox{ is ``Y"}\\
0 & \mbox{if the label on } \vec{x} \mbox{ is ``N"}\end{array}\right.\]

Remember also that for a particular choice of parameters $\vec{a}' \in \mathbb{R}^{n+1}$ specifying the separating hyperplane (see notational digression above), the output guessed by the model on a point $\vec{x} \in \mathbb{R}^n$ is \[\sigma(\vec{a}' \cdot \vec{x}') \in (0,1),\] where $\sigma$ is the sigmoid function  \[\sigma(t) = \frac{1}{1 + e^{-t}}.\] We can (and should, I suppose) think of \[h_{\vec{a}'}(\vec{x}) := \sigma(\vec{a}'\cdot \vec{x}')\] as the probability that the label on $\vec{x}$ is "Y" (according to the model specified by the vector of parameters $\vec{a}' = (a_0, a_1, \ldots, a_n)$). 

The cross-entropy "cost" or "loss" associated to hyperplane parameters $\vec{a}'$ and a particular data point $\vec{x}$ is then defined as: \[J_{\vec{a}'}(\vec{x}) := -y(\vec{x})\ln(h_{\vec{a}'}(\vec{x})) - (1 - y(\vec{x})) \ln(1-h_{\vec{a}'}(\vec{x})),\] and if we have $N$ pre-labeled data points $\vec{x}^{(1)}, \ldots, \vec{x}^{(N)}$, we define the cost to be the average of the individual costs:
\[J_{\vec{a}}\{\vec{x}^{(1)}, \ldots, \vec{x}^{(N)}\} := \frac{1}{N}\sum_{i=1}^N J_{\vec{a}'}(\vec{x}^{(i)}).\]

Let's pause for a sec, because it's worth noting how much less complicated this function is than it appears at first glance. Remember that $y(\vec{x})$ is only ever $0$ or $1$, so for each data point $\vec{x}^{(i)}$ one of the two terms in the sum drops out and the other is just the negative of the natural log of an expression involving the difference between the actual label (which is either $0$ or $1$) and the predicted label (which is some real number between $0$ and $1$). As far as I can tell, the main reason for the appearance of the natural log here is because:

1. The more wrong you are, the more you are penalized: Think of the behavior of $-\ln(t)$ for values of t between 0 and 1. Its main feature is that as $t$ goes to $0$, $-\ln(t)$ goes to $\infty$, and as $t$ goes to $1$, $-\ln(t)$ goes to $0$. As a result, when the difference $y(\vec{x}) - h_{\vec{a}'}(\vec{x})$ between the actual label and the predicted label is large (close to $1$), then $1$ minus this difference is close to $0$, so when we take $-\ln$ of this number, we get something huge. The hugeness goes to $0$ as the discrepancy between the actual label and the predicted label goes to $0$.
2. Having $\ln$ in the expression makes it easier to take partial derivatives of the cost function: Read the next section to understand why this is.

Gradient descent

Now that we have a way of measuring how well we've done for a particular choice of parameters $\vec{a}'$, calculus tells us how we might do a bit better (at least nearby).

Remember we have our space $\mathcal{D} = \mathbb{R}^n$ that parameterizes our data, and we have our space $\mathbb{R}^{n+1}$ that parameterizes the possible separating hyperplanes. We now want to think of our cost function as a function from our hyperplane-parameterizing space to $\mathbb{R}$ and locate the point(s) in our hyperplane-parameterizing space that minimize cost.

Here is where calculus helps us. Remember that if we have a real-valued smooth function of several parameters and we are interested in finding an absolute minimum of the function (and our domain is boundary-less), we know for sure that this absolute minimum will occur at a local minimum of the function. And every local minimum of the function will in particular have the property that all of the partial derivatives of the function vanish there.

This tells us that to find an absolute minimum of the cost function we should look for places where the partial derivatives of the cost function vanish (aka critical points of the function). As a first pass, this is a great idea as long as we remember that not every critical point is a local minimum, and not every local minimum is an absolute minimum. If you like Morse theory, you don't need to be convinced of those two statements. If you don't yet like Morse theory, the following two pics may convince you (again, low tech--sorry):

A portion of the graph of a real-valued function whose domain is 2-dimensional.
The partial derivatives at the black dot vanish, but the black dot is not a local minimum.

A portion of the graph of a real-valued function whose domain is 1-dimensional.
The black dot is a local minimum but not an absolute minimum.

Since it is not always easy (read: computationally advantageous) to find the critical points of a cost function directly, what is done in practice is to compute the gradient of the cost as a function of the hyperplane-parameterizing space: \[\nabla(J) := \left(\frac{\partial J}{\partial a_0}, \frac{\partial J}{\partial a_1}\ldots, \frac{\partial J}{\partial a_n},\right)\] and take small-ish steps in the negative gradient direction until your gradient gets close enough to $\vec{0}$ that you're pretty darned sure you're close to a critical point. This is called gradient descent, and it's what puts the "learning" in "machine learning." To first order, it's really that simple.

(WARNING: Keep your wits about you. The gradient of the cost function is computed with respect to the hyperplane-parameterizing space NOT the data-parameterizing space. The machine is trying to learn the best hyperplane to fit the data, which it is treating as a constant.)

Of course, one of the big problems with gradient descent is that unless you happen to know in advance that your function has only one critical point and that it is definitely a local minimum, then the result of performing gradient descent will not necessarily find you a global minimum. I'll probably try to talk about this at greater length later. Let's ignore it for now, compute the gradient of the cross-entropy cost function, and call it a day.

Gradient of cross-entropy cost function (+ a useful property of the sigmoid function)

Now we just dust off the ole' chain rule, keeping in mind the following useful observation about the sigmoid function $\sigma(t) := \frac{1}{1 + e^{-t}}$: \[\frac{d\sigma}{dt} = \sigma(t)(1 - \sigma(t)).\] This fact also uses the chain rule in the first step. The rest is just algebra:
\begin{eqnarray*}
 \frac{d\sigma}{dt} &=& \frac{e^{-t}}{(1+e^{-t})^2}\\
 &=& \frac{1}{1+e^{-t}}\cdot\frac{(1+e^{-t}) - 1}{1 + e^{-t}}\\
 &=& \sigma(t)(1 - \sigma(t))
\end{eqnarray*}

Now it will turn out that \[\frac{\partial J}{\partial a_j} = \frac{1}{N} \sum_{i=1}^N (h_{\vec{a}'}(\vec{x}^{(i)}) - y^{(i)})x_j^{(i)},\] where we recall that $h_{\vec{a}'}(\vec{x}) := \sigma(\vec{a}' \cdot \vec{x}')$. This derivation has some slightly non-obvious steps, so I include it here. Note that the partial derivative of a sum is the sum of partial derivatives, so we just need to verify that the partial derivative $\frac{\partial J}{\partial a_j}$ associated to a particular data point $\vec{x}^{(i)}$ has the form we see inside the summation above. If $y(\vec{x}^{(i)}) = 1$, the chain rule and the fact above about the derivative of the sigmoid function tells us this is:

\begin{eqnarray*}
 &=& -y(\vec{x}^{(i)}) \cdot \frac{1}{\sigma(\vec{a}'\cdot(\vec{x}^{(i)})')}\cdot \sigma(\vec{a}'\cdot(\vec{x}^{(i)})')\cdot (1 - \sigma(\vec{a}'\cdot(\vec{x}^{(i)})') \cdot x_j^{(i)}\\
 &=& y(\vec{x}^{(i)}) \cdot (\sigma(\vec{a}'\cdot(\vec{x}^{(i)})') - 1) \cdot x_j^{(i)}\\
&=& (h_{\vec{a}}(\vec{x}^{(i)}) - y(\vec{x}^{(i)})) \cdot x_j^{(i)}
\end{eqnarray*}

where in the last step we are using the assumption that $y(\vec{x}^{(i)}) = 1$. Similarly, if $y(\vec{x}^{(i)}) = 0$, the summand reads:

\begin{eqnarray*}
 &=& (1-y(\vec{x}^{(i)})) \cdot \frac{1}{1 - \sigma(\vec{a}'\cdot(\vec{x}^{(i)})')}\cdot \sigma(\vec{a}'\cdot(\vec{x}^{(i)})')\cdot (1 - \sigma(\vec{a}'\cdot(\vec{x}^{(i)})') \cdot x_j^{(i)}\\
 &=& (1- y(\vec{x}^{(i)})) \cdot (\sigma(\vec{a}'\cdot(\vec{x}^{(i)})') \cdot x_j^{(i)}\\
&=& (h_{\vec{a}}(\vec{x}^{(i)}) - y(\vec{x}^{(i)})) \cdot x_j^{(i)}
\end{eqnarray*}

where again in the last step, we are using the assumption that $y(\vec{x}^{(i)}) = 0$.

OK, I'm tired now and probably you are too. I'm also sure the equations here are riddled with sign errors and other less forgivable mistakes. Please tell me if you notice any (forgivable or not). I'll try to have fewer equations in later posts.

Hello world.

I'm a low-dimensional topologist trying to learn the basics of machine learning + AI, especially the mathematics behind neural networks.

(Aside: This is just in case the title of the blog rings a too-distant bell.)

If you'd rather just tune me out and explore on your own, what little I do know I learned from the following sources, listed roughly in chronological order. As I learn more, I'll expand this list:

• Andrew Ng's Coursera course (also a really great place to get a broad overview of machine learning in general - beware: calculus is not a prereq, so the math is mostly black-boxed, but someone comfortable with multivariable calculus and linear algebra can fill most of those boxes with little trouble)
• Michael Nielsen's awesome free on-line Neural Networks and Deep Learning book
• Chris Olah's blog, colah's blog
• Jesse Johnson and his blog, The Shape of Data
• Mark Hughes

I'll begin with some basics about machine learning algorithms in general and neural networks in particular. I'm really going to start from the very beginning (a very good place to start, according to Julie Andrews). I feel a little funny doing this, because I'll start by saying some things which are probably pretty obvious to most people that have thought about this at all. OTOH, sometimes it helps to hear the obvious stuff. And there's a reasonable chance that many people who actually use neural nets have never really thought about the obvious stuff. Why take a chance?

I'll start by describing a particular class of problems machine learning algorithms like to try to solve.

Decision problems

According to wikipedia, a decision problem is a problem in some formal system with a yes or no answer, depending on the values of some input parameters. A canonical example is the problem of spam detection. Given an e-mail message, you'd like to classify it as "Yes - spam" or "No - not spam."

Of course, when we put it like this it is not yet a formal decision problem, because we haven't yet chosen a model. I.e., we haven't translated our floppy real-world question into a precise mathematical one, since we haven't determined what input parameters we will use to make the decision.

(Indeed, this is by far the hardest step. But let's roll with it anyway.)

So, step one is choosing some appropriate input parameters. Off the top of my head these might include, e.g.:

1. length (in characters) of the message, 
2. number of misspelled words, 
3. number of appearances of the word "sex", 
4. what-have-you

At the moment, I think it's mostly humans that are charged with picking appropriate input parameters, but I do think humans are working on outsourcing this part to machines, too. Not sure yet how or how successfully.

Once the input parameters are chosen, you have formally defined your decision problem. You have yourself a multi-dimensional space, each axis of which corresponds to one of the input parameters you've chosen. Now each e-mail message can be assigned a point in this multi-dimensional space, and you're in business.

All you need now is to take the data you have (which, perhaps, a human has gone through and manually classified as "Yes - spam" or "No - not spam") and develop from it an algorithm to partition your parameter space into a "Yes" part and a "No" part. The idea here is that if you now get a new e-mail message that you haven't seen and assign it a point in your parameter space, your algorithm will now classify it as "Yes" or "No" depending on where it lands.

So what do you want your algorithm to do? Well, it's reasonable to guess that if some point is classified as "Yes" then nearby points will be too. So your job is to figure out how to build some (one? two? not sure) walls in your parameter space to separate the "Yes" sections from the "No" ones. These walls are often called the decision boundaries.

What's the easiest way we can possibly imagine our space being partitioned? (Besides everything being classified as "No", obviously...) That's right! Split in two by a hyperplane. This is the linearly separable situation, and it's a particularly happy one, so we'll talk about it first. 

When your decision boundary is a single hyperplane (your data is linearly separable)

Recall that a hyperplane is just a multi-dimensional analogue of a plane imbedded in 3-dimensional space or a line imbedded in 2-dimensional space. In general, if our parameter space is n-dimensional, a hyperplane is an (n-1)-dimensional linear space that cuts your n-dimensional space neatly in two.

And the nice thing about a hyperplane in n-dimensional space is that it is the solution set of a single linear equation in n variables. In linear algebra terms, it is the set of vectors $\vec{x} = (x_1, \ldots, x_n) \in \mathbb{R}^n$ whose dot product with a particular vector $\vec{a} = (a_1, \ldots, a_n) \in \mathbb{R}^n$ is a particular fixed value, $b$. That is, the hyperplane determined by a vector $\vec{a}$ and a shift $b$ is the set of vectors $\vec{x} \in \mathbb{R}^n$ for which \[\vec{a}\cdot \vec{x} = b.\]

The right way to understand this is to notice that a hyperplane through the origin of $\mathbb{R}^n$ is defined as the set of points whose dot product with a particular vector $\vec{a} \in \mathbb{R}^n$ is 0. That is, it is the (n-1)-dimensional subspace of vectors perpendicular or orthogonal to $\vec{a}$. Also note that $\mathbb{R}^n$ is completely filled up by the translates or shifts of this hyperplane through the origin, and since the dot product of any vector $\vec{x} \in \mathbb{R}^n$ with $\vec{a}$ is simply the signed length of its projection in the direction of $\vec{a}$ (in the case $\vec{a}$ has length $1$--in general, it is the signed length of this projection scaled by the length of $\vec{a}$), the hyperplane which is shifted by $b$ from the origin is precisely the set of vectors whose dot product with $\vec{a} \in \mathbb{R}^n$ is $b$.

Even better, if you believe that your decision boundary is a hyperplane determined by orthogonal vector $\vec{a}$ and shift $b$, then the algorithm for solving the decision problem is suuuuuuper simple: If $\vec{a}\cdot \vec{x} > b$, then "Yes." If $\vec{a} \cdot \vec{x} < b$, then "No."

Great!

Extracting confidence ratings from linearly separable data

Of course, in the linearly separable situation, there's always the possibility that you'll have a data point land right on the decision boundary hyperplane. Also, data is noisy and so it's reasonable to have lower confidence about your classification of data points that are very close to the decision boundary. This is where sigmoid functions, like $\frac{1}{1+ e^{-t}}$ are useful. A sigmoid function maps $0$ to $0.5$, negative values to the interval $(0,0.5)$, positive values to the interval $(0.5,1)$. Moreover, a sigmoid function converges quickly to $0$ for negative $t$ and quickly to $1$ for positive $t$.

So in practice what a sigmoid function does is translate the position of a point with respect to the decision boundary to a number that can be interpreted as the probability that the answer is "Yes." If you're right on the decision boundary, that number is 0.5 (50% certainty that they answer is "Yes"-makes sense!), and as you get further and further away from the decision boundary, your confidence in your answer increases. On one side, the probability approaches $1$ quickly (i.e., you quickly gain confidence that the answer is "Yes"), and on the other side, the probability approaches $0$ quickly (i.e., you quickly gain confidence that the answer is "No").

Upshot: Let $\sigma(t) := \frac{1}{1 + e^{-t}}$. If your data is linearly separable by a hyperplane defined by vector $\vec{a} \in \mathbb{R}^n$ and shift $b \in \mathbb{R}$, and you want to determine the "probability" that a particular point $\vec{x} \in \mathbb{R}^n$ corresponds to a "Yes" answer, just calculate \[\sigma(\vec{a}\cdot\vec{x} - b).\]

Note: the "noisier" you believe your data is, the farther away you will need to move from the decision boundary before you are truly confident in your assessment. In other words, the shallower you will want to make the "S" in the graph of your sigmoid function. Do this by replacing $-t$ with $-ct$ for $0< c<1$. Likewise, if you believe your data is less noisy, choose $1<c$ to make a your sigmoid function more closely resemble a step function.

More importantly, the assumption that your data is linearly separable is really much too strong in most cases. In most situations, assuming this will lead to pretty poor results. I mean, who's to say that the "Yes" part of your space is even connected? Or contractible? Maybe it has interesting topology. Who the heck knows? But it's a reasonable first pass for a newbie.

OK, that's probably enough for a very first post. Next time, I'll actually explain what a machine learning algorithm does in the linearly separable situation, in preparation for talking a bit about neural networks and trying to get at what they're up to.