Как это тикает

Привет.
Сегодня, я покажу как работает программа распознавания образов. И конечно же, данная статья ничего не имеет общего с ABBY FineReader. Также отмечу, что это статья на 5 минут, здесь вы не найдете теоретических выкладок.
Далее...
Введение
Вместо теории приведу картинку, которая показывает как будет работать программа. Отмечу, что обучать мы будем однослойный перцептрон(нейронную сеть).

Основная часть
Эту программу можно также рассматривать как бинарный классификатор, который основываясь на входном векторе(картинке) генерирует его класс(1 или 0).
Кстати, вот так бы выглядела предыдущая картинка на языке C#:). Во избежания усложнения, демонстрационный пример будет реализован в виде консольного приложения. А вместо картинок будут использоваться в массивы чисел. using System; namespace TestAI { class Program { static void Main(string[] args) { Perceptron p = new Perceptron(1, 25); // обучающая выборка int[][] a = new int[2][]; a[0] = new int[25] { 0, 1, 1, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 1, 1, 0 }; a[1] = new int[25] { 0, 0, 1, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 0 }; // обучение for (int i = 0; i < a.Length; i++) { p.Teach(a[1], new int[1] { i }); } // Будем распознавать этот вектор int[] input = new int[25] { 0, 0, 1, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 0 }; // Распознаем int[] output = p.Recognize(input); // Класс(1 или 0) Console.WriteLine(output[0]); } } } В качестве реализации однослойного перцептрона возьмем решение предложенное на хабре и перепишем его на шарпе. using System; namespace TestAI { class Perceptron { private Neuron[] neurons; int m; int n; public Perceptron(int n, int m) { this.n = n; this.m = m; neurons = new Neuron[n]; for (int i = 0; i < n; i++ ) { neurons[i] = new Neuron(m); } } public int[] Recognize(int[] x) { int[] y = new int[n]; for (int i = 0; i < n; i++) { y[i] = neurons[i].Transfer(x); } return y; } public void Teach(int[] x, int[] y) { int d = 0; int v = 1; int[] t = Recognize(x); while (!Equal(t, y)) { for (int j = 0; j < n; j++) { d = y[j] - t[j]; neurons[j].Teach(v, d, x); } t = Recognize(x); } } public bool Equal(int[] v1, int[] v2) { if (v1.Length != v2.Length) { return false; } for (int i = 0; i < v1.Length; i++ ) { if (v1[i] != v2[i]) { return false; } } return true; } } class Neuron { private int[] w; private int s = 50; public Neuron(int m) { w = new int[m]; for (int i = 0; i < w.Length; i++) { w[i] = 0; } } public int Transfer(int[] x) { return Activate(Add(x)); } public void Teach(int v, int d, int[] x) { for (int i = 0; i < w.Length; i++) { w[i] += v * d * x[i]; } } private int Add(int[] x) { int nec = 0; for (int i = 0; i < x.Length; i++ ) { nec += w[i] * x[i]; } return nec; } private int Activate(int nec) { return (nec >= s) ? 1 : 0; } } } Заключение
В данной статья, я попытался максимально доступно показать, как распознавать образы.

Привет!
Сегодня, я расскажу про стемминг и его применение.

Что такое стемминг?
Стемминг - это процесс нахождения основы слова. Например, для слова "приставка" основой будет "приставк", а корнем слова "став".

Далее... Зачем нужен стемминг?
Обычно в простых поисковых системах, в которых не требуется учет морфологии, применяется стемминг для обобщения пользовательских запросов.
В этих поисковых системах документы разбиваются на множества основ слов.
Поиск осуществляется по основам слова.

Реализация алгоритма стемминга на C#
using System.Text.RegularExpressions; using System; namespace Stemmer.RU { /// <summary> /// Stemmer /// </summary> class Porter { public const string VERSION = "0.2"; private const string VOWEL = "аеиоуыэюя"; private const string PERFECTIVEGROUND = "((ив|ивши|ившись|ыв|ывши|ывшись)|((?<=[ая])(в|вши|вшись)))$"; private const string REFLEXIVE = "(с[яь])$"; private const string ADJECTIVE = "(ее|ие|ые|ое|ими|ыми|ей|ий|ый|ой|ем|им|ым|ом|его|ого|еых|ую|юю|ая|яя|ою|ею)$"; private const string PARTICIPLE = "((ивш|ывш|ующ)|((?<=[ая])(ем|нн|вш|ющ|щ)))$"; private const string VERB = "((ила|ыла|ена|ейте|уйте|ите|или|ыли|ей|уй|ил|ыл|им|ым|ены|ить|ыть|ишь|ую|ю)|((?<=[ая])(ла|на|ете|йте|ли|й|л|ем|н|ло|но|ет|ют|ны|ть|ешь|нно)))$"; private const string NOUN = "(а|ев|ов|ие|ье|е|иями|ями|ами|еи|ии|и|ией|ей|ой|ий|й|и|ы|ь|ию|ью|ю|ия|ья|я)$"; private const string RVRE = "^(.*?[аеиоуыэюя])(.*)$"; private const string DERIVATIONAL = "[^аеиоуыэюя][аеиоуыэюя]+[^аеиоуыэюя]+[аеиоуыэюя].*(?<=о)сть?$"; private const string SUPERLATIVE = "(ейше|ейш)?"; /// <summary> /// Parses stemm of the word /// </summary> /// <param name="word"></param> /// <returns>Stemm of the word</returns> public string Stemm(string word) { word = word.ToLower(); word = word.Replace("ё", "е"); if (IsMatch(word, RVRE)) { // Step 1 if (!Replace(ref word, PERFECTIVEGROUND, "")) { Replace(ref word, REFLEXIVE, ""); if (Replace(ref word, ADJECTIVE, "")) { Replace(ref word, PARTICIPLE, ""); } else { if (!Replace(ref word, VERB, "")) { Replace(ref word, NOUN, ""); } } } // Step 2 Replace(ref word, "и$", ""); // Step 3 if (IsMatch(word, DERIVATIONAL)) { Replace(ref word, "ость?$", ""); } // Step 4 if (!Replace(ref word, "ь$", "")) { Replace(ref word, SUPERLATIVE, ""); Replace(ref word, "нн$", "н"); } } return word; } private bool IsMatch(string word, string matchingPattern) { return new Regex(matchingPattern).IsMatch(word); } private bool Replace(ref string replace, string cleaningPattern, string by) { string original = replace; replace = new Regex(cleaningPattern, RegexOptions.ExplicitCapture| RegexOptions.Singleline ).Replace(replace, by); return original != replace; } } } Применение стеммера
using System; using Stemmer.RU; namespace Stemmer { class Program { static void Main(string[] args) { Porter p = new Porter(); while (true) { Console.WriteLine("Введите слово:"); string input = Console.ReadLine(); if (input != "выйти") { Console.WriteLine("Основа слова \"" + input + "\": " + p.Stem(input)); } else { break; } } } } } Источники
Стемминг
Russian stemming algorithm
Эвристическое (без словаря) извлечение корня из русского слова
Вероятностный морфологический анализатор русского и украинского языков