What is Machine Learning? - Part II

Linear Regression with Multiple Variables

Multiple Features

Linear regression with multiple variables is also known as "multivariable linear regression." We now introduce notation for equations where we can have any number of input variables.
$$ \begin{align*} x_j^{(i)} &= \text{value of feature } j \text{ in the }i^{th}\text{ training example} \newline x^{(i)}& = \text{the column vector of all the feature inputs of the }i^{th}\text{ training example} \newline m &= \text{the number of training examples} \newline n &= \left| x^{(i)} \right| \; \text{(the number of features)} \end{align*} $$
Now define the multivariable form of the hypothesis function as follows, accomodating these multiple features:
$$ h_\theta (x) = \theta_0 + \theta_1 x_1 + \theta_2 x_2 + \theta_3 x_3 + \cdots + \theta_n x_n $$
Using the definition of matrix multiplication, our multivariable hypothesis function can be concisely represented as:
$$ \begin{align*} h_\theta(x) = \begin{bmatrix} \theta_0 \hspace{2em} \theta_1 \hspace{2em} ... \hspace{2em} \theta_n \end{bmatrix} \begin{bmatrix} x_0 \newline x_1 \newline \vdots \newline x_n \end{bmatrix} = \theta^T x \end{align*} $$
This is a vectorization of our hypothesis function for one training example; see the lessons on vectorization to learn more. [Note: So that we can do matrix operations with theta and x, we will set $x^{(i)}_0 = 1$, for all values of $i$. This makes the two vectors 'theta' and $x^{(i)}$ match each other element-wise (that is, have the same number of elements: $n + 1$).]

Now we can collect all $m$ training examples each with $n$ features and record them in an $n+1$ by $m$ matrix. In this matrix we let the value of the subscript (feature) also represent the row number (except the initial row is the "zeroth" row), and the value of the superscript (the training example) also represent the column number, as shown here:

What is Machine Learning?

Two definitions of Machine Learning are offered. Arthur Samuel described it as: "the field of study that gives computers the ability to learn without being explicitly programmed." This is an older, informal definition.

Tom Mitchell provides a more modern definition: "A computer program is said to learn from experience E with respect to some class of tasks T and performance measure P, if its performance at tasks in T, as measured by P, improves with experience E."

Example: playing checkers.

E = the experience of playing many games of checkers
T = the task of playing checkers.
P = the probability that the program will win the next game.

Supervised Learning

In supervised learning, we are given a data set and already know what our correct output should look like, having the idea that there is a relationship between the input and the output.

Supervised learning problems are categorized into "regression" and "classification" problems. In a regression problem, we are trying to predict results within a continuous output, meaning that we are trying to map input variables to some continuous function. In a classification problem, we are instead trying to predict results in a discrete output. In other words, we are trying to map input variables into discrete categories.

Example:

Given data about the size of houses on the real estate market, try to predict their price. Price as a function of size is a continuous output, so this is a regression problem.

We could turn this example into a classification problem by instead making our output about whether the house "sells for more or less than the asking price." Here we are classifying the houses based on price into two discrete categories.

Robot Navigation - Q learning algorithm

Objective

The aim of this lab is to understand the reinforcement learning subject of the autonomous robots course and implement a reinforcement learning algorithm to learn a policy that moves a robot to a goal position. The algorithm is the Q-learning algorithm and it will be implemented in Matlab.

1 - Introduction

The reinforcement learning algorithm does not force the robot to plan path by using any path planning algorithm, rather the algorithm learns optimal solution by randomly moving inside map for several times. It is an approximation of natural learning process, where unknown problem is solved just by trial and error method. The following sections will briefly discuss about the implementation and the results obtained by the algorithm.

Environment: The environment used for this lab experiment is shown below.

Figure-1: Environment used for the implementation.

States and Actions: The size of the given environment is 20$\times$14 = 280 states. The robot can only do 4 different actions: ←, ↑, →, ↓. Thus, the size of the Q matrices would be 280$\times$4 = 1120 cells.

Dynamics: Dynamics make the robot move towards a direction according to the actions. The robot will move one cell per iteration to the direction of the action that we select, unless there is an obstacle or the wall in front of it, in which case it will stay in the same position.

Reinforcement function: Reinforcement function assigns reward at each cell, +1 for goal cell and -1 otherwise.

Implementing Object Detection Based on Color in Webot Simulator for E-puck

This project was implemented by Richa AGARWAL, Taner GUNGOR and Pramita WINATA.

Abstract-Object detection and recognition is a challenging task in computer vision systems. So it was decided to work with E-puck for the same. But using a real e-puck connected with the system through bluetooth it is diffucult to transfer images captured by the robot's camera. So, it was decided to use Webot simulator for E-puck robot to develope and test the algorithm to detect objects using the color of an object. Where robot scans for the object if detects the goal, it moves in the direction of goal avoiding obstacles, else moves randomly in the arena looking for the goal (red object). The most relevant aspects of the simulator and implementation are explained.
Keywords-Webot simulator, e-puck, path planning

INTRODUCTION
We are implementing a simple object detection algorithm in Webot simulator for E-puck using C controller. The algorithm is designed to detect red objects using E-puck's camera. It is easier to control and grab images from E-puck robot using Webot simulator and controler.

1 - WEBOTS SIMULATOR
Webots is a development environment used to model, program and simulate mobile robots. With Webots the user can design complex robotic setups, with one or several, similar or different robots, in a shared environment. The properties of each object, such as shape, color, texture, mass, friction, etc., are chosen by the user. A large choice of simulated sensors and actuators is available to equip each robot. The robot controllers can be programmed with the built-in IDE or with third party development environments. The robot behavior can be tested in physically realistic worlds. The controller programs can optionally be transferred to commercially available real robots. Webots is used by over many universities and research centers worldwide. The development time you save is enormous.

Figure-1: Webots development stages

Webots allows you to perform 4 basic stages in the development of a robotic project Model, Program, Simulate and transfer as depicted on the Fig. 1.

Understanding k-Nearest Neighbour

Goal

In this chapter, we will understand the concepts of k-Nearest Neighbour (kNN) algorithm.

Theory

kNN is one of the simplest of classification algorithms available for supervised learning. The idea is to search for closest match of the test data in feature space. We will look into it with below image.

In the image, there are two families, Blue Squares and Red Triangles. We call each family as Class. Their houses are shown in their town map which we call feature space. (You can consider a feature space as a space where all datas are projected. For example, consider a 2D coordinate space. Each data has two features, x and y coordinates. You can represent this data in your 2D coordinate space, right? Now imagine if there are three features, you need 3D space. Now consider N features, where you need N-dimensional space, right? This N-dimensional space is its feature space. In our image, you can consider it as a 2D case with two features).

Now a new member comes into the town and creates a new home, which is shown as green circle. He should be added to one of these Blue/Red families. We call that process, Classification. What we do? Since we are dealing with kNN, let us apply this algorithm.

Robot Navigation - Rapidly-Exploring Random Tree Algorithm

Objective

The aim of this post is to understand the rapidly-exploring random tree and implement it in Matlab.

1 - Introduction

A rapidly exploring random tree (RRT) is an algorithm designed to efficiently search nonconvex, high-dimensional spaces by randomly building a space-filling tree. The tree is constructed incrementally from samples drawn randomly from the search space and is inherently biased to grow towards large unsearched areas of the problem. It widely used in autonomous robotic path planning.

2 - The Algorithm

RRTs were proposed as both a sampling algorithm and a data structure designed to allow fast searches in high-dimensional spaces in motion planning. RRTs are progressively built towards unexplored regions of the space from an initial configuration as shown in Figure 1.

Progressive construction of an RRT.

At every step a random $q\_rand$ configuration is chosen and for that configuration the nearest configuration already belonging to the tree $q\_near$ is found. For this a definition of distance is required (in motion planning, the euclidean distance is usually chosen as the distance measure). When the nearest configuration is found, a local planner tries to join $q\_near$ with qrand with a limit distance . If $q\_rand$ was reached, it is added to the tree and connected with an edge to $q\_near$. If $q\_rand$ was not reached, then the configuration $q\_new$ obtained at the end of the local search is added to the tree in the same way as long as there was no collision with an obstacle during the search. This operation is called the Extend step, illustrated in Figure 2. This process is repeated until some criteria is met, like a limit on the size of the tree.

Robot Navigation - A Star Algorithm

Objective

The aim of this lab is to understand the A* algorithm and implement it in Matlab.

1 - Introduction

In computer science, A* is a computer algorithm that is widely used in pathfinding and graph traversal, the process of plotting an efficiently traversable path between points, called nodes. A* achieves better time performance by using heuristics.

2 - The Algorithm

A* uses a best-first search and finds a least-cost path from a given initial node to the goal node. As A* traverses the graph, it follows a path of the lowest expected total cost or distance, keeping a sorted priority queue of alternate path segments along the way.

It uses a knowledge-plus-heuristic cost function of node x to determine the order in which the search visits nodes in the tree. The cost function is a sum of two functions:

1. the past path-cost function, which is the known distance from the starting node to the current node x (denoted g(x))
2. a future path-cost function, which is an admissible "heuristic estimate" of the distance from x to the goal (denoted h(x)).

The h(x) part of the f(x) function must be an admissible heuristic; that is, it must not overestimate the distance to the goal. Thus, for an application like routing, h(x) might represent the straight-line distance to the goal, since that is physically the smallest possible distance between any two points or nodes.

If the heuristic h satisfies the additional condition h(x) = d(x,y) + h(y) for every edge (x, y) of the graph (where d denotes the length of that edge), then h is called consistent. In such a case, A* can be implemented more efficiently. No node needs to be processed more than once and. Now let's look at closely to the each steps.

Robot Navigation - The Rotational Sweep Algorithm

Objective

The aim of this post is to understand the rotational plane sweep algorithm to build a visibility graph and implement it in Matlab.

1 - Introduction

The rotational plane sweep is a path planning algorithm based on topological maps. It is one of the most powerful method of intelligent robot navigation. The basic concepts and details of the algorithm are going to be explained in the next chapter. After that, we are going to see the results.

2 - The Algorithm

Topological map is a simplified map with only relationship between points. It can be represented as a graph:

• nodes are real positions
• edges join positions in the free space.

They include the distance. It is easy to find a path in a topological map. So, the only problem is how to build a topological map? We are going to create visibility graph.

In order to create visibility graph. We should define for a 2D polygonal configuration space

• The nodes $v_{i}$ of the visibility graph include the start location, the goal location, and all the vertices of the configuration space obstacles. 
• The graph edges $e_{ij}$ are straight-line segments that connect two line-of-sight nodes $v_{i}$ and $v_{j}$, i.e., 

\begin{equation} e_{ij} \neq \emptyset \Longleftrightarrow sv_{i} + (1 - s)v_{j} \in cl(Q_{free}) \forall s \in [0, 1] \end{equation}

Robot Navigation - The Wavefront Planner Algorithm

Hi, reader this report was written for the 'Autonomous Robots' labwork. It explains 'The Wavefront Planner Algorithm'. End of this post, you can see the Matlab codes and also the report itself.

1 - Introduction

The theories behind robot maze navigation is immense. It would take several books just to cover the basics. But this labwork only concentrate on the wavefront planner algorithm which is still powerful methods of intelligent robot navigation. The basic concepts and details of the algorithm are going to be explained in the next chapter. After that, we are going to see the results.

2 - The Algorithm

The wavefront algorithm finds a path from point S (start) to point G (goal) through a discretized workspace such as this (0 designates a cell of free space, 1 designates a cell fully occupied by an obstacle):

\[
\begin{bmatrix}
1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\
1 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 1 \\
1 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 2 & 0 & 1 \\
1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 1 \\
1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 1 \\
1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 1 \\
1 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 1 \\
1 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\
1 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\
1 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\
1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 1 \\
1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 1 \\
1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 1 \\
1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\
\end{bmatrix}
\]

Face Recognition

Chapter 1: Introduction

1. Preliminary

In this project, we implemented a face recognition system by using principal component analysis, which is known as PCA. PCA method provide a mathematical way to reduce the dimension of problem.

Since the most elements of a facial image are highly correlated, it is better to extract a set of interesting and discriminative feature of a facial image. Mathematically speaking, we transform the correlated data to independent data. To implement the transform, we employed some linear algebra method such as SVD (Chapter3). The main idea is to obtain Eigenfaces that every face can be regard as a linear combination of these eigenfaces (Chapter4). Then the face recognition problem convert to a mathematic problem: what is the linear combination of a face? In other words, it simplify a problem from 2D to 1D.