## Tuesday, November 4, 2014

### Machine Learning: Linear Regression

A small piece of machine learning: linear regression.
(More like a note to myself hehe)
(Prof. Andrew Ng of Stanford University is damn awesome!)

In linear regression, we want to come up with hypothesis $$h_{\theta} ( \vec{x} ) = \sum_{i=0}^n \theta_i x_i$$ which minimizes the least square function $$J(\theta) = \frac{1}{2} \sum_{i=0}^{m} (h_{\theta}(\vec{x}^i) - y^i)^2$$. To do so, we employ an algorithm called the gradient descent algorithm, which seeks to minimizes $$J(\theta)$$ by incrementally updating $$\theta$$ by going down the steepest gradient. For each $$j$$, we update
$$\theta_j = \theta_j - \alpha \frac{\partial}{\partial \theta_j} J(\theta)$$
until $$J(\theta)$$ converges. $$\alpha$$ is called the learning rate which determines the rate of convergence (somewhat, but if $$\alpha$$ is too big, the algorithm becomes very unstable and diverges). The algorithm is usually repeated in several (to thousands) of iterations.

If we operate the partial derivatives, we get
$$\theta_j = \theta_j - \alpha \sum_{i=0}^m (h_{\theta}(x^i) - y^i)x_j^i$$
From here we have two choices of implementing the algorithm: by batch gradient descent or by stochastic gradient descent, depending on whether we want to iterate through all m data in the training set, or we want to process each one at a time.
I think choosing the appropriate $$\alpha$$ and number of iteration is the key for this algorithm to run and output satisfactory hypothesis function.

Follow up post:
Machine Learning: Closed form Linear Regression