[МРО] Методичка МРО

Следует обратить внимание на то, что с увеличением числа

введенных в машину объектов и количества секущих плос-

костей противоречия будут возникать между объектами и

оппонентами, лежащими все ближе и ближе к границам областей

А, В, С. Область пространства, в которой возможны противо-

речия, все время сужается, и вероятность возникновения проти-

воречия при появлении нового объекта становится все меньше и

меньше, так как убывает число неправильно поименованных

областей. Частота возникновения противоречий может, таким

Н

образом, служить критерием завершения первой части алгоУ-

ритма. Закончим первую часть алгоритма проведением плоско-

стиVII. Сложившаясяситуацияприведенанарис. 1.12. Т

II

Б

IV

III

й

I

2

и

3

р

6

Y

о

10

т

8

VI

1

9

Z

и

VI I

4

7

V

з

5

о

п

Рис. 1.12. Разбиение пространства на ряд областей

е

Р

Пространство разбито на ряд областей. Некоторые из них

ной штриховкой. Остальные области (их горазо больше, чем

первых) остались «пустыми» и ни к какому образу не отнесены.

Совершенно ясно, что на этом нельзя заканчивать процесс

обучения. Подлежащая определению новая точка может попасть

в «пустую» область, и ее нельзя будет отнести ни к какому

образу. Необходимо каким-то способом поименовать все без

исключения области пространства. Продолжение первой части

алгоритма, разумеется, не может привести к этой цели, так как

число «пустых» областей будет все быстрее и быстрее опережать

Н

число появившихся точек. Обратимся к основной нашей идееУ–

предположению о компактности множеств точек, соответствую-

щих образам. Исходя из этого предположения естественноТотне-

Б

сти «пустые» области к тем же образам, что и какая-нибудь из

соседних поименованных областей. При этом такая манипу-

ляция с «пустыми» областями, окруженными одноименными

частями пространства, будет совершенно однозначна и не при-

областями

ведет к ошибкам (например, пустая область y на рис. 1.12 вполне

определенноотноситсякобразу А).

й, лежащими у границ

Только

при

операциях с

множеств, будутвозможнынеоднозначностьиошибки. «Пустая»

область z (см. рис. 1.12), нап

, может быть ошибочно отне-

сенакобразуС.

т

имер

Расширение поимен ванных частей пространства можно

костей, ра

деляющие одноименные области. Оставшиеся пос-

представить как выбрасываниео

кусков плоскостей, отделяю-

з

щих «пустые» облас и от соседних поименованных. Разуме-

ется, как л шн

, могут выбрасываться также и куски плос-

о

ле так й

перации куски плоскостей и образуют искомую

разделяющую гиперповерхность.

Весьма важно выбрасывать куски плоскостей более или менее

Р

равномерно по пространству. Не соблюдая этого правила, можно

прийти к заведомо неправильной разделяющей поверхности.

Если, например, начав с некоторой поименованной области,

еприсоединить к ней все соседние «пустые», к образовавшейся

пространство отнести к тому же образу, что и исходная область,

ибо после окончания первой части алгоритма поименованные

области, как редкие островки, «затеряны» среди областей не

поименованных. На рис. 1.13 заштрихована область, которую

можно отнести к образу С, если действовать таким методом,

начинаясоднойизпоименованныхобластейэтогообраза.

У

Т

Н

Б

й

и

р

Рис. 1.13. Область, отнесенная к образу С

Для того чтобы обеспеч ть более ли менее равномерное

плоскости

выбрасывание куск в пл ск стей, можно прибегнуть к следую-

ят

щему приему. Вначале следует выяснить, нет ли плоскостей,

которые целиком с с

из лишних кусков, и, если такие най-

и

. Затем сначала выбросить «лиш-

дутся, выброси ь э

ние» куски одной з ос авшихся плоскостей, потом другой и т.д.

Можно дока ать, что при этом поименованными окажутся все

частипространства.

п

зИсключение лишних плоскостей

е

Вернемсяок рис. 1.12. Легко видеть, что плоскости I, III и V

Р

могут быть исключены целиком. Они не содержат кусков,

IV

II

M

У

2

N

3

7

Т

10

6

Н

8

VI

1

9

VI I

4

5

Б

й

Рис. 1.14. Исключение лишних плоскостей

куски

Исключение лишн х кусков плоскостей

разделено

Проверяя поочередно все

плоскости II, затем все куски

плоскости IV и т. д. и выб асывая те куски, исключение

о

ечиям, придем к ситуации, при

которых не приводит к п

тив

т

на поименованные области

которой все пространство

(рис. 1.15).

и

з

B

о

A

2

п

10

е

1

8

Р

7

Процесс обучения закончен. Теперь, чтобы узнать оче-

редной объект, машине достаточно определить, в какой из

областей пространства лежит соответствующая ему точка.

Впрочем, машина может и ошибиться. Как видно из рис. 1.15,

разбиение получилось далеко не идеальным. Значительная

часть области В отнесена к образу С, а «кусочки» областей А

и С попали в образ В. Это произошло потому, что в ходе

обучения машины не встретились точки, расположенные в

этих частях пространства. По всей видимости, если процесс

обучения был бы более длительным, относительная площадьУ

неправильно поименованных кусков (а значит, и вероятность

в будущем ошибок при распознавании) была бы меньшеТ. Од-

нако увеличение длительности обучения приводит к расши-

рению требуемого

объема памяти машины. Есть

другие

Н

способы повышения надежности распознавания. О них будет

сказано далее.

Б

Описан е алгор тма

Машина, естественно, опе

й

ует в действительности не с

чертежами, а с числами. П

действия машины на том

же примере (см. рис. 1.1).

оследим

р

Проведение секущих плоскостей

о

Запомн в коорд на ы первых двух точек, машина выбирает

т

случайно п ч сел

λi (ii = 1, 2, 3,..., п, где п – размерность

рецепторов). Затем машина определяет значение

двухсумм:

и

з

пространства

σ(1) = Σλi

x ξi (1)

(1.1)

или

п

Случайный выбор коэффициентов означает, что каждый очередной ко-

эффициент может с равной вероятностью оказаться любым из некоторого

е

Р

конечного или бесконечного ряда чисел. Для осуществления такого выбо-

ра в машинах используют специальные датчики случайных чисел.

15

σ(2) = Σλi x ξi (2),

(1.2)

где xξi(1) – координаты первой, а ξi(2) – координаты второй точки.

После этого машина выбирает, также случайным образом, неко-

торое число λп+1, большее, чем меньшая из сумм σ(1) и σ(2), но

меньшее, чем большая из этих сумм. Если образовать две новые

суммы

Т

σ(1) = Σλi x ξi (1) – λn+1;

(1.3)

σ

(2)

= Σλi x ξi

(2)

–

λn+1,

У

(1.4)

то, учитывая способ, которым было выбрано число λn+1, легко

видеть, что одна из этих сумм обязательно будет отрицательной,

а другая – положительной. Геометрически же этоНозначает, что

этой

найденные машиной числа λ1, λ2 ,..., λn+1 есть коэффициенты

плоскости,

разделяющей две

точки.БДействительно, при

наши

плоскости

подстановкевлевуючастьуравнен я

р

Σλi x ξi –

λn+1

= 0

(1.5)

координатоднойизт чекп лучаетсяотрицательныйрезультат, а

т

положительный.

при подстановке к

рдинат другой точки –

Известно, что под бные результаты полу-чаются в том случае,

и

когдаточкилежатпооразныестороныотплоскости.

з

Условимся обознача ь положение данной точки относительно

плоскости

начком «1», если при подстановке координат этой

о

точки в левую часть уравнения плоскости получается положи-

тельн е число, и значком «0» в противном случае. Будем

п

г в рить, что точка имеет знак «1» или знак «0» относительно

е

Представим часть

памяти

машины после

данн й л скости.

Р

роведения первой разделяющей плоскости (см. рис. 1.2) в виде

Т а б л и ц а 1.1

Таблица знаков

Номер

Образ

Номер плоскости

точки

I

Знак точки

У

1

А

0

Т

2

В

1

Н

Б

При появлении следующей (третьей) точки (см. рис. 1.3)

машина определяет ее знак относительно первой плоскости и

заполняет третью строку таблицы знаков (табл. 1.2).

й

Т а б л и ц а 1.2

Табл ца знаков

р

Номер плоскости

Номер

и

I

точки

Об аз

т

Знак точки

1

и

оА

0

з

В

1

2

3

А

1

оочередно сравнивает последнюю строку таблицы

с каждой

Затем машина производит поиск оппонента, т. е.

е

Противоречием считается совпадение

Р

из редыдущих строк.

пстрок, относящихся к

разным

образам. В данном случае

Т а б л и ц а 1.3

Таблица знаков

Номер

Образ

Номер плоскости

У

I

II

точки

Н

Знак точки

Т

1

А

0

1

2

В

1

Б

0

3

А

1

1

Противоречие ликвидировано.

й

рис

Появляются точки 4, 5 и 6 (см.

. 1.5). После вычисления

их знаков приходим к табл. 1.4.

р

Т а б л и ц а 1.4

Таблица знаков

Номер

т

Номер плоскости

и

I

II

Образ

точки

о

Знак точки

з

А

0

1

1

о

В

1

0

2

3

А

1

1

п

С

0

0

4

5

С

0

0

Р

6

В

0

0

Поиск оппонентов, произведенный после появления точки 4, а

езатем после появления точки 5, дает отрицательный результат.

Т а б л и ц а 1.5

Таблица знаков

Т

У

Номер

Номер плоскости

Образ

I

II

Н

точки

Знак точки

1

А

0

1

Б

1

1

2

В

1

0

1

0

3

А

1

1

1

1

4

С

0

й

1

1

0

5

С

0

0

0

1

6

В

0

0

0

0

Противоречия вновь ликв д

ованы.

вид табл. 1.6.

точек

С появлением новых

машина

продолжает заполнять

таблицу знаков. С кажд й н в й точкой в таблице появляется

т

новая строка, с кажд й плрскостью – новый столбец. После

и

завершения первой час и алгоритма таблица знаков имеет

з

Т а б л и ц а 1.6

Таблица знаков

Н мер

Образ

Номер плоскости

I

II

III

IV

V

VI

VII

е

точкио

Знак точки

Р

п1

2

3

4

5

6

7

8

9

1

А

0

1

1

1

0

1

1

2

В

1

0

1

0

0

1

0

19

Окончание табл. 1.6

2

1

3

4

5

6

7

8

9

3

А

1

1

1

1

0

1

0

4

С

0

0

1

1

1

0

1

5

С

0

0

0

1

1

0

У

1

6

В

0

0

0

0

0

1

0

7

С

0

0

0

0

1

Т

0

1

8

В

0

0

1

1

0

1

1

9

С

0

0

1

1

0

0

1

10

А

0

0

1

1

0

1

0

По своему содержанию табл. 1.6 эквивалентна рис. 1.12. Каж-

дая строка таблицы соответствует одной из заштрихованныхН

на

й

рис. 1.12 частей пространства и представляет собой своеобраз-

ный код такой области – выпуклого n-мерногоБмногогранника,

и

образованного секущими плоскостями . Этот код указывает, по

р

какую сторону от каждой из секущ х плоскостей лежит много-

гранник, содержащийданнуюточку.

о

Исключение лишних плоскостей

стр ки со всемизаполненияостальными. «Выбрасывание» столбца означает,

После

аблицы знаков машина переходит

ко

второй части алгор

ма. В начале из таблицы знаков «выбра-

з

сывается» столбецт, соответствующий плоскости I. Затем произ-

водится по ск прот воречий, т.е. поочередное сравнение каждой

его

п

цифры при этом не учитываются. Если противоречий не

что

обнаруживается, т. е. не находится одинаковых строк, отно-

е

сящихся к разным образам, столбец исключается из памяти

Р

машины. В противном случае столбец «восстанавливается», т. е.

го цифры учитываются в последующих операциях. Машина