Posts

Posted on

11. Learning: Identification Trees, Disorder

Identification Trees

Problems

  • Non-numeric data
  • Not all characteristics matter
  • Some do matter but not all of the time
  • Cost: certain tests may be more expensive than others

Occam’s razor

The objective is to build the smallest tree possible (to reduce costs and computation) and because the simplest explanation is always the best.

Testing data

Small data sets

The different tests upon the data can be ranked by the homogeneous groups it produces and the total number of items in each homogeneous group.

Using the most efficient tests first, the remaining ambiguous data is checked through the other tests and so until until all the data is sorted.

Large data sets

For large data sets, no tests may divide the data in homogeneous group. The results of tests must therefore be ranked according to their level of disorder.

If P = Positive results, N = negative results, T = total

Disorder (Set) = – P/T log[2] ( P/T )  – N/T log[2] ( N/T )

The resulting curve of this equation is a parabolic curve with max at y = 1 for x = 1/2 and min at y = 0 for x = {0,1}

So the quality of each test can be defined as follows:

Quality (Test) = Sum[for each set produced] ( Disorder (Set) ) * Number of samples in set / Number of samples handed by test

Decision boundaries

Contrary to nearest neighbors, identification tests always separate the data space in two equal parts parallel to the space axis.

Posted on

10. Introduction to Learning, Nearest Neighbors

Learning

Regularity: “Bulldozer computing”

  • Nearest neighbors: pattern recognition
  • Neural nets: mimic biology
  • Boosting: theory

Constraints: human-like learning

  • One-shot
  • Explanation-based learning

Nearest neighbor

A detection mechanism generates a vector of features. These features are converted in a vector of values that is compared to a library of possibilities to find the closest match in order to recognize patterns, objects, etc.

Method: Standard objects (ex: electric covers) are positioned in a space according to recognizable characteristics (ex: size, hole size). Decision boundaries between the standards are then established in the space to define areas of attribution to a nearest neighbor. Objects are then sorted according to which area the belong to.

Another method of sorting objects (ex: newspaper articles) to recognize could be to compare the angle of their vectors in the space with the vectors of the standard objects.

In the case of a robotic arm, instead of solving equations of angles at the joints which cannot be implemented in real life, due to friction and wear, a table of values is gathered at each position during a learning phase. During the working phase, the closest set of values from the table is used to complete the task.

Problems

  • Spread: Values can be concentrated in the space making it difficult to discern objects. Solution: norm the data using statistical analysis.
  • Subject matter: make sure to measure values that do actually make a difference between objects, not values that generate confusing results.
  • Relevancy: use data that is relevant to the matter at hand, not just any data that is independent from the target results.
Posted on

9. Constraints: Visual Object Recognition

Borders and faces orientation

Discerning borders of objects and face orientation with vectors, an initial computer vision theory seemed plausible but too difficult to implement.

Orthographic projection

In orthographic projection, the correspondence of a system of points of three known objects and one unknown object creates a system of equations with a unique solution of parameters. If this solution can be applied  to all points of the unknown object, the object is recognized.

This works with manufactured objects but not so well with natural objects.

“Goldilocks principle”

Don’t search for features that are too big / complex, and not too small / simple. Not too big, not too small.

Face recognition

Use an integral of different recognizable points on a face: search for a correlation of 2 eyes + 1 nose, 1 nose + 1 mouth, etc.

Posted on

8. Constraints: Search, Domain Reduction

https://www.youtube.com/watch?v=d1KyYyLmGpA

Domain Reduction Algorithm

Vocabulary

  • Variable v: something that can have an assignment
  • Value x: something that can be assigned
  • Domain d: set of all different values
  • Constraint c: limit on variable values

With a depth-first search, the domain reduction algorithm goes back up one node when it is unable to comply with a constraint. It reduces the domain of available variables at node n-1 to make sure it will have an unused variable in the next node n.

By considering more variables (propagating to neighboring states in the US map coloring example), the domain can be reduced to a single value at a certain node.

Solving the problem faster

By working on the most constraints nodes first, the algorithm doesn’t have to work back up as much as if it starts with least constraints first.

Obviously, the main constraint of using only a small number of values (colors in the example) is the most limiting one. Being able to increase the number of values can drastically simplify the problem.

In case of uncertainty on the exact number of values, find a range of values that solve the problem (such as in the airplane assignment example).

Resources allocations

  1. Used most constraints first
  2. Propagate through domain reduced to single algorithm
  3. In the absence of definite result, find a narrow range of max values where it doesn’t work, and min values where it does
Posted on

7. Constraints: Interpreting Line Drawings

Computer vision

Empirical approach

Using lines on pictures of real-world objects, the edges between shapes could serve to identify the number of objects in it.

The different intersections possible generally form two types of trihedral vertexes to identify shapes:

  • arrow vertexes
  • fork vertexes

Theoretical approach

A second approach uses convex and concave lines and boundaries between objects in a more theoretical domain, to identify trihedral vertexes between 3 faces, where objects are always considered in a general position of perspective where unusual cases are not considered.

These constraints create 18 different possibilities of junctions. With this catalog of positions, shapes can be identified to know if an object can exist in the domain defined above… but not in the real world.

Towards robot vision

Adding cracks, shadows, non-trihedral vertexes and light to the theoretical approach, the domain complexity increased with more than a 1000 junctions possibilities.

However, in the same manner as the theoretical approach, an algorithm that identifies junctions one by one with this catalog, a much wider array of objects can be identified to determine what their actual shape is and or if some ambiguity is left.