Лекция 9: Метод предельных упрощений (МПУ) По тому, как организован процесс обучения распознающих систем, четко выделяются два подхода к проблеме ОРО. Первый основан на построении сложных разделяющих поверхностей в случайно выбранных пространствах, а во втором центр тяжести проблемы переносится на достижение понимания принципов формирования такого описания объектов, в рамках которого сам процесс распознавания чрезвычайно прост. Обучение в этом случае рассматривается как некий процесс конструирования пространств для решения конкретных задач.

В МПУ предполагается, что разделяющая функция задается заранее в виде линейного (самого простого) полинома, а процесс обучения состоит в конструировании такого пространства минимальной размерности, в котором заранее заданная наиболее простая разделяющая функция безошибочно разделяет обучающую последовательность. МПР назван так потому, что в нем строится самое простое решающее правило в пространстве небольшой размерности, т. е. в простом пространстве.

Пусть на некотором множестве объектов V заданы два подмножества и, определяющих собой образы на обучающей последовательности V. Рассмотрим i-е свойство объектов, такое, что некоторые объекты обучающей последовательности этим свойством обладают, а другие нет. Пусть заданным свойством обладают объекты, образующие подмножество, а объекты подмножества этим свойством не обладают ( ). Тогда i-е свойство называют признаком первого типа относительно образа, если выполняются соотношения: и (1) И признаком второго типа, если выполняются условия: и (2)

Если же выполняются соотношения и (3) и(4) То i-е свойство считается признаком первого типа относительно образа то это же свойство объявляется признаком второго типа относительно образа Если свойство не обладает ни одной из приведенных особенностей, то оно не относится к признакам и не участвует в формировании пространства.

Одинаковые признаки это два признака и, порождающие подмножества, такие, что (5) Доказано утверждение, смысл которого заключается в том, что если пространство конструировать из однотипных, но неодинаковых признаков, то в конце концов будет построено такое пространство, в котором обучающая последовательность будет безошибочно разделена на два образа линейным, т. е. самым простым, решающим правилом. V Рис. 1

Метод предельных упрощений состоит в том, что в процессе обучения последовательно проверяются всевозможные свойства объектов и из них выбираются только такие, которые обладают хотя бы одной из особенностей, определяемых соотношениями (1) - (4). Такой отбор однотипных, но неодинаковых признаков продолжается до тех пор, пока при некотором значении размерности пространства не наступит безошибочное линейное разделение образов на обучающей последовательности. В зависимости от того, из признаков какого типа строится пространство, в качестве разделяющей плоскости выбирается плоскость, описываемая уравнением: (6) Либо уравнением: (7) Каждый объект относится к одному из образов в зависимости от того, по какую сторону относительно плоскости находится соответствующий этому объекту вектор в пространстве признаков размерности n.