I constantly get questions on how algorithms work, how to build machine learning systems (if you aren't familiar, read my other post first) and how software can detect objects. There is an enormous amount that goes into all of that, but I thought it might be fun to put together a multi-part post on how to create an application that can do all of this, so this is part one. For this part, we aren't going to get into a lot of statistics, utilize databases or do anything too complex, but really jump into the fundamentals of how it all works.
The USPS has been utilizing machine learning for well over a decade to sort mail by the city and zip code. It has been extremely cost effective and highly accurate. Thinking about that, imagine you're writing individual letters and numbers into a 10 by 10 grid. You might get some that look like the following:
While this seems really simple, keep in mind that with a 10 by 10 grid, there are 100 squares, resulting in 1,267,650,600,228,230,000,000,000,000,000 possible combinations (2 to the 100th power). Another way to visualize this would be binary, either 0 or 1. If there is color in the square, let's give it a 1. If not, let's give it a 0. If we put this into C#, we could do this:
int[][] trainingSets = new int[][]
{
new int[] // ' '
{
0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0
},
new int[] // 'N'
{
0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 1, 0, 0, 0, 0, 0, 0, 1, 0,
0, 1, 1, 0, 0, 0, 0, 0, 1, 0,
0, 1, 0, 1, 0, 0, 0, 0, 1, 0,
0, 1, 0, 0, 1, 0, 0, 0, 1, 0,
0, 1, 0, 0, 0, 1, 0, 0, 1, 0,
0, 1, 0, 0, 0, 0, 1, 0, 1, 0,
0, 1, 0, 0, 0, 0, 0, 1, 1, 0,
0, 1, 0, 0, 0, 0, 0, 0, 1, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0
},
new int[] // 'N'
{
0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 1, 1, 0, 0, 0, 0, 0, 1, 0,
0, 1, 1, 1, 0, 0, 0, 0, 1, 0,
0, 1, 0, 1, 1, 0, 0, 0, 1, 0,
0, 1, 0, 0, 1, 1, 0, 0, 1, 0,
0, 1, 0, 0, 0, 1, 1, 0, 1, 0,
0, 1, 0, 0, 0, 0, 1, 1, 1, 0,
0, 1, 0, 0, 0, 0, 0, 1, 1, 0,
0, 1, 0, 0, 0, 0, 0, 0, 1, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0
},
new int[] // 'i'
{
0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 1, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 1, 0, 0, 0, 0, 0,
0, 0, 0, 0, 1, 0, 0, 0, 0, 0,
0, 0, 0, 0, 1, 0, 0, 0, 0, 0,
0, 0, 0, 0, 1, 0, 0, 0, 0, 0,
0, 0, 0, 0, 1, 0, 0, 0, 0, 0,
0, 0, 0, 0, 1, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0
},
new int[] // 'i'
{
0, 0, 0, 0, 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, 0,
0, 0, 0, 0, 1, 1, 0, 0, 0, 0,
0, 0, 0, 0, 1, 1, 0, 0, 0, 0,
0, 0, 0, 0, 1, 1, 0, 0, 0, 0,
0, 0, 0, 0, 1, 1, 0, 0, 0, 0,
0, 0, 0, 0, 1, 1, 0, 0, 0, 0,
0, 0, 0, 0, 1, 1, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0
},
new int[] // 'i'
{
0, 0, 0, 0, 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, 0,
0, 0, 0, 0, 1, 1, 0, 0, 0, 0,
0, 0, 0, 0, 1, 1, 0, 0, 0, 0,
0, 0, 0, 0, 1, 1, 0, 0, 0, 0,
0, 0, 0, 0, 1, 1, 0, 0, 0, 0,
0, 0, 0, 0, 1, 1, 0, 0, 0, 0,
0, 0, 0, 0, 1, 1, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0
},
new int[] // 'A'
{
0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 1, 1, 1, 1, 1, 1, 1, 1, 0,
0, 1, 0, 0, 0, 0, 0, 0, 1, 0,
0, 1, 0, 0, 0, 0, 0, 0, 1, 0,
0, 1, 1, 1, 1, 1, 1, 1, 1, 0,
0, 1, 0, 0, 0, 0, 0, 0, 1, 0,
0, 1, 0, 0, 0, 0, 0, 0, 1, 0,
0, 1, 0, 0, 0, 0, 0, 0, 1, 0,
0, 1, 0, 0, 0, 0, 0, 0, 1, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0
},
new int[] // 'A'
{
0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 1, 1, 1, 1, 1, 1, 0, 0,
0, 0, 1, 0, 0, 0, 0, 1, 0, 0,
0, 0, 1, 0, 0, 0, 0, 1, 0, 0,
0, 0, 1, 1, 1, 1, 1, 1, 0, 0,
0, 0, 1, 0, 0, 0, 0, 1, 0, 0,
0, 0, 1, 0, 0, 0, 0, 1, 0, 0,
0, 0, 1, 0, 0, 0, 0, 1, 0, 0,
0, 0, 1, 0, 0, 0, 0, 1, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0
},
new int[] // 'T'
{
0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 1, 1, 1, 1, 1, 1, 1, 1, 0,
0, 1, 1, 1, 1, 1, 1, 1, 1, 0,
0, 0, 0, 0, 1, 1, 0, 0, 0, 0,
0, 0, 0, 0, 1, 1, 0, 0, 0, 0,
0, 0, 0, 0, 1, 1, 0, 0, 0, 0,
0, 0, 0, 0, 1, 1, 0, 0, 0, 0,
0, 0, 0, 0, 1, 1, 0, 0, 0, 0,
0, 0, 0, 0, 1, 1, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0
},
new int[] // 'E'
{
0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 1, 1, 1, 1, 1, 1, 1, 1, 0,
0, 1, 0, 0, 0, 0, 0, 0, 0, 0,
0, 1, 0, 0, 0, 0, 0, 0, 0, 0,
0, 1, 1, 1, 1, 1, 1, 1, 1, 0,
0, 1, 0, 0, 0, 0, 0, 0, 0, 0,
0, 1, 0, 0, 0, 0, 0, 0, 0, 0,
0, 1, 0, 0, 0, 0, 0, 0, 0, 0,
0, 1, 1, 1, 1, 1, 1, 1, 1, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0
},
new int[] // 'e'
{
0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 1, 1, 1, 1, 0, 0, 0,
0, 0, 1, 0, 0, 0, 0, 1, 0, 0,
0, 1, 0, 0, 0, 0, 0, 0, 1, 0,
0, 1, 0, 0, 0, 0, 0, 0, 1, 0,
0, 1, 1, 1, 1, 1, 1, 1, 0, 0,
0, 1, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 1, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 1, 1, 1, 1, 1, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0
},
new int[] // '2'
{
0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 1, 1, 1, 0, 0, 0, 0,
0, 0, 1, 0, 0, 0, 1, 0, 0, 0,
0, 0, 0, 0, 0, 0, 1, 0, 0, 0,
0, 0, 0, 0, 0, 1, 0, 0, 0, 0,
0, 0, 0, 0, 1, 0, 0, 0, 0, 0,
0, 0, 0, 1, 0, 0, 0, 0, 0, 0,
0, 0, 1, 0, 0, 0, 0, 0, 0, 0,
0, 1, 1, 1, 1, 1, 1, 1, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0
},
new int[] // '3'
{
0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 1, 1, 1, 1, 1, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 1, 0, 0,
0, 0, 0, 0, 0, 0, 0, 1, 0, 0,
0, 0, 0, 1, 1, 1, 1, 1, 0, 0,
0, 0, 0, 0, 0, 0, 0, 1, 0, 0,
0, 0, 0, 0, 0, 0, 0, 1, 0, 0,
0, 0, 1, 1, 1, 1, 1, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0
},
new int[] // '4'
{
0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 1, 0, 0, 0, 1, 0, 0, 0,
0, 0, 1, 0, 0, 0, 1, 0, 0, 0,
0, 0, 1, 0, 0, 0, 1, 0, 0, 0,
0, 0, 1, 0, 0, 0, 1, 0, 0, 0,
0, 0, 1, 1, 1, 1, 1, 1, 0, 0,
0, 0, 0, 0, 0, 0, 1, 0, 0, 0,
0, 0, 0, 0, 0, 0, 1, 0, 0, 0,
0, 0, 0, 0, 0, 0, 1, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0
},
new int[] // '5'
{
0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 1, 1, 1, 1, 1, 1, 0, 0,
0, 0, 1, 0, 0, 0, 0, 0, 0, 0,
0, 0, 1, 0, 0, 0, 0, 0, 0, 0,
0, 0, 1, 1, 1, 1, 1, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 1, 0, 0,
0, 0, 0, 0, 0, 0, 0, 1, 0, 0,
0, 0, 1, 1, 1, 1, 1, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0
}
};
If we create our own character, it might be a sloppy lowercase e and look like the following:
This would be coded in C# as such:
int[] inputData = new int[] // Our Input
{
0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 1, 0, 1, 1, 1, 0, 0,
0, 0, 1, 0, 0, 0, 0, 1, 0, 0,
0, 1, 0, 0, 0, 0, 0, 0, 0, 0,
0, 1, 0, 0, 0, 0, 0, 0, 1, 0,
0, 1, 0, 0, 0, 0, 0, 1, 1, 0,
0, 1, 1, 1, 1, 1, 0, 0, 0, 0,
0, 0, 1, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 1, 1, 1, 1, 1, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0
};
All of this is operating on the concept of a training set, known as supervised learning, where we are giving it several data points and providing labels. A simple version of doing this is setting up a dictionary where we will map the array above with the letter to which it should be considered:
Dictionary trainingSetCharacterLookup = new Dictionary();
// Assign the array values to a letter.
trainingSetCharacterLookup.Add(0, "' '");
trainingSetCharacterLookup.Add(1, "'N'");
trainingSetCharacterLookup.Add(2, "'N'");
trainingSetCharacterLookup.Add(3, "'i'");
trainingSetCharacterLookup.Add(4, "'i'");
trainingSetCharacterLookup.Add(5, "'i'");
trainingSetCharacterLookup.Add(6, "'A'");
trainingSetCharacterLookup.Add(7, "'A'");
trainingSetCharacterLookup.Add(8, "'T'");
trainingSetCharacterLookup.Add(9, "'E'");
trainingSetCharacterLookup.Add(10, "'e'");
trainingSetCharacterLookup.Add(11, "'2'");
trainingSetCharacterLookup.Add(12, "'3'");
trainingSetCharacterLookup.Add(13, "'4'");
trainingSetCharacterLookup.Add(14, "'5'");
int trainingSetCount = trainingSets.Length;
int[] counter = new int[trainingSetCount];
for (int i = 0; i < trainingSetCount; i++)
{
for (int j = 0; j < 100; j++)
{
if (trainingSets[i][j] == inputData[j])
{
counter[i]++;
}
}
}
int maxValue = counter.Max();
int arrayPosition = counter.ToList().IndexOf(maxValue);
Console.WriteLine("This is the data provided: ");
DisplayArray(inputData);
Console.WriteLine("It most closely matches: ");
DisplayArray(trainingSets[arrayPosition]);
Console.WriteLine("This character is: " + trainingSetCharacterLookup[arrayPosition]);
Console.ReadLine();
Finally, the function that outputs the arrays into a readable format:
// Outputs the data in a 10x10
public static void DisplayArray(int[] data)
{
for (int i = 0; i < 100; ++i)
{
if (i % 10 == 0)
{
Console.WriteLine("");
Console.Write(" ");
}
if (data[i] == 0)
Console.Write(" ");
else
Console.Write("1");
}
// Inserts a blank line between characters
Console.WriteLine("");
}
When run, the following is the resulting output:
We aren't taking into consideration numerous items: surrounding context of characters, mapping multiple potential parameters (such as how USPS matches the city to possible zip codes to ensure accuracy of detection), we have a very small training set and we're not saving the information once it has been learned to allow self-learning over time.
This is a simple frequency calculation to determine which is closest in the training set, but it illustrates how it all fits together and is the fundamentals on which far more accurate and complex systems are built.