Machine Learning Cheat Sheet Part 4 - Polynomial Regression and Normal Equation

1. Polynomial Regression

The hypothesis function does not need to be linear (a straight line) if it does not fit the data well. It's possible to change the behaviour of the curve of the hypothesis function by making it a quadratic, cubic or square root function (or any other form).

We can combine existing feature into one. For example, combine $x_1$ and $x_2$ into a new feature $x_3$ by taking $x_1 \times x_2$.

If the hypothesis function is:

$ h_\theta (x) = \theta_0 + \theta_1 x $

then we can create additional features based just on $x_1$ to get a quadratic function:

$ h_\theta (x) = \theta_0 + \theta_1 x + \theta_2 x^2 $

or the cubic function:

$ h_\theta (x) = \theta_0 + \theta_1 x_1 + \theta_2 x_1^2 + \theta_3 x_1^3 $

where new features are:

$ x_2 = x_1^2 $ and $ x_3 = x_1^3 $, so the function becomes:

$ h_\theta (x) = \theta_0 + \theta_1 x_1 + \theta_2 x_2 + \theta_3 x_3 $

NOTE: if features are chosen this way then feature scaling becomes very important.


2. Normal Equation

Normal Equation is the method to solve $\Theta$ analytically rather than using iterations with gradient descent. Normal Equation method will minimise $J$ by explicitly taking its derivatives with respect to the $\theta_j$'s and setting them to zero. This approach finds the optimum $\theta$ without iteration.

$m$ - number of training examples
$n$ - number of features

The Normal Equation formula is:

$ \Theta = (X^{T}X)^{-1}X^Ty $

Negative side-effects:

1. Normal Equation calculates matrix inversion $ (X^{T}X)^{-1} $ that has complexity $O(n^3)$ - this makes it slow if there is a very large number of features. In practice, when $n$ exceeds 10,000 it might be a good idea to switch from Normal Equation to iterations with Gradient Descent.

2. $X^{T}X^{-1}$ could be non-invertible (singular, degenerate). There are two possible solutions for such cases:

1) In Octave use $pinv(X'*X)*X'*y$ rather than $inv$ function as $pinv$ function might still be able to calculate the value of $\theta$ even if $X^{T}X^{-1}$ is non-invertible.

2) Common causes for non-invertibility could be:

• Redundant features that are closely related (i.e. they are linearly dependent), or
• There are too many features (e.g. $m\leqslant n$).

Solution to these problems could be:

• Deleting a feature that is linearly dependent on another feature
• Deleting some features or use regularisation when there are too many features.

Comparison of Gradient Descent and Normal Equation

Gradient Descent	Normal Equation
Need to choose $\alpha$	No need to choose $\alpha$
Might need feature scaling	No need for feature scaling
Needs many iterations	No need to iterate
$O(kn^2)$	$O(n^3)$ to calculate inverse of $X^{T}X$
Works well for $n>10,000$	Works well for $n\leqslant10,000$

Machine Learning Cheat Sheet Part 3 - Linear Regression with Multiple Variables

1. Notation:

$ m $ - number of training examples.

$ n = \vert x^{(i)} \vert $ - number of features.

$ x^{(i)} $ - column vector of all the feature inputs of the $ i^{th} $ training example.

$ x_{j}^{(i)} $ - value of feature $ j $ in the $ i^{th} $ training example.

$ \alpha $ - learning rate.


2. Hypothesis:

$ h_\theta(x) = \theta_0 + \theta_1x_1 + \theta_2x_2 + ... + \theta_nx_n $

or
$ h_\theta(x) =  \left[ \begin{array}{cc} \theta_0 & \theta_1 & ... & \theta_n \end{array} \right] \times \left[ \begin{array}{cc} x_1 \\ x_2 \\ ... \\ x_n \end{array} \right] = \Theta^{T}X $

where $ x_0^{(i)} = 1 $ for $ (i \in 1, ..., m) $


3. Parameters:

$ \theta_0, \theta_1, ..., \theta_n $ or $ \Theta $


4. Cost function:

\[
J(\theta_1, \theta_2, ..., \theta_n) = J(\Theta) = \frac{1}{2m} \sum_{i=1}^{m} (h_\theta(x^{(i)}) - y^{(i)})^2
\]
5. Gradient descent:

repeat until convergence:
\[
{
\{
\\
\theta_0 = \theta_0 - \alpha \frac{1}{m} \sum_{i=1}^{m} (h_0(x^{(i)}) - y^{(i)}) \times x_0^{(i)}
\\
\theta_1 = \theta_1 - \alpha \frac{1}{m} \sum_{i=1}^{m} (h_0(x^{(i)}) - y^{(i)}) \times x_1^{(i)}
\\
\theta_2 = \theta_2 - \alpha \frac{1}{m} \sum_{i=1}^{m} (h_0(x^{(i)}) - y^{(i)}) \times x_2^{(i)}
\\
...
\\
\}
}
\]
6. Feature scaling:

This to be applied to the input data (training) set. Features may have significant differences in their values. For example, $ x_1 $ may have values from 100 to 10,000 (e.g. area of a house in $ feet^2 $) while $ x_1 $ may have values from 1 to 6 (e.g. number of bedrooms). It would be a good idea to scale the feature values, so that:
\[
-1 \leqslant x_i \leqslant 1  \\ or \\ -0.5 \leqslant x_i \leqslant 0.5
\]
Feature scaling technique could be a combination of feature scaling and mean normalisation:
\[
x_i = \frac{x_i - \mu_i}{s_i}
\]
where $\mu$ is an average of all the values of feature $x_i$ and $s_i$ is either the range of values $(\max - \min)$ of $x_i$ or their standard deviation. Note that dividing by the range, or dividing by the standard deviation, give different results.


7. Debugging gradient descent using learning rate $\alpha$:

7.1 Value of $J(\theta)$ and number of iterations:

Make a plot of values of cost function $J(\theta)$ (y-axis) over the number of iterations of gradient descent (x-axis). If $J(\theta)$ ever increases, then try to decrease $\alpha$ and repeat.

7.2 Automatic convergence test:

It has been proven that if learning rate $\alpha$ is sufficiently small, then $J(\theta)$ will decrease on each iteration. Declare convergence if $J(\theta)$ decreases by less than $\varepsilon$ in one iteration, where $\varepsilon$ is some small value such as $10^{-3}$. However in practice it could be difficult to choose this threshold value.

7.3 Trade-off:

If $\alpha$ is too small, it could result in slow convergence.
if $\alpha$ is too large,  it may not decrease on each iteration and thus may not converge.

Choose a small $\varepsilon$ and then increase it by $\approx3\times$:
$0.001, 0.003, 0.01, 0.03, 0.1, 0.3, 1, ...$

Machine Learning Cheat Sheet Part 2 - Linear Regression with One Variable

1. Training set: $ (x^{(1)}, y^{(1)}), (x^{(2)}, y^{(2)}), ... (x^{(m)}, y^{(m)}) $

2. Hypothesis: $ h_\theta(x)=\theta_0+\theta_1x $

3. Parameters: $ \theta_0, \theta_1 $

4. Cost function: $J(\theta_0, \theta_1)$ uses parameters $\theta_0$ and $\theta_1$ to check the difference between hypothesis values $h_\theta(x)$ and given values $y$ from training example $(x,y)$:

\[ J(\theta_0, \theta_1) = \frac{1}{2m} \sum_{i=1}^{m} (h_\theta(x^{(i)}) - y^{(i)})^2 \]
5. Goal: minimise cost function

$ min_{\theta_0, \theta_1} J(\theta_0, \theta_1) $

6. Gradient descent algorithm (minimisation of cost function):

$ \alpha $ - learning rate

repeat until convergence:
\[
{
\{
\\
 \theta_0 = \theta_0 - \alpha \frac{1}{m} \sum_{i=1}^{m} (h_0(x^{(i)} - y^{(i)})
\\
\theta_1 = \theta_1 - \alpha \frac{1}{m} \sum_{i=1}^{m} (h_0(x^{(i)} - y^{(i)})\times x^{(i)}
\\
\}
}
\]
(update $ \theta_0 $ and $ \theta_1 $ simultaneously!)

Machine Learning Cheat Sheet Part 1 - Supervised and Unsupervised Machine Learning

1. Machine Learning definition:

Field of study that gives computer the ability to learn without being explicitly programmed.

Arthur Samuel (1959)

A computer program is said to learn from experience E with respect to some task  T and some performance measure P, if its performance on T, as measured by P, improves with experience E.

Tom Mitchel (1998)

2. Supervised Machine Learning

Supervised machine learning is the task of inferring a function from labeled training data. The training data consist of a set of training examples. Each example is a pair consisting of an input value/s (usually a vector) and a known output value. A supervised learning algorithm analyses the training data and produces an inferred function, which can be used for mapping new examples. An optimal scenario will allow for the algorithm to correctly labels unseen instances.

The inferred function could represent:

• regression - predict continuous valued output, or
• classification or categorisation - predict discrete valued output, for example, 0 and 1.

3. Unsupervised Machine Learning

Unsupervised machine learning is the task of inferring a function to describe hidden structure from unlabelled data (see Cocktail Party Effect).

Machine Learning Cheat Sheet - Introduction

This is a summary of my notes taken on Machine Learning course that I completed on Coursera. It was taught by Professor Andrew Ng, Associate Professor at Stanford University, Chief Scientist at Baidu and Chairman/Co-founder at Coursera. The notes include main math formulas and some practical tips mentioned during the course. Covered topics are:

1. Supervised and unsupervised machine learning
2. Linear regression with one variable
3. Linear regression with multiple variables
4. Polynomial regression and Normal Equation
5. Logistic regression (Classification)
6. (to be continued - work in progress)

Graph Database OrientDB

Neo4j's book 'Graph Databases' provides an easy introduction to the topic (google for its PDF version). Try to concentrate on schema design principles supported by practical examples and skip learning their query language Cypher unless you want to use Neo4j for your projects.

On Dec 7th, 2016 there was a good webinar about migrating data from Neo4j to OrientDB. It was surprising to see what OrientDB has under the hood - nice SQL, indexing, clustering, sharding, security model and visual representation of actual graphs stored in the database. Also OrientDB could be used as a scheme-less or schema-based  graph-oriented database or a document-oriented database or use both models (graph and document) simultaneously. Unfortunately it doesn't run on Java ME yet (it's in its roadmap though). A shortened earlier version of this webinar is available on Youtube. Below is a copy of questions and answers popped up during the presentation:

Q: Is OrientDB enterprise edition available under an open source license as well as commercial?
A: OrientDB Enterprise Edition is only commercial, but the Community is licensed as Open Source with Apache2. You can try Enterprise Edition for 45 days before to decide.

Q: LIke a viral license (AGPL) that would allow us to use enterprise edition if we open source the code we use with orient?
A: OrientDB Community Edition is licensed as Apache2, so it's not viral. You can use it for any purpose, even embedding it at no cost.

Q: Which version of OrientDB are you using?
A: OrientDB v2.2.13

Q: Do you offer a startup program? So that small companies can use enterprise edition at no/low cost?
A: Absolutely. We provide 50% of discount for startups. No hidden costs, it's all on our web site.

Q: when using the object model are ther constraints to consider can i mix match models?
A: The object model (JPA-like) doesn't work very well with the graph one, so we sugget to pick one of them. The Graph model is more powerful and supported.

Q: Does the choice of schema mode influence the performance of standard or index-based lookups?
A: Yes, using the schema makes the database much smaller (property names are not saved in the record) and therefore a smaller database is faster.

Q: Inaccurate to say that Neo4j does not support inheritance or polymorphic queries- it does with labels.
A: Neo4j labels are not polymorphic and there is not such concept in Neo4j. For more information look at http://stackoverflow.com/questions/24873067/how-to-work-with-type-hierarchies-in-neo4j, specially at the last answer/comment.

Q: How would you compare orient's extended SQL to Gremlin?
A: SQL and Gremlin are quite different in many senses, SQL is declarative, Gremlin is more oriented to step-by-step traversal/filtering. Please consider that both OrientDB and Neo4j support Gremlin, that is a standard, so you can easily migrate from one to another

Q: How do you do variable depth queries in orientdb? e.g. min depth 1 to max depth 5
A: you can use a mix of TRAVERSE and SELECT, like "SELECT FROM (TRAVERSE ... WHILE $depth < 10) WHERE $depth > 3. Or you can use the MATCH syntax, where you have distinct WHILE and WHERE conditions, one for the traversal and the other for filtering

Q: Can you query across clusters? For example if the graph is fully connected?
A: Yes, OrientDB will manage the query for you. Of course the query performance depends on how many hops you do between clusters

Q: So a cluster is a cut of the graph essentially?
A: Yes, exactly

Q: If you can write to multiple mastes, how does orient handle consistency / transactions?
A: OrientdB supports distributed transactions that assure the concistency of the database by using a 2-phase locking protocol across the servers.

Q: If you can write to multiple mastes, how does orient handle consistency / transactions?
A: Consistency is based on MVCC and quorum based consensus.

Q: What requirements does OrientDB have for Java runtime? Will it run on Java ME?
A: In terms of runtime, it only needs Java SE (no Java ME supported for now)

Q: What version of Neo4j are you comparing OrientDB to? And what version of OrientDB are you talking about?
A: We compared last GA version of both products, so Neo4j 3.0.6 and OrientDB 2.2.13

Q: Does orient work with LDAP / active directory?
A: OrientDB supports Kerberos and you can import LDAP users

Q: Neo4j seems to be a much larger company (in fact I think they just raised a bunch of money). Why do you think it is possible for orient to have so many more features than Neo4j while being a much smaller company?
A: Receiving funding is not a guarantee the company will be there tomorrow. Look at what's happened to RethinkDB and other companies that have received funding, but weren't focused on building a sunstainable business. OrientDB company is profitable since 3 years ago and its investors are its clients. We believe this is the only healthy business :-)

Q: Does key/value model (like Redis) stays in memory? We use Redis for the speed (memory residence). How will the speed be affected if we drop Redis and move to Orient for Key/Value?
A: As "just" Key/Value DBMS, Redis is faster, so if you just need a K/V we suggest to use Redis. But if your domain is more complex and requires documents, graphs, etc, then the Multi-Model approach is the best in terms of global performance and complexity.

Q: What is the theoretical/practical limit to the number of classes in ODB?
A: in current release you can have up to 32.000 data files, so if you have one per class you can have 32.000 classes

Q: What are the most common use cases for your customers in production now? How do these differ from the use-cases of customers using Neo4j?
A: While Neo4j is "only" a Graph Database, OrientDB can be used on a wider number of use cases, especially when an Operational database is required. For Operational I mean a primary database, while Neo4j in 99% of the cases is used as a secondary database, mostly for analytics with data loaded from a RDBMS (the primary one).

Q: Does the graph have size limits? Please give an example of a BIG graph already deployed in OrientDB.
A: These are the limitations: http://orientdb.com/docs/2.2/Limits.html. You can create up to 302,231,454,903 Trillion of vertices and edges, it should be enough :-) The biggest installation is for an energy company with +100 servers.

Alibaba Cloud

Alibaba's statement on IP EXPO LONDON was plain and clear - tell us what you need and we'll do it for you, let's work together for our mutual benefit.

It didn't take long - Alibaba Cloud came to Europe. Although Alibaba has a quite efficient payment system that they technically polished in China while processing huge number of transactions on the daily basis, in Europe they started with offering just traditional cloud infrastructure. I can't wait and see what kind of other offers would follow.

How Alibaba presence looks from a consumer perspective? I've got a quick example - during Alibaba's 11.11 event I bought two 5000LM X800 'tactical' torches (they are great for cycling!) for a half price of one. I got them from an eBay seller who most likely proxied Alibaba transaction on that day.

If supply chain, online catalogues, shopping carts, checkouts and delivery of purchased items are all done under the same umbrella (Alibaba), what would happen to current distributors of Chinese goods in Europe and programmers that provide support for their online transactions? How would Amazon and eBay compete with Alibaba?

What kind of services (MaaS, SaaS, PaaS, etc) and APIs would Alibaba provide for its European infrastructure? I hope we'll find it out pretty soon.