Различные подходы к построению систем ИИ

Имеется, по крайней мере, две точки зрения на то, что следовало бы считать искусственным интеллектом. Первую можно назвать нейробионической. Ее сторонники ставят перед собой цель воспроизвести искусственным образом те процессы, которые протекают в мозгу человека, — это путь изучения естественного мозга, выявление способов его работы, создания технических средств для повторения биологических структур и протекающих в них процессов.

Вторая точка зрения, доминирующая в проблеме искусственного интеллекта, может быть названа информационной. Сторонники информационного исхода считают, что основной целью работ в искусственном интеллекте является не построение технического аналога биологической системы, а создание средств для решения задач, традиционно считающихся интеллектуальными.

Информационная точка зрения в свою очередь неоднородна. В ней можно выделить три направления.

Часть специалистов считает, что можно найти свой способ ее решения на ЭВМ, который даст либо результат, подобный человеческому, либо даже лучший. Специалисты этого направления неоднократно демонстрировали свое искусство по созданию программ такого рода. Достаточно назвать, например, программы для игры в шахматы, которые играют в эту игру лучше подавляющего большинства людей, проводящих время за шахматной доской. Но делают это программы совсем не так, как люди. Другая часть специалистов считает, что искусственный интеллект должен имитировать не решение отдельных (пусть и весьма творческих) задач. Ибо естественный интеллект человека — это его способность при необходимости обучаться тому или иному виду творческой деятельности, значит, и программы, создаваемые в искусственном интеллекте, должны быть ориентированы не на решение конкретных задач, а на создание для автоматического построения необходимых программ решения конкретных задач, когда в этом возникает необходимость. Именно эта группа исследователей сейчас определяет лицо искусственного интеллекта, составляя основную массу специалистов этого профиля. Третья часть специалистов – это программисты, чьими руками делают программы для решения задач искусственного интеллекта.
Они склонны рассматривать область своей деятельности как новый виток развития программирования. Они считают, что средства, разрабатываемые для написания программ решения интеллектуальных задач, в конце концов, есть средства, позволяющие по описанию задачи на профессиональном естественном языке построить нужную программу на основании тех стандартных программных модулей, которые хранятся в памяти машины. Все метасредства, которые предлагают те, кто рассматривает искусственный интеллект как способ разобраться на информационном уровне, какие функции реализует естественный интеллект, когда он решает задачу, программисты видят сквозь призму своей цели — создания интеллектуального программного обеспечения (по существу, комплекса средств, автоматизирующих деятельность самого программиста). В те годы, когда возникали ЭВМ, мало кто предполагал, что они очень быстро вытеснят из вычислительной сферы все остальные вычислительные устройства. Дж. Фон-Нейман, с именем которого связана идея архитектуры классической ЭВМ, в те годы интересовался и другой организацией процесса вычислений, использующей аналоги нейроподобных структур; первые модели Формальных нейронов были предложены Мак-Калоком и Питсом.

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

Одним из наиболее известных нейробионических устройств был персептрон, предложенный Ф. Розенблатом. Он породил целое семейство конструкций, в основе которых лежала идея первоначального устройства Розенблата.

Метод, который лежал в основе функционирования персептрона, похож на те приемы, которые используются в распознавании образов.


Это научное направление весьма близко соприкасается с исследованиями по искусственному интеллекту. Строго говоря, нет никаких оснований не включать его в состав нового научного направления. Во всяком случае, нет особых возражений. Но, традиционно, возникшее гораздо ранее направление, связанное с распознаванием образов, существует отдельно. Хотя во многих пограничных вопросах эти две области научных исследований перекрываются (например, в методах формирования решающих правил при обучении на примерах и контрпримерах, как это происходит в персептронах, или в задачах анализа зрительных сцен).

Дальнейшие исследования в области нейробионических устройств шли по пути увеличения числа слоев из формальных нейронов, изменения и усложнения способа функционирования нейронов и построения решающего правила; параллельно развивалась теория персептронов. Но два обстоятельства затормозили эти работы. Очень быстро при решении практических задач распознавания стало понятно, что возможности устройств типа персептронов ограничены. Например, они не могли разложить изображение, являющееся комбинацией двух ранее персептрону известных, на составляющие. Это заставляло рассматривать подобную комбинацию как новое изображение. С другой стороны, Минский Н. и Пейперт С. доказали ряд теорем о персептронах, в которых обосновали их принципиальную ограниченность, а отсутствие новых идей нейробионических устройств в течение десятка лет не давало повода для развития этих исследований. Но успехи микроэлектроники последних лет, сделавшие возможным создание большого числа нейроп одобных элементов в малом объеме, вновь возродило надежды сторонников этого подхода. Появились нейрокомпьютеры, в которых процесс решения задачи развертывается на сети искусственных нейронов. Этот процесс может включать в себя множество параллельно и асинхронно протекающих подпроцессов, что сулит высокую эффективность решения задач на нейрокомпьютерах. Беда состоит только в том, что пока неизвестны регулярные приемы программирования решения задач для ЭВМ такой архитектуры.



Программы для решения интеллектуальных задач могут быть разделены на несколько групп, которые определяются типом задач, решаемых этими программами. Первую группу составляют игровые программы, они, в свою очередь, делятся на две подгруппы: человеческие игры и компьютерные игры. Особенностью всех программ для имитации человеческих игр является большая роль поисковых процедур — поиск лучшего или локально лучшего хода требует в сложных играх типа шахмат просмотра большого числа вариантов. Недаром шахматные программы являются специальным тестом для проверки эффективности поисковых процедур.

Программы решения интеллектуальных задач представлены на рис. 2.1.


Рис. 2.1.  Программы решения интеллектуальных задач

Интересно отметить, что именно поисковые процедуры казались на первом этапе развития работ по интеллектуальным программам той метапроцедурой, с помощью которой можно будет решать все интеллектуальные задачи. Первая программа, которая обобщила эту идею, называлась "Общий решатель задач". В этой программе, созданной А. Ньюэллом, Дж. Шоу и Г. Саймоном, поиск с локальными критериями успеха был основной процедурой. Решение всех задач, по мысли авторов, могло быть сведено к поиску пути в лабиринте альтернативных возможностей.

И хотя эти надежды не оправдались, цикл подобных исследований оказался весьма полезным. Были созданы достаточно эффективные процедуры поиска, используемые специалистами по искусственными интеллекту не только при решении игровых задач, но и во многих других областях (например, при планировании целесообразной деятельности в интеллектуальных системах).

Переборные игры составляют, по-видимому, большинство во множестве распространенных среди людей игр. Существенно меньшую часть составляют топологические игры, в которых необходимо учитывать не только дерево игры, задаваемое возможными последовательностями ходов противников, но и структурой самой позиции как целого. Примером такой игры может служить го. В этой игре оценка позиции не может быть сведена, как, например, в шахматах, к описанию множества фигур и их расположения на игровом поле.


Для го важно не конкретное расположение камней по тем или иным полям, а те конфигурации, которые они образуют на плоскости игрового поля. Программирование таких игр требует создания в памяти ЭВМ эталонных образов тех или иных областей, занятых камнями противников. А это куда более сложная и до конца пока не решенная задача, нежели организация поиска по дереву альтернативных возможностей. Стохастические игры появляются тогда, когда в процессе игры возникают вероятностные шаги или очередная си туация формируется при участии некоторого вероятностного механизма. С программированием таких игр (например, карточной игры в очко) связано развитие методов правдоподобного оценивания вариантов, получившего в искусственном интеллекте заметное использование. Во всех таких ситуациях важно уметь пересчитать оценку правдоподобия результирующей ситуации после выбора определенного хода с учетом оценок правдоподобия текущей ситуации и выбора противника.

К стохастическим играм примыкают и игры с неполной информацией, когда при принятии решения необходимо как-то оценивать недостающую информацию. Эти приемы постоянно используются при обращении к содержимому памяти в интеллектуальных системах, когда в ней отсутствует нужная информация, что является почти стандартной ситуацией при функционировании таких систем в сложных предметных областях.

Компьютерные игры, получившие в последнее время столь широкое распространение, вообще говоря, не относятся традиционно к работам по искусственному интеллекту. Хотя эта ситуация столь же случайна, как и ситуация с распознаванием образов. Конечно, игры с жесткой схемой, в которых "интеллекта" практически нет, не представляют для работ по искусственному интеллекту интереса, но сценарные игры уж точно относятся к рассматриваемой области науки. В них используются сценарии развития игры, движение по которым определяется обоими партнерами. Эти же принципы применяются и в таких типичных для искусственного интеллекта задачах, как организация диалога интеллектуальной системы с пользователем на ограниченном естественном языке, интересны сценарии и для планирования целесообразной деятельности в интеллектуальных работах и других системах искусственного интеллекта.



С самого начала появления ЭВМ стали создаваться программы для машинного перевода и автоматического реферирования текстов. Создание этих программ оказало значительное влияние на развитие искусственного интеллекта, заложило основы тех работ, которые были непосредственно связаны с естественно-языковым общением пользователей с интеллектуальными системами.

В системах машинного перевода были разработаны модели и методы, позволяющие автоматически проводить морфологический, синтаксический и во многом семантический анализ фраз естественного языка, нащупаны приемы анализа связного текста. Все эти результаты активно используются при обработке естественно-языковых текстов в интеллектуальных системах.

В работах по автоматическому реферированию были заложены основы понимания общей структуры текста как целого, от идеи "что говорится" был сделан переход к идее "о чем говорится". Это позволило на более высоком уровне создавать программы генерации текстов. Если первые программы такого вида основывались на жестких моделях порождения или вероятностных механизмах, то более поздние программы генерации текстов стали опираться на идеи сценариев, а также на приемы, наработанные в программах по автоматическому реферированию. Сейчас качество прозаических текстов, создаваемых с помощью ЭВМ, достаточно высоко, если тексты имеют жесткую внутреннюю структуру, определяемую их назначением. Таковы, например, волшебные сказки, в основе которых лежит жесткий сценарий поведения действующих лиц, таковы хроникальные заметки или документы, но созданы и достаточно любопытные программы, порождающие поэтические тексты, в которых наблюдается иная крайность — почти пол ное отсутствие смысловой структуры при достаточно жесткой структуре формы.

Музыкальные программы, пожалуй, наиболее известны широкой публике, так как первые опыты по созданию таких программ сразу дали весьма обнадеживающие результаты. Этот успех связан опять-таки с наличием, с одной стороны, жестких правил при построении мелодии, а с другой стороны, во многом вероятностными моделями, порождающими остальные элементы музыкального произведения.


Менее известны широкой публике программы, ориентированные на музыковедов, в которых имитируются стили исполнения или исследуется "анатомия" музыкальных произведений и процесса их сочинения. Однако весь комплекс музыкальных программ, хотя и не оказал прямого влияния на работы по искусственному интеллекту, стал полезным для формирования общего взгляда на природу творческих процессов и их моделирования.

Узнающие программы зародились в недрах исследований по распознаванию образов. Но, как уже говорилось, многие из них оказали значительное влияние на идеи, характерные для работ по созданию интеллектуальных систем, особенно при создании обучающих систем. При их разработке были найдены методы оценивания похожести одних объектов на другие, заложены основы рассуждений по аналогии и ассоциации, использования обучающих последовательностей примеров и контрпримеров; все это вошло в фонд методов, которыми пользуется специалист по искусственному интеллекту.

Несколько особняком стоят программы, с помощью которых создаются машинные произведения в области графики и живописи. Эти исследования связаны, в основном, с появлением специальных программных и в меньшей мере аппаратных средств для устройств графического вывода. Но косвенно эти программы оказывают влияние на те разделы искусственного интеллекта, которые связаны с использованием зрительных образов при решении задач.

Третье основное направление в создании искусственного интеллекта образует его фундамент. Именно здесь создается теория данного научного направления, решаются основные проблемы, связанные с центральным объектом изучения искусственного интеллекта — знаниями.

Существуют различные подходы к построению систем ИИ. Это разделение не является историческим, когда одно мнение постепенно сменяет другое, и различные подходы существуют и сейчас. Кроме того, поскольку по-настоящему полных систем ИИ в настоящее время нет, то нельзя сказать, что какой-то подход является правильным, а какой-то — ошибочным.

Кратко рассмотрим логический подход.


Почему он возник? Ведь человек занимается отнюдь не только логическими измышлениями. Это высказывание, конечно, верно, но именно способность к логическому мышлению очень сильно отличает человека от животных.

Основой для данного логического подхода служит Булева алгебра. Каждый программист знаком с нею и с логическими операторами с тех пор, когда он осваивал оператор IF. Свое дальнейшее развитие Булева алгебра получила в виде исчисления предикатов — в котором она расширена за счет введения предметных символов, отношений между ними, кванторов существования и всеобщности. Практически каждая система ИИ, построенная на логическом принципе, представляет собой машину доказательства теорем. При этом исходные данные хранятся в базе данных в виде аксиом, правила логического вывода существуют как отношения между ними. Кроме того, каждая такая машина имеет блок генерации цели, и система вывода пытается доказать данную цель как теорему. Если цель доказана, то трассировка примененных правил позвол яет получить цепочку действий, необходимых для реализации поставленной цели. Мощность такой системы определяется возможностями генератора целей и машиной доказательства теорем.

Конечно, можно сказать, что выразительности алгебры высказываний не хватит для полноценной реализации ИИ, но стоит вспомнить, что основой всех существующих ЭВМ является бит — ячейка памяти, которая может принимать значения только 0 и 1. Таким образом, было бы логично предположить, что все, что возможно реализовать на ЭВМ, можно было бы реализовать и в виде логики предикатов. Хотя здесь ничего не говорится о том, за какое время.

Добиться большей выразительности логическому подходу позволяет такое сравнительно новое направление, как нечеткая логика. Основным ее отличием является то, что правдивость высказывания может принимать в ней, кроме "да/нет" (1/0), еще и промежуточные значения — "не знаю" (0.5), "пациент скорее жив, чем мертв" (0.75), "пациент скорее мертв, чем жив" (0.25).




Данный подход больше похож на мышление человека, поскольку мы на вопросы редко отвечаем только "да" или "нет". Хотя, правда, на экзамене будут приниматься только ответы из разряда классической булевой алгебры.

Для большинства логических методов характерна большая трудоемкость, поскольку во время поиска доказательства возможен полный перебор вариантов. Поэтому данный подход требует эффективной реализации вычислительного процесса, и хорошая работа обычно гарантируется при сравнительно небольшом размере базы данных.

Под структурным подходом мы подразумеваем здесь попытки построения ИИ путем моделирования структуры человеческого мозга. Одной из первых таких попыток был персептрон Френка Розенблатта. Основной моделируемой структурной единицей в персептронах (как и в большинстве других вариантов моделирования мозга) является нейрон.

Позднее возникли и другие модели, которые в просторечии обычно известны под термином "нейронные сети" (НС). Эти модели различаются по строению отдельных нейронов, по топологии связей между ними и по алгоритмам обучения. Среди наиболее известных сейчас вариантов НС можно назвать НС с обратным распространением ошибки, сети Хопфилда, стохастические нейронные сети.

НС наиболее успешно применяются в задачах распознавания образов, в том числе сильно зашумленных, однако имеются и примеры успешного использования их для построения собственно систем ИИ — это уже ранее упоминавшийся ТАИР.

Для моделей, построенных "по мотивам" человеческого мозга, характерна не слишком большая выразительность, легкое распараллеливание алгоритмов и связанная с этим высокая производительность параллельно реализованных НС. Также для таких сетей характерно одно свойство, которое очень сближает их с человеческим мозгом, — нейронные сети работают даже при условии неполной информации об окружающей среде, то есть, как и человек, они на вопросы могут отвечать не только "да" и "нет", но и "не знаю точно, но скорее да".



С ЧЯ связана одна очень интересная идея. Кто бы хотел жить вечно? Я думаю, что почти все ответят на этот вопрос "я".

Представим себе, что за нами наблюдает какое-то устройство, которое следит за тем, что в каких ситуациях мы делаем, говорим. Наблюдение идет за величинами, которые поступают к нам на вход (зрение, слух, вкус, тактильные, вестибулярные и т. д.), и за величинами, которые выходят от нас (речь, движение и др.). Таким образом человек выступает здесь как типичный ЧЯ.

Далее это устройство пытается отстроить какую-то модель таким образом, чтобы при определенных сигналах на входе она выдавала на выходе те же данные, что и человек. Если данная затея будет когда-нибудь реализована, то для всех посторонних наблюдателей такая модель будет той же личностью, что и реальный человек. А после его смерти она будет высказывать те мысли, которые предположительно высказывал бы и смоделированный человек.

Мы можем пойти дальше и скопировать эту модель и получить брата близнеца с точно такими же "мыслями".

Можно сказать, что "это, конечно, все интересно, но при чем тут я? Ведь эта модель только для других будет являться мной, но внутри ее будет пустота. Копируются только внешние атрибуты, но я после смерти уже не буду думать, мое сознание погаснет (для верующих людей слово "погаснет" необходимо заменить на "покинет этот мир") ". Что ж, это так. Но попробуем пойти дальше.

Согласно философским представлениям автора данного курса, сознание представляет собой сравнительно небольшую надстройку над нашим подсознанием, которая следит за активностью некоторых центров головного мозга, таких, как центр речи или конечной обработки зрительных образов, после чего "возвращает" эти образы на начальные ступени обработки данной информации. Происходит повторная обработка этих образов, мы как бы видим и слышим, что думает наш мозг. Следовательно, появляется возможность мысленного моделирования окружающей действительности при нашем "активном" участии в данном процессе.


И именно наш процесс наблюдения за деятельностью этих немногих центров является тем, что мы называем сознанием. Если мы "видим" и "слышим" наши мысли, мы в сознании, если нет, то мы находимся в бессознательном состоянии.

Если бы мы смогли смоделировать работу именно этих немногих "сознательных" нервных центров (работа которых, правда, основана на деятельности всего остального мозга) в качестве одного ЧЯ и работу "супервизора" в качестве другого ЧЯ, то можно было бы с уверенностью говорить, что "да, данная модель думает, причем так же, как и я". Здесь я ничего не хочу говорить о том, как получить данные о работе этих нервных центров, поскольку, на мой взгляд, сегодня нет ничего такого, что позволило бы следить за мозгом человека годами и при этом не мешало бы его работе и жизни.

И заканчивая беглое ознакомление с различными методами и подходами к построению систем ИИ, хотелось бы отметить, что на практике очень четкой границы между ними нет. Очень часто встречаются смешанные системы, где часть работы выполняется по одному типу, а часть — по другому.

Вспомогательные системы нижнего

Для того, чтобы человек сознательно воспринял информацию (для примера возьмем чертеж), она должна пройти довольно длительный цикл предварительной обработки. Вначале свет попадает в глаз. Пройдя через всю оптическую систему, фотоны в конце концов попадают на сетчатку — слой светочувствительных клеток — палочек и колбочек.

Рис. 2.2. 

Уже здесь — еще очень далеко от головного мозга — происходит первый этап обработки информации, поскольку, например, у млекопитающих сразу за светочувствительными клетками находится обычно два слоя нервных клеток, которые выполняют сравнительно несложную обработку.

Теперь информация поступает по зрительному нерву в головной мозг человека, в так называемые "зрительные бугры". То, что именно сюда приходит видеоинформация для дальнейшей обработки, показывают многочисленные опыты над людьми во время различных операций, в ходе которых производилась трепанация черепа. При этом пациентам раздражали область зрительных бугров слабым электрическим полем, что вызывало у них различные световые галлюцинации. Что интересно, при изменении места раздражения, пропорционально смещению смещались и места галлюцинаций, т. е. на зрительные бугры как бы проецируется то, что мы видим.

Некоторые исследователи пошли дальше и вживляли слепым людям целую матрицу электродов, напряжения на которых соответствовали освещенности соответствующих участков видеокамеры, размещенной на голове пациента. После операции слепые начинали различать крупные фигуры (квадрат, треугольник, круг) и даже читать текст (при вживлении матрицы 10*10). Широкому распространению данного метода лечения слепоты препятствуют как недостаточно высокий наш технический уровень, так и чрезвычайно высокая опасность операций на открытом мозге. Такого рода опыты проводятся только попутно с операцией, вызванной другими причинами.

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

Смысл всего сказанного заключается в том, чтобы показать, что в системах ИИ имеются подсистемы, которые мы уже сейчас можем реализовать, даже не зная о том, как они реализованы у человека. Причем можем это сделать не хуже, чем у прототипа, а зачастую и лучше. Например, искусственный глаз (а равно и блок первичной обработки видеоинформации, основанные на простейших фильтрах или других сравнительно несложных устройствах) не устает, может видеть в любом диапазоне волн, легко заменяется на новый, видит при свете звезд.

Устройства обработки звука позволяют улавливать девиацию голоса человека в 1-2 Герца. Данное изменение частоты происходит при повышенном возбуждении вегетативной нервной системы, которое, в свою очередь, часто обусловлено волнением человека. На этом принципе основаны современные детекторы лжи, которые позволяют обнаружить с высокой вероятностью даже записанные на пленку много лет назад ложные высказывания.

Современные системы управления электродвигателем позволяют с высокой точностью держать заданные координаты даже при ударном изменении нагрузки. А ведь это примерно то же, что держать на длинной палке баскетбольный мяч, по которому то слева, то справа кидают теннисные мячи.

За одно и то же время компьютер произведет гораздо больше арифметических операций и с большей точностью, чем человек.

Антиблокировочная система на автомобилях позволяет держать тормоза на грани блокирования колеса, что дает наибольшее сцепление с дорогой, а это без АБС по силам только очень опытным водителям.

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

Данный принцип разбиения задачи на подзадачи уже давно используется природой. К примеру, мы далеко не полностью используем все возможности наших мышц в области разнообразия движений. Мы не можем заставить наши глаза смотреть в разные стороны, не говоря уже о том, чтобы делать это на разном уровне (левый глаз — влево-вверх, правый — вправо-вниз). При ходьбе мы часто используем далеко не оптимальный набор движений, и далеко не все сочетания вариантов напряжения мышц мы опробуем. Попробуйте, скажем, сделать волну животом. В принципе, здесь нет ничего сложного, поскольку каждый пучок мышц пресса иннервируется отдельно, но если Вы этого не делали ранее, то получить необходимый результат будет не просто — в повседневной жизни это действие не нужно, а значит, его нет и в "словаре движений", а на обучение необходимо определенное время. А по поводу оптимальности походки существуют расчеты, что если бы человек всегда рассчитывал оптимально траекторию движения, в которой существует более 200 степеней свобод, то он бы не ходил, а в основном бы только думал о том, как надо ходить.

На самом деле наша система управления построена по иерархическому принципу, когда задача распределяется между несколькими уровнями. Высший уровень нервной системы (связанный с большими полушариями мозга) ставит лишь общую задачу — скажем, переложить книгу на стол. Этот уровень вообще не контролирует действие отдельных двигательных единиц, направленных на решение поставленной задачи. Здесь уместна аналогия: командующий армией, ставя перед своими войсками некую общую задачу, отнюдь не предписывает каждому солдату и офицеру, что именно он должен делать в каждый момент операции.

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

В общем ситуация схожа с той, когда программист использует библиотеку подпрограмм. При этом ему не важно, какой алгоритм в них применен, если программа работает нормально. А на написание своей библиотеки тратится драгоценное время. Кроме того, еще не известно, будет ли она работать так же хорошо.

Общий вывод данной лекции состоит в том, что в настоящее время существуют методы, алгоритмы и устройства, которые позволяют нам довольно неплохо смоделировать нижние уровни человеческого интеллекта, причем совсем не обязательно на таком же физическом принципе.

Геометрический и структурный подходы.

Каждый раз, когда сталкиваешься с незнакомыми задачами, появляется естественное желание представить их в виде некоторой легко понимаемой модели — она позволила бы осмыслить задачу в таких терминах, которые легко воспроизводятся нашим воображением. А так как мы существуем в пространстве и во времени, наиболее понятной для нас является пространственно-временная интерпретация задач.

Любое изображение, которое возникает в результате наблюдения какого-либо объекта в процессе обучения или экзамена, можно представить в виде вектора, а значит, и в виде точки некоторого пространства признаков. Если утверждается, что при показе изображений возможно однозначно отнести их к одному из двух (или нескольких) образов, то тем самым утверждается, что в некотором пространстве существует две (или несколько) области, не имеющие общих точек, и что изображения — точки из этих областей. Каждой такой области можно приписать наименование, т. е. дать название, соответствующее образу.

Проинтерпретируем теперь в терминах геометрической картины процесс обучения распознаванию образов, ограничившись пока случаем распознавания только двух образов. Заранее считается известным лишь то, что требуется разделить две области в некотором пространстве и что показываются точки только из этих областей. Сами эти области заранее не определены, т. е. нет каких-либо сведений о расположении их границ или правил определения принадлежности точки к той или иной области.

В ходе обучения предъявляются точки, случайно выбранные из этих областей, и сообщается информация о том, к какой области принадлежат предъявляемые точки. Никакой дополнительной информации об этих областях, т. е. о расположении их границ, в ходе обучения не сообщается. Цель обучения состоит либо в построении поверхности, которая разделяла бы не только показанные в процессе обучения точки, но и все остальные точки, принадлежащие этим областям, либо в построении поверхностей, ограничивающих эти области так, чтобы в каждой из них находились только точки одного образа.
Иначе говоря, цель обучения состоит в построении таких функций от векторов-изображений, которые были бы, например, положительны на всех точках одного и отрицательны на всех точках другого образа. В связи с тем, что области не имеют общих точек, всегда существует целое множество таких разделяющих функций, а в результате обучения должна быть построена одна из них.

Если предъявляемые изображения принадлежат не двум, а большему числу образов, то задача состоит в построении по показанным в ходе обучения точкам поверхности, разделяющей друг от друга все области, которые соответствуют этим образам. Задача эта может быть решена, например, путем построения функции, принимающей над точками каждой из областей одинаковое значение, а над точками из разных областей значение этой функции должно быть различно.

Рис. 3.2. 

На первый взгляд кажется, что знание всего лишь некоторого количества точек из области недостаточно, чтобы отделить всю область. Действительно, можно указать бесчисленное количество различных областей, которые содержат эти точки, и как бы ни была построена по ним поверхность, выделяющая область, всегда можно указать другую область, которая пересекает поверхность и вместе с тем содержит показанные точки. Однако известно, что задача о приближении функции по информации о ней в ограниченном множестве точек, существенно более узкой, чем все множество, на котором функция задана, является обычной математической задачей об аппроксимации функций. Разумеется, решение таких задач требует введения определенных ограничений на классе рассматриваемых функций, а выбор этих ограничений зависит от характера информации, которую может добавить учитель в процессе обучения. Одной из таких подсказок является гипотеза о компактности образов. Интуитивно ясно, что аппроксимация разделяющей функции будет задачей тем более легкой, чем более компактны и чем более разнесены в пространстве области, подлежащие разделению. Так, например, в случае, показанном на 3.2a, разделение заведомо более просто, чем в случае, показанном на 3.2б.


Действительно, в случае, изображенном на 3.2а, области могут быть разделены плоскостью, и даже при больших погрешностях в определении разделяющей функции она все же будет продолжать разделять области. В случае же на 3.2б, разделение осуществляется замысловатой поверхностью, и даже незначительные отклонения в ее форме приводят к ошибкам разделения. Именно это интуитивное представление о сравнительно легко разделимых областях привело к гипотезе компактности.

Наряду с геометрической интерпретацией проблемы обучения распознаванию образов существует и иной подход, который назван структурным, или лингвистическим. Поясним его на примере распознавания зрительных изображений. Сначала выделяется набор исходных понятий — типичных фрагментов, встречающихся на изображениях, и характеристик взаимного расположения фрагментов — "слева", "снизу", "внутри" и т. д. Эти исходные понятия образуют словарь, который позволяет строить различные логические высказывания, иногда называемые предположениями. Задача состоит в том, чтобы из большого количества высказываний, которые могли бы быть построены с использованием этих понятий, отобрать наиболее существенные для данного конкретного случая.

Далее, просматривая конечное и по возможности небольшое число объектов из каждого образа, нужно построить описание этих образов. Построенные описания должны быть столь полными, чтобы решить вопрос о том, к какому образу принадлежит данный объект. При реализации лингвистического подхода возникают две задачи: задача построения исходного словаря, т. е. набор типичных фрагментов, и задача построения правил описания из элементов заданного словаря.

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

Гипотеза компактности

Если предположить, что в процессе обучения пространство признаков формируется исходя из задуманной классификации, то тогда можно надеяться, что задание пространство признаков само по себе задает свойство, под действием которого образы в этом пространстве легко разделяются. Именно эти надежды по мере развития работ в области распознавания образов стимулировали появление гипотезы компактности , которая гласит: образам соответствуют компактные множества в пространстве признаков. Под компактным множеством пока будем понимать некие "сгустки" точек в пространстве изображений, предполагая, что между этими сгустками существуют разделяющие их разряжения.

Однако эту гипотезу не всегда удавалось подтвердить экспериментально, но, что самое главное, те задачи, в рамках которых гипотеза компактности хорошо выполнялась (рис. 3.2а), все без исключения находили простое решение. И наоборот, те задачи, для которых гипотеза не подтверждалась (рис. 3.2б), либо совсем не решались, либо решались с большим трудом с привлечением дополнительных ухищрений. Этот факт заставил усомниться в справедливости гипотезы компактности, так как для опровержения любой гипотезы достаточно одного отрицающего ее примера. Вместе с этим, выполнение гипотезы всюду там, где удавалось хорошо решить задачу обучения распознаванию образов, сохраняло к ней интерес. Сама гипотеза компактности превратилась в признак возможности удовлетворительного решения задач распознавания.

Формулировка гипотезы компактности подводит вплотную к понятию абстрактного образа. Если координаты пространства выбирать случайно, то и изображения в нем будут распределены случайно. Они будут в некоторых частях пространства располагаться более плотно, чем в других. Назовем некоторое случайно выбранное пространство абстрактным изображением. В этом абстрактном пространстве почти наверняка будут существовать компактные множества точек. Поэтому в соответствии с гипотезой компактности множества объекты, которым в абстрактном пространстве соответствуют компактные множества точек, разумно назвать абстрактными образами данного пространства.

Обучение и самообучение

Если бы удалось подметить некое всеобщее свойство, не зависящее ни от природы образов, ни от их изображений, а определяющее лишь их способность к разделимости, то наряду с обычной задачей обучения распознаванию, с использованием информации о принадлежности каждого объекта из обучающей последовательности тому или иному образу, можно было бы поставить иную классификационную задачу — так называемую задачу обучения без учителя. Задачу такого рода на описательном уровне можно сформулировать так: системе одновременно или последовательно предъявляются объекты без каких-либо указаний об их принадлежности к образам. Входное устройство системы отображает множество объектов на множество изображений и, используя некоторое заложенное в нее заранее свойство разделимости образов, производит самостоятельную классификацию этих объектов. После такого процесса самообучения система должна приобрести способность к распознаванию не только уже знакомых объектов (объектов из обучающей посл едовательности), но и тех, которые ранее не предъявлялись. Процессом самообучения некоторой системы называется такой процесс, в результате которого эта система без подсказки учителя приобретает способность к выработке одинаковых реакций на изображения объектов одного и того же образа и различных реакций на изображения различных образов. Роль учителя при этом состоит лишь в подсказке системе некоторого объективного свойства, одинакового для всех образов и определяющего способность к разделению множества объектов на образы.

Оказывается, таким объективным свойством является свойство компактности образов. Взаимное расположение точек в выбранном пространстве уже содержит информацию о том, как следует разделить множество точек. Эта информация и определяет то свойство разделимости образов, которое оказывается достаточным для самообучения системы распознаванию образов.

Большинство известных алгоритмов самообучения способны выделять только абстрактные образы, т. е. компактные множества в заданных пространствах. Различие между ними состоит, по-видимому, в формализации понятия компактности. Однако это не снижает, а иногда и повышает ценность алгоритмов самообучения, так как часто сами образы заранее никем не определены, а задача состоит в том, чтобы определить, какие подмножества изображений в заданном пространстве представляют собой образы. Хорошим примером такой постановки задачи являются социологические исследования, когда по набору вопросов выделяются группы людей. В таком понимании задачи алгоритмы самообучения генерируют заранее не известную информацию о существовании в заданном пространстве образов, о которых ранее никто не имел никакого представления.

Кроме того, результат самообучения характеризует пригодность выбранного пространства для конкретной задачи обучения распознаванию. Если абстрактные образы, выделяемые в процессе самообучения, совпадают с реальными, то пространство выбрано удачно. Чем сильнее абстрактные образы отличаются от реальных, тем "неудобнее" выбранное пространство для конкретной задачи.

Обучением обычно называют процесс выработки в некоторой системе той или иной реакции на группы внешних идентичных сигналов путем многократного воздействия на систему внешней корректировки. Такую внешнюю корректировку в обучении принято называть "поощрениями" и "наказаниями". Механизм генерации этой корректировки практически полностью определяет алгоритм обучения. Самообучение отличается от обучения тем, что здесь дополнительная информация о верности реакции системе не сообщается.

Понятие образа

Образ, класс — классификационная группировка в системе классификации, объединяющая (выделяющая) определенную группу объектов по некоторому признаку.

Образное восприятие мира — одно из загадочных свойств живого мозга, позволяющее разобраться в бесконечном потоке воспринимаемой информации и сохранять ориентацию в океане разрозненных данных о внешнем мире. Воспринимая внешний мир, мы всегда производим классификацию воспринимаемых ощущений, т. е. разбиваем их на группы похожих, но не тождественных явлений. Например, несмотря на существенное различие, к одной группе относятся все буквы А, написанные различными почерками, или все звуки, которые соответствуют одной и той же ноте, взятой в любой октаве и на любом инструменте, а оператор, управляющий техническим объектом, на целое множество состояний объекта реагирует одной и той же реакцией. Характерно, что для составления понятия о группе восприятий определенного класса достаточно ознакомиться с незначительным количеством ее представителей. Ребенку можно показать всего один раз какую-либо букву, чтобы он смог найти эту букву в тексте, написанном различными шрифтами, или узнать ее, даже если она написана в у мышленно искаженном виде. Это свойство мозга позволяет сформулировать такое понятие, как образ.

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

Способность восприятия внешнего мира в форме образов позволяет с определенной достоверностью узнавать бесконечное число объектов на основании ознакомления с конечным их числом, а объективный характер основного свойства образов позволяет моделировать процесс их распознавания. Будучи отражением объективной реальности, понятие образа столь же объективно, как и сама реальность, а поэтому может быть само по себе объектом специального исследования.

В литературе, посвященной проблеме обучения распознавания образов (ОРО), часто вместо понятия образа вводится понятие класса.

Проблема обучения распознаванию образов (ОРО)

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

Рассмотрим пример задач из области ОРО.

Рис. 3.1.  Пример задач из области ОРО

Здесь представлены 12 изображений, и следует отобрать признаки, при помощи которых можно отличить левую триаду картинок от правой. Решение данных задач требует моделирования логического мышления в полном объеме.

В целом проблема распознавания образов состоит из двух частей: обучения и распознавания. Обучение осуществляется путем показа отдельных объектов с указанием их принадлежности тому или другому образу. В результате обучения распознающая система должна приобрести способность реагировать одинаковыми реакциями на все объекты одного образа и различными — на все объекты различных образов. Очень важно, что процесс обучения должен завершиться только путем показов конечного числа объектов без каких-либо других подсказок. В качестве объектов обучения могут быть либо картинки, либо другие визуальные изображения (буквы), либо различные явления внешнего мира, например, звуки, состояния организма при медицинском диагнозе, состояние технического объекта в системах управления и др. Важно, что в процессе обучения указываются только сами объекты и их принадлежность образу. За обучением следует процесс распознавания новых объектов, который характеризует действия уже обученной системы. Автоматизация этих процедур и составляет проблему обучения распознаванию образов. В том случае, когда человек сам разгадывает или придумывает, а затем навязывает машине правило классификации, проблема распознавания решается частично, так как основную и главную часть проблемы (обучение) человек берет на себя.

Проблема обучения распознаванию образов интересна как с прикладной, так и с принципиальной точки зрения. С прикладной точки зрения решение этой проблемы важно прежде всего потому, что оно открывает возможность автоматизировать многие процессы, которые до сих пор связывали лишь с деятельностью живого мозга. Принципиальное значение проблемы тесно связано с вопросом, который все чаще возникает в связи с развитием идей кибернетики: что может и что принципиально не может делать машина? В какой мере возможности машины могут быть приближены к возможностям живого мозга? В частности, может ли машина развить в себе способность перенять у человека умение производить определенные действия в зависимости от ситуаций, возникающих в окружающей среде? Пока стало ясно только то, что если человек может сначала сам осознать свое умение, а потом его описать, т. е. указать, почему он производит действия в ответ на каждое состояние внешней среды или как (по какому правилу) он объединяет отдельные объекты в образы, то такое умени е без принципиальных трудностей может быть передано машине. Если же человек обладает умением, но не может объяснить его, то остается только один путь передачи умения машине — обучение примерами.

Круг задач, которые могут решаться с помощью распознающих систем, чрезвычайно широк. Сюда относятся не только задачи распознавания зрительных и слуховых образов, но и задачи распознавания сложных процессов и явлений, возникающих, например, при выборе целесообразных действий руководителем предприятия или выборе оптимального управления технологическими, экономическими, транспортными или военными операциями. В каждой из таких задач анализируются некоторые явления, процессы, состояния внешнего мира, всюду далее называемые объектами наблюдения. Прежде чем начать анализ какого-либо объекта, нужно получить о нем определенную, каким-либо способом упорядоченную информацию. Такая информация представляет собой характеристику объектов, их отображение на множестве воспринимающих органов распознающей системы.



Но каждый объект наблюдения может воздействовать на нас по-разному, в зависимости от условий восприятия. Например, какая-либо буква, даже одинаково написанная, может в принципе как угодно смещаться относительно воспринимающих органов. Кроме того, объекты одного и того же образа могут достаточно сильно отличаться друг от друга и, естественно, по-разному воздействовать на воспринимающие органы.

Каждое отображение какого-либо объекта на воспринимающие органы распознающей системы, независимо от его положения относительно этих органов, принято называть изображением объекта, а множества таких изображений, объединенные какими-либо общими свойствами, представляют собой образы.

При решении задач управления методами распознавания образов вместо термина "изображение" применяют термин "состояние". Состояние — это определенной формы отображение измеряемых текущих (или мгновенных) характеристик наблюдаемого объекта. Совокупность состояний определяет ситуацию. Понятие "ситуация" является аналогом понятия "образ". Но эта аналогия не полная, так как не всякий образ можно назвать ситуацией, хотя всякую ситуацию можно назвать образом.

Ситуацией принято называть некоторую совокупность состояний сложного объекта, каждая из которых характеризуется одними и теми же или схожими характеристиками объекта. Например, если в качестве объекта наблюдения рассматривается некоторый объект управления, то ситуация объединяет такие состояния этого объекта, в которых следует применять одни и те же управляющие воздействия. Если объектом наблюдения является военная игра, то ситуация объединяет все состояния игры, которые требуют, например, мощного танкового удара при поддержке авиации.

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

Адаптация и обучение

Адаптация — это процесс изменения параметров и структуры системы, а возможно, и управляющих воздействий, на основе текущей информации с целью достижения определенного состояния системы при начальной неопределенности и изменяющихся условиях работы.

Обучение — это процесс, в результате которого система постепенно приобретает способность отвечать нужными реакциями на определенные совокупности внешних воздействий, а адаптация — это подстройка параметров и структуры системы с целью достижения требуемого качества управления в условиях непрерывных изменений внешних условий.

Алгоритм с ковариациями и с квадратичными описаниями

Рис. 4.8.  МГУА как эквивалент массовой селекции

В этом алгоритме [5, 6] используются частные описания, представленные в следующих формулах: yi=a0+a1xi+a2xj+a3xixj;

.

Сложность модели увеличивается от ряда к ряду селекции как по числу учитываемых аргументов, так и по степени. Степень полного описания быстро растет. На первом ряду — квадратичные описания, на втором — четвертой степени, на третьем — восьмой и т. д. В связи с этим минимум критерия селекции находится быстро, но не совсем точно. Кроме того, имеется опасность потери существенного аргумента, особенно на первых рядах селекции (в случае отсутствия протекции). Специальные теоремы теории МГУА определяют условия, при которых результат селекции не отличается от результата полного перебора моделей.

Чтобы степень полного уравнения повышалась с каждым рядом селекции на единицу, достаточно рассматривать все аргументы и их ковариации как обобщенные аргументы и пользоваться составленными для них линейными описаниями.

История исследований в области нейронных сетей

Возвратимся немного назад и рассмотрим историю исследований нейронных сетей.

Как и в истории любой другой науки, здесь были свои успехи и неудачи. Кроме того, здесь постоянно сказывается психологический фактор, проявляющийся в неспособности человека описать словами то, как он думает.

Способность нейронной сети к обучению впервые исследована Дж. Маккалоком и У. Питтом. В 1943 году вышла их работа "Логическое исчисление идей, относящихся к нервной деятельности", в которой была построена модель нейрона и сформулированы принципы построения искусственных нейронных сетей.

Крупный толчок развитию нейрокибернетики дал американский нейрофизиолог Френк Розенблатт, предложивший в 1962 году свою модель нейронной сети — персептрон. Воспринятый первоначально с большим энтузиазмом, он вскоре подвергся интенсивным нападкам со стороны крупных научных авторитетов. И хотя подробный анализ их аргументов показывает, что они оспаривали не совсем тот персептрон, который предлагал Розенблатт, крупные исследования по нейронным сетям были свернуты почти на 10 лет.

Несмотря на это в 70-е годы было предложено много интересных разработок, таких, например, как когнитрон, способный хорошо распознавать достаточно сложные образы независимо от поворота изображения и изменения его масштаба.

В 1982 году американский биофизик Дж. Хопфилд предложил оригинальную модель нейронной сети, названную его именем. В последующие несколько лет было найдено множество эффективных алгоритмов: сеть встречного потока, двунаправленная ассоциативная память и др.

В киевском институте кибернетики с 70-х годов ведутся работы над стохастическими нейронными сетями.

Коллективы решающих правил

Давно известны приемы повышения качества принимаемых решений, состоящие в объединении специалистов той или иной области знаний в коллектив, вырабатывающий совместное решение. Идею коллективного решения можно применить и к "коллективу" формальных алгоритмов, что позволит повысить эффективность решения многих задач.

Для рационального использования особенностей различных алгоритмов при решении задач распознавания возможно объединить различные по характеру алгоритмы распознавания в коллективы, которые формируют классификационное решение на основе правил, принятых в теории коллективных решений. Пусть в некоторой ситуации Х принимается решение S. Тогда S=R(X), где R — алгоритм принятия решения в ситуации X. Предположим, что существует L различных алгоритмов решения задачи, т. е. Sl=Rl(X), l=1, 2, ... , L, где Sl — решение, полученное алгоритмом Rl. Будем называть множество алгоритмов {R}={R1, R2, ..., Ri.} коллективом алгоритмов решения задачи (коллективом решающих правил), если на множестве решений Sl в любой ситуации Х определено решающее правило F, т. е. S=F(S1, S2, ..., SL, X). Алгоритмы Rl принято называть членами коллектива, Sl — решением l-го члена коллектива, а S — коллективным решением. Функция F определяет способ обобщения индивидуальных решений в решения коллектива S. Поэтому синтез функции F, или способ обобщения, является центральным моментом в организации коллектива.

Принятие коллективного решения может быть использовано при решении различных задач. Так, в задаче управления под ситуацией понимается ситуация среды и целей управления, а под решением — самоуправление, приводящее объект в целевое состояние. В задачах прогноза Х — исходное, а S — прогнозируемое состояние. В задачах распознавания ситуацией Х является описание объекта X, т. е. его изображение, а решением S — номер образа, к которому принадлежит наблюдаемое изображение. Индивидуальное и коллективное решения в задаче распознавания состоят в отнесении некоторого изображения к одному из образов.
Наиболее интересными коллективами распознающих алгоритмов являются такие, в которых существует зависимость веса каждого решающего правила Rl от распознаваемого изображения. Например, вес решающего правила Rl может определяться соотношением

(4.57)

где Bl — область компетентности решающего правила Rl. Веса решающих правил выбираются так, что

(4.58)

для всех возможных значений X. Соотношение (4.57) означает, что решение коллектива определяется решением того решающего правила Ri, области компетентности которого принадлежит изображение объекта X. Такой подход представляет собой двухуровневую процедуру распознавания. На первом уровне определяется принадлежность изображения той или иной области компетентности, а уже на втором — вступает в силу решающее правило, компетентность которого максимальна в найденной области. Решение этого правила отождествляется с решением всего коллектива. Основным этапом в такой организации коллективного решения является обучение распознаванию областей компетентности. Практически постановкой этой задачи различаются правила организации решения коллектива. Области компетентности можно искать, используя вероятностные свойства правил коллектива, можно применить гипотезу компактности и считать, что одинаковым правилам должны соответствовать компактные области, которые можно выделить алгоритмами самообучения. В процессе обучения сначала выделяются компактные множества и соответствующие им области, а затем в каждой из этих областей восстанавливается свое решающее правило. Решение такого правила, действующего в определенной области, объявляется диктаторским, т. е. отождествляется с решением всего коллектива.

В персептроне каждый A-элемент может интерпретироваться как член коллектива. В процессе обучения все A-элементы приобретают веса, в соответствии с которыми эти A-элементы участвуют в коллективном решении. Особенность каждого A-элемента состоит в том, что он действует в некотором подпространстве исходного пространства, характер которого определяется связями между S- и A-элементами. Решение, получаемое на выходе персептрона, можно интерпретировать как средневзвешенное решение коллектива, состоящего из всех A-элементов.

Метод наименьших квадратов

Перед тем, как начинать рассмотрение МГУА, было бы полезно вспомнить (или узнать впервые) метод наименьших квадратов — наиболее распространенный метод подстройки линейно зависимых параметров.

Рассмотрим для примера МНК для трех аргументов.

Пусть функция T=T(U, V, W) задана таблицей, то есть из опыта известны числа Ui, Vi, Wi, Ti ( i = 1, … , n). Будем искать зависимость между этими данными в виде:

T(U,V,W)=aU+bV+cW (4.43)

где a, b, c — неизвестные параметры.

Подберем значения этих параметров так, чтобы была наименьшей сумма квадратов уклонений опытных данных Ti и теоретических Ti = aUwi + bVi + cWi, то есть сумма:

(4.44)

Величина

является функцией трех переменных a, b, c. Необходимым и достаточным условием существования минимума этой функции является равенство нулю частных производных функции по всем переменным, то есть:

(4.45)

Так как:

(4.46)

система для нахождения a, b, c будет иметь вид:

(4.47)

Данная система решается любым стандартным методом решения систем линейных уравнений (Гаусса, Жордана, Зейделя, Крамера).

Рассмотрим некоторые практические примеры нахождения приближающих функций.

Задача подбора коэффициентов

, , сводится к решению общей задачи при T=y, U=x2, V=x, W=1, .

Задача подбора коэффициентов

, , сводится к решению общей задачи при T=f, U=sin(x), V=cos(y), W=1/x, .

Если мы распространим МНК на случай с m параметрами,

(4.48)

то путем рассуждений, аналогичных приведенным выше, получим следующую систему линейных уравнений:

(4.49)

где

Метод потенциальных функций

Предположим, что требуется разделить два непересекающихся образа V1 и V2. Это значит, что в пространстве изображений существует, по крайней мере, одна функция, которая полностью разделяет множества, соответствующие образам V1 и V2. Эта функция должна принимать положительные значения в точках, которые соответствуют объектам, принадлежащим образу V1, и отрицательные — в точках образа V2. В общем случае таких разделяющих функций может быть много, тем больше, чем компактней разделяемые множества. В процессе обучения требуется построить одну из этих функций, иногда в некотором смысле наилучшую.

Метод потенциальных функций связан со следующей процедурой. В процессе обучения с каждой точкой пространства изображений, соответствующей единичному объекту из обучающей последовательности, связывается функция U(X, Xi), заданная на всем пространстве и зависящая от Xi как от параметра. Такие функции называются потенциальными, так как они напоминают функции потенциала электрического поля вокруг точечного электрического заряда. Изменение потенциала электрического поля по мере удаления от заряда обратно пропорционально квадрату расстояния. Потенциал, таким образом, может служить мерой удаления точки от заряда. Когда поле образовано несколькими зарядами, потенциал в каждой точке этого поля равен сумме потенциалов, создаваемых в этой точке каждым из зарядов. Если заряды, образующие поле, расположены компактной группой, потенциал поля будет иметь наибольшее значение внутри группы зарядов и убывать по мере удаления от нее.

Обучающей последовательности объектов соответствует последовательность векторов X1, X2, …, с которыми в пространстве изображений связана последовательность U(X, X1), U(X, X2), … потенциальных функций, используемых для построения функций f(X1, X2, …). По мере увеличения числа объектов в процессе обучения функция f должна стремиться к одной из разделяющих функций. В результате обучения могут быть построены потенциальные функции для каждого образа:

(4.35)

В качестве разделяющей функции f(X) можно выбрать функцию вида:

f(X)=U1(X)-U2(X), (4.36)

которая положительна для объектов одного образа и отрицательна для объектов другого.

В качестве потенциальной функции рассмотрим функцию вида

(4.37)

где — линейно независимая система функций; — действительные числа, отличные от нуля для всех j = 1, 2, … ; Xi — точка, соответствующая i-му объекту из обучающей последовательности. Предполагается, что и U(X, Xi) ограничены при .

В процессе обучения предъявляется обучающая последовательность и на каждом n-м такте обучения строится приближение fn(X), которое характеризуется следующей основной рекуррентной процедурой:

fn+1(X)=qnfn(X)+rnU(Xn+1,X), (4.38)

Разновидности алгоритмов потенциальных функций отличаются выбором значений qn и rn, которые являются фиксированными функциями номера n. Как правило, , а rn выбирается в виде:

(4.39)

где S(fn, f) — невозрастающие функции, причем

(4.40)

Коэффициенты представляют собой неотрицательную числовую последовательность, зависящую только от номера n. Кроме того, и (например, ) или .

Разработано несколько вариантов алгоритмов потенциальных функций, различие между которыми состоит в выборе законов коррекции разделяющей функции от шага к шагу, т. е. в выборе законов коррекции разделяющей функции от шага к шагу, иными словами, в выборе коэффициентов rn. Приведем два основных алгоритма потенциальных функций.

Будем считать, что (нулевое приближение). Пусть в результате применения алгоритма после n-го шага построена разделяющая функция fn(X), а на (n+1)-м шаге предъявлено изображение Xn+1, для которого известно действительное значение разделяющей функции f(Xn+1). Тогда функция fn+1(X) строится по следующему правилу:

(4.41)

Во втором алгоритме также принимается, что . Переход к следующему приближению, т. е. переход от функции fn(X) к fn+1(X), осуществляется в результате следующей рекуррентной процедуры:

(4.42)

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

Если в (ф. 5) принять и предположить, что xv может иметь только два значения 0 и 1, то в этом случае алгоритм потенциальных функций будет совпадать со схемой персептрона с индивидуальными порогами А-элементов и с коррекцией ошибок.Поэтому многие теоретические положения метода потенциальных функций могут быть успешно применены для анализа некоторых перцептронных схем.

Метод предельных упрощений (МПУ)

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

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

Пусть на некотором множестве объектов V заданы два подмножества

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

(4.50)

и признаком второго типа, если выполняются

(4.51)

Если же выполняются соотношения

(4.52)

то i-е свойство считается признаком первого типа относительно образа

, а если выполняются

(4.53)

то это же свойство объявляется признаком второго типа относительно образа

. Если свойство не обладает ни одной из приведенных особенностей, то оно вообще не относится к признакам и не участвует в формировании пространства.

Одинаковые признаки — это два признака xi и xj, порождающие подмножества V1j, V2j, V1i, V2i, такие, что

V1j= V1i и V2j= V2i. (4.54)

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

Метод предельных упрощений состоит в том, что в процессе обучения последовательно проверяются все возможные свойства объектов и из них выбираются только такие, которые обладают хотя бы одной из особенностей, определяемых соотношениями (4.50), (4.51). Такой отбор однотипных, но неодинаковых признаков продолжается до тех пор, пока при некотором значении размерности пространства не наступит безошибочное линейное разделение образов на обучающей последовательности. В зависимости от того, из признаков какого типа строится пространство, в качестве разделяющей плоскости выбирается плоскость, описываемая уравнением

(4.55)

либо уравнением

(4.56)

Каждый объект относится к одному из образов в зависимости от того, по какую сторону относительно плоскости находится соответствующий этому объекту вектор в пространстве признаков размерности n.

Модель нейронной сети с обратным распространением ошибки (back propagation)

В 1986 году Дж. Хинтон и его коллеги опубликовали статью с описанием модели нейронной сети и алгоритмом ее обучения, что дало новый толчок исследованиям в области искусственных нейронных сетей.

Нейронная сеть состоит из множества одинаковых элементов — нейронов, поэтому начнем с них рассмотрение работы искусственной нейронной сети.

Биологический нейрон моделируется как устройство, имеющее несколько входов (дендриты) и один выход (аксон). Каждому входу ставится в соответствие некоторый весовой коэффициент (w), характеризующий пропускную способность канала и оценивающий степень влияния сигнала с этого входа на сигнал на выходе. В зависимости от конкретной реализации, обрабатываемые нейроном сигналы могут быть аналоговыми или цифровыми (1 или 0). В теле нейрона происходит взвешенное суммирование входных возбуждений, и далее это значение является аргументом активационной функции нейрона, один из возможных вариантов которой представлен на рис. 1.

Рис. 4.2.  Искусственный нейрон

Будучи соединенными определенным образом, нейроны образуют нейронную сеть. Работа сети разделяется на обучение и адаптацию. Под обучением понимается процесс адаптации сети к предъявляемым эталонным образцам путем модификации (в соответствии с тем или иным алгоритмом) весовых коэффициентов связей между нейронами. Заметим, что этот процесс является результатом алгоритма функционирования сети, а не предварительно заложенных в нее знаний человека, как это часто бывает в системах искусственного интеллекта.

Среди различных структур нейронных сетей (НС) одной из наиболее известных является многослойная структура, в которой каждый нейрон произвольного слоя связан со всеми аксонами нейронов предыдущего слоя или, в случае первого слоя, со всеми входами НС. Такие НС называются полносвязными. Когда в сети только один слой, алгоритм ее обучения с учителем довольно очевиден, так как правильные выходные состояния нейронов единственного слоя заведомо известны и подстройка синаптических связей идет в направлении, минимизирующем ошибку на выходе сети.
По этому принципу строится, например, алгоритм обучения однослойного персептрона. В многослойных же сетях оптимальные выходные значения нейронов всех слоев, кроме последнего, как правило, не известны, и двух- или более слойный персептрон уже невозможно обучить, руководствуясь только величинами ошибок на выходах НС. Один из вариантов решения этой проблемы: разработка наборов выходных сигналов, соответствующих входным, для каждого слоя НС, что, конечно, является очень тру доемкой операцией и не всегда осуществимо. Второй вариант: динамическая подстройка весовых коэффициентов синапсов, в ходе которой выбираются, как правило, наиболее слабые связи и изменяются на малую величину в ту или иную сторону, а сохраняются только те изменения, которые повлекли уменьшение ошибки на выходе всей сети. Очевидно, что данный метод "тыка", несмотря на свою кажущуюся простоту, требует громоздких рутинных вычислений. И, наконец, третий, более приемлемый вариант: распространение сигналов ошибки от выходов НС к ее входам, в направлении, обратном прямому распространению сигналов в обычном режиме работы. Этот алгоритм обучения НС получил название процедуры обратного распространения. Именно он будет рассмотрен в дальнейшем.

Согласно методу наименьших квадратов, минимизируемой целевой функцией ошибки НС является величина:

(4.3)

где – реальное выходное состояние нейрона j выходного слоя N нейронной сети при подаче на ее входы p-го образа; djp – идеальное (желаемое) выходное состояние этого нейрона.

Суммирование ведется по всем нейронам выходного слоя и по всем обрабатываемым сетью образам. Минимизация ведется методом градиентного спуска, что означает подстройку весовых коэффициентов следующим образом:

(4.4)

Здесь wij – весовой коэффициент синаптической связи, соединяющей i-ый нейрон слоя n-1 с j-ым нейроном слоя n, – коэффициент скорости обучения, 0<<1.

Как показано в [2],

(4.5)

Здесь под yj, как и раньше, подразумевается выход нейрона j, а под sj – взвешенная сумма его входных сигналов, то есть аргумент активационной функции.


Так как множитель dyj/ dsj является производной этой функции по ее аргументу, из этого следует, что производная активационной функция должна быть определена на всей оси абсцисс. В связи с этим функция единичного скачка и прочие активационные функции с неоднородностями не подходят для рассматриваемых НС. В них применяются такие гладкие функции, как гиперболический тангенс или классический сигмоид с экспонентой. В случае гиперболического тангенса

(4.6)

Третий множитель , очевидно, равен выходу нейрона предыдущего слоя .

Что касается первого множителя в (4.5), он легко раскладывается следующим образом[2]:

(4.7)

Здесь суммирование по k выполняется среди нейронов слоя n+1.

Введя новую переменную

(4.8)

мы получим рекурсивную формулу для расчетов величин слоя n из величин более старшего слоя n+1.

(4.9)

Для выходного же слоя

(4.10)

Теперь мы можем записать (4.4) в раскрытом виде:

(4.11)

Иногда для придания процессу коррекции весов некоторой инерционности, сглаживающей резкие скачки при перемещении по поверхности целевой функции, (4.11) дополняется значением изменения веса на предыдущей итерации

(4.12)

где – коэффициент инерционности, t – номер текущей итерации.

Таким образом, полный алгоритм обучения НС с помощью процедуры обратного распространения строится так:

Подать на входы сети один из возможных образов и в режиме обычного функционирования НС, когда сигналы распространяются от входов к выходам, рассчитать значения последних. Напомним, что

(4.13)

где M – число нейронов в слое n-1 с учетом нейрона с постоянным выходным состоянием +1, задающего смещение; – i-ый вход нейрона j слоя n.

, где f() – сигмоид, (4.14)

(4.15)

где Iq – q-ая компонента вектора входного образа.

Рассчитать для выходного слоя по формуле (4.10). Рассчитать по формуле (4.11) или (4.12) изменения весов слоя N.Рассчитать по формулам (4.9) и (4.11) (или (4.9) и (4.10)) соответственно и для всех остальных слоев, n=N-1,...1.Скорректировать все веса в НС

(4.16)

Рис. 4.3.  Диаграмма сигналов в сети при обучении по алгоритму обратного распространения



Если ошибка сети существенна, перейти на шаг 1. В противном случае – конец.Сети на шаге 1 попеременно в случайном порядке предъявляются все тренировочные образы, чтобы сеть, образно говоря, не забывала одни по мере запоминания других. Алгоритм иллюстрируется рис. 4.3.

Из выражения (4.10) следует, что, когда выходное значение стремится к нулю, эффективность обучения заметно снижается. При двоичных входных векторах в среднем половина весовых коэффициентов не будет корректироваться [3], поэтому область возможных значений выходов нейронов [0,1] желательно сдвинуть в пределы [-0.5,+0.5], что достигается простыми модификациями логистических функций. Например, сигмоид с экспонентой преобразуется к виду

(4.17)

Теперь коснемся вопроса емкости НС, то есть числа образов, предъявляемых на ее входы, которые она способна научиться распознавать. Для сетей с числом слоев больше двух он остается открытым. Как показано в [4], для НС с двумя слоями, то есть одним выходным и одним скрытым слоем, детерминистская емкость сети Cd оценивается так:

Nw/Ny<Cd<Nw/Nylog(Nw/Ny) (4.18)

где Nw – число подстраиваемых весов, Ny – число нейронов в выходном слое.

Следует отметить, что данное выражение получено с учетом некоторых ограничений. Во-первых, число входов Nx и нейронов в скрытом слое Nh должно удовлетворять неравенству Nx+Nh>Ny. Во-вторых, Nw/Ny>1000. Однако вышеприведенная оценка выполнялась для сетей с активационными функциями нейронов в виде порога, а емкость сетей с гладкими активационными функциями, например – (4.17), обычно больше. Кроме того, фигурирующее в названии емкости прилагательное "детерминистский" означает, что полученная оценка емкости подходит абсолютно для всех возможных входных образов, которые могут быть представлены Nx входами. В действительности распределение входных образов, как правило, обладает некоторой регулярностью, что позволяет НС проводить обобщение и, таким образом, увеличивать реальную емкость. Так как распределение образов, в общем случае, заранее не известно, мы можем говорить о такой емкости только предположительно, но обычно она раза в два превышает емкость детерминистскую.



В продолжение разговора о емкости НС логично затронуть вопрос о требуемой мощности выходного слоя сети, выполняющего окончательную классификацию образов. Дело в том, что для разделения множества входных образов, например, по двум классам, достаточно всего одного выхода. При этом каждый логический уровень – "1" и "0" – будет обозначать отдельный класс. На двух выходах можно закодировать уже 4 класса, и так далее. Однако результаты работы сети, организованной таким образом, можно сказать – "под завязку", – не очень надежны. Для повышения достоверности классификации желательно ввести избыточность путем выделения каждому классу одного нейрона в выходном слое или, что еще лучше, нескольких, каждый из которых обучается определять принадлежность образа к классу со своей степенью достоверности, например: высокой, средней и низкой. Такие НС позволяют проводить классификацию входных образов, объединенных в нечеткие (размытые или пересекающиеся) множества. Это свойство приближает п одобные НС к условиям реальной жизни.

Рассматриваемая НС имеет несколько "узких мест". Во-первых, в процессе обучения может возникнуть ситуация, когда большие положительные или отрицательные значения весовых коэффициентов сместят рабочую точку на сигмоидах многих нейронов в область насыщения. Малые величины производной от логистической функции приведут в соответствие с (4.9) и (4.10) к остановке обучения, что парализует НС. Во-вторых, применение метода градиентного спуска не гарантирует, что будет найден глобальный, а не локальный минимум целевой функции. Эта проблема связана еще с одной, а именно – с выбором величины скорости обучения. Доказательство сходимости обучения в процессе обратного распространения основано на производных — то есть приращения весов и, следовательно, скорость обучения должны быть бесконечно малыми, — однако в этом случае обучение будет происходить неприемлемо медленно. С другой стороны, слишком большие коррекции весов могут привести к постоянной неустойчивости процесса обучения.


Поэтому в качестве обычно выбирается число меньше 1, но не очень маленькое, например, 0.1, и оно, вообще говоря, может постепенно уменьшаться в процессе обучения. Кроме того, для исключения случайных попаданий в локальные минимумы иногда, после того как значения весовых коэффициентов стабилизируются, кратковременно сильно увеличивают, чтобы начать градиентный спуск из новой точки. Если повторение этой процедуры несколько раз приведет алгоритм в одно и то же состояние НС, можно более или менее уверенно сказать, что найден глобальный максимум, а не какой-то другой.

Существует и иной метод исключения локальных минимумов, а заодно и паралича НС, заключающийся в применении стохастических НС, но о них лучше поговорить отдельно.

Нейронные сети Хопфилда и Хэмминга

Среди различных конфигураций искуственных нейронных сетей (НС) встречаются такие, при классификации которых по принципу обучения, строго говоря, не подходят ни обучение с учителем, ни обучение без учителя. В таких сетях весовые коэффициенты синапсов рассчитываются только однажды, перед началом функционирования сети, на основе информации об обрабатываемых данных, и все обучение сети сводится именно к этому расчету. С одной стороны, предъявление априорной информации можно расценивать как помощь учителя, но с другой – сеть фактически просто запоминает образцы до того, как на ее вход поступают реальные данные, и не может изменять свое поведение, поэтому говорить о звене обратной связи с "миром" (учителем) не приходится. Из сетей с подобной логикой работы наиболее известны сеть Хопфилда и сеть Хэмминга, которые обычно используются для организации ассоциативной памяти. Далее речь пойдет именно о них.

Структурная схема сети Хопфилда приведена на рис.4.4. Она состоит из единственного слоя нейронов, число которых является одновременно числом входов и выходов сети. Каждый нейрон связан синапсами со всеми остальными нейронами, а также имеет один входной синапс, через который осуществляется ввод сигнала. Выходные сигналы, как обычно, образуются на аксонах.

Рис. 4.4.  Структурная схема сети Хопфилда

Задача, решаемая данной сетью в качестве ассоциативной памяти, как правило, формулируется следующим образом. Известен некоторый набор двоичных сигналов (изображений, звуковых оцифровок, прочих данных, описывающих некие объекты или характеристики процессов), которые считаются образцовыми. Сеть должна уметь из произвольного неидеального сигнала, поданного на ее вход, выделить ("вспомнить" по частичной информации) соответствующий образец (если такой есть) или "дать заключение" о том, что входные данные не соответствуют ни одному из образцов. В общем случае, любой сигнал может быть описан вектором X = { xi: i=0...n-1}, где n – число нейронов в сети и размерность входных и выходных векторов.
Каждый элемент xi равен либо +1, либо -1. Обозначим вектор, описывающий k-ый образец, через Xk, а его компоненты, соответственно, –

, k=0...m-1, где m – число обра зцов. Когда сеть распознaет (или "вспомнит") какой-либо образец на основе предъявленных ей данных, ее выходы будут содержать именно его, то есть Y = Xk, где Y – вектор выходных значений сети: Y = { yi: i=0,...n-1}. В противном случае, выходной вектор не совпадет ни с одним образцовым.

Если, например, сигналы представляют собой некие изображения, то, отобразив в графическом виде данные с выхода сети, можно будет увидеть картинку, полностью совпадающую с одной из образцовых (в случае успеха) или же "вольную импровизацию" сети (в случае неудачи).

На стадии инициализации сети весовые коэффициенты синапсов устанавливаются следующим образом:

(4.25)

Здесь i и j – индексы, соответственно, предсинаптического и постсинаптического нейронов; , – i-ый и j-ый элементы вектора k-ого образца.

Алгоритм функционирования сети следующий (p – номер итерации):

На входы сети подается неизвестный сигнал. Фактически его ввод осуществляется непосредственной установкой значений аксонов:

yi(0) = xi , i = 0...n-1, (4.26)

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

Рассчитывается новое состояние нейронов

j=0...n-1 (4.27)

и новые значения аксонов

yi(p+1) = f[sj(p+1)] (4.28)


Рис. 4.5.  Активационные функции.

где f – активационная функция в виде скачка, приведенная на рис. 4.5 а.

Проверка, изменились ли выходные значения аксонов за последнюю итерацию. Если да – переход к пункту 2, иначе (если выходы стабилизировались) – конец. При этом выходной вектор представляет собой образец, наилучшим образом сочетающийся с входными данными.Как говорилось выше, иногда сеть не может провести распознавание и выдает на выходе несуществующий образ. Это связано с проблемой ограниченности возможностей сети.


Для сети Хопфилда число запоминаемых образов m не должно превышать величины, примерно равной 0.15n. Кроме того, если два образа А и Б сильно похожи, они, возможно, будут вызывать у сети перекрестные ассоциации, то есть предъявление на входы сети вектора А приведет к появлению на ее выходах вектора Б, и наоборот.


Рис. 4.6.  Структурная схема сети Хэмминга

Когда нет необходимости, чтобы сеть в явном виде выдавала образец, то есть достаточно, скажем, получать номер образца, ассоциативную память успешно реализует сеть Хэмминга. Данная сеть характеризуется, по сравнению с сетью Хопфилда, меньшими затратами на память и объемом вычислений, что становится очевидным из ее структуры (рис. 4.6)

Сеть состоит из двух слоев. Первый и второй слои имеют по m нейронов, где m – число образцов. Нейроны первого слоя имеют по n синапсов, соединенных со входами сети (образующими фиктивный нулевой слой). Нейроны второго слоя связаны между собой ингибиторными (отрицательными обратными) синаптическими связями. Единственный синапс с положительной обратной связью для каждого нейрона соединен с его же аксоном.

Идея работы сети состоит в нахождении расстояния Хэмминга от тестируемого образа до всех образцов. Расстоянием Хэмминга называется число отличающихся битов в двух бинарных векторах. Сеть должна выбрать образец с минимальным расстоянием Хэмминга до неизвестного входного сигнала, в результате чего будет активизирован только один выход сети, соответствующий этому образцу.

На стадии инициализации весовым коэффициентам первого слоя и порогу активационной функции присваиваются следующие значения:

,i=0...n-1, k=0...m-1 (4.29)

Tk = n/2, k = 0...m-1 (4.30)

Здесь – i-ый элемент k-ого образца.

Весовые коэффициенты тормозящих синапсов во втором слое берут равными некоторой величине 0 < < 1/m. Синапс нейрона, связанный с его же аксоном имеет вес +1.

Алгоритм функционирования сети Хэмминга следующий:

На входы сети подается неизвестный вектор X = {xi:i=0...n-1}, исходя из которого рассчитываются состояния нейронов первого слоя (верхний индекс в скобках указывает номер слоя):



, j=0...m-1 (4.31)

После этого полученными значениями инициализируются значения аксонов второго слоя:

, j = 0...m-1 (4.32)

Вычислить новые состояния нейронов второго слоя:

(4.33)

и значения их аксонов:

(4.34)

Активационная функция f имеет вид порога, причем величина F должна быть достаточно большой, чтобы любые возможные значения аргумента не приводили к насыщению.

Проверить, изменились ли выходы нейронов второго слоя за последнюю итерацию. Если да – перейти к шагу 2. Иначе – конец.

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

Нейронные сети: обучение без учителя

Рассмотренный в предыдущей главе алгоритм обучения нейронной сети с помощью процедуры обратного распространения подразумевает наличие некоего внешнего звена, предоставляющего сети, кроме входных, также и целевые выходные образы. Алгоритмы, пользующиеся подобной концепцией, называются алгоритмами обучения с учителем. Для их успешного функционирования необходимо наличие экспертов, создающих на предварительном этапе для каждого входного образа эталонный выходной. Так как создание искусственного интеллекта движется по пути копирования природных прообразов, ученые не прекращают спор на тему, можно ли считать алгоритмы обучения с учителем натуральными или же они полностью искусственны. Например, обучение человеческого мозга, на первый взгляд, происходит без учителя: на зрительные, слуховые, тактильные и прочие рецепторы поступает информация извне, и внутри нервной системы происходит некая самоорганизация. Однако, нельзя отрицать и того, что в жизни человека немало учителей – и в буквальном, и в переносном смысле, – которые координируют внешние воздействия. Вместе в тем, чем бы ни закончился спор приверженцев этих двух концепций обучения, они обе имеют право на существование.

Главная черта, делающая обучение без учителя привлекательным, – это его "самостоятельность". Процесс обучения, как и в случае обучения с учителем, заключается в подстраивании весов синапсов. Некоторые алгоритмы, правда, изменяют и структуру сети, то есть количество нейронов и их взаимосвязи, но такие преобразования правильнее назвать более широким термином – самоорганизацией, и в рамках данной лекции они рассматриваться не будут. Очевидно, что подстройка синапсов может проводиться только на основании информации, доступной в нейроне, то есть его состояния и уже имеющихся весовых коэффициентов. Исходя из этого соображения и, что более важно, по аналогии с известными принципами самоорганизации нервных клеток, построены алгоритмы обучения Хебба.

Сигнальный метод обучения Хебба заключается в изменении весов по следующему правилу:

(4.19)

где – выходное значение нейрона i слоя (n-1), – выходное значение нейрона j слоя n; и – весовой коэффициент синапса, соединяющего эти нейроны, на итерациях t и t-1 соответственно; – коэффициент скорости обучения. Здесь и далее, для общности, под n подразумевается произвольный слой сети. При обучении по данному методу усиливаются связи между возбужденными нейронами.

Существует также и дифференциальный метод обучения Хебба.

(4.19)

Здесь и – выходное значение нейрона i слоя n-1 соответственно на итерациях t и t-1; и – то же самое для нейрона j слоя n. Как видно из формулы (2), сильнее всего обучаются синапсы, соединяющие те нейроны, выходы которых наиболее динамично изменились в сторону увеличения.

Полный алгоритм обучения с применением вышеприведенных формул будет выглядеть так:

На стадии инициализации всем весовым коэффициентам присваиваются небольшие случайные значения.На входы сети подается входной образ, и сигналы возбуждения распространяются по всем слоям согласно принципам классических прямопоточных (feedforward) сетей[1], то есть для каждого нейрона рассчитывается взвешенная сумма его входов, к которой затем применяется активационная (передаточная) функция нейрона, в результате чего получается его выходное значение , i=0...Mi-1, где Mi – число нейронов в слое i; n=0...N-1, а N – число слоев в сети.На основании полученных выходных значений нейронов по формуле (4.18) или (4.19) производится изменение весовых коэффициентов.Цикл с шага 2, пока выходные значения сети не стабилизируются с заданной точностью. Применение этого нового способа определения завершения обучения, отличного от использовавшегося для сети обратного распространения, обусловлено тем, что подстраиваемые значения синапсов фактически не ограничены. На втором шаге цикла попеременно предъявляются все образы из входного набора.Следует отметить, что вид откликов на каждый класс входных образов не известен заранее и будет представлять собой произвольное сочетание состояний нейронов выходного слоя, обусловленное случайным распределением весов на стадии инициализации.


Вместе с тем, сеть способна обобщать схожие образы, относя их к одному классу. Тестирование обученной сети позволяет определить топологию классов в выходном слое. Для приведения откликов обученной сети к удобному представлению можно дополнить сеть одним слоем, который, например, по алгоритму обучения однослойного персептрона, необходимо заставить отображать выходные реакции сети в требуемые образы.

Другой алгоритм обучения без учителя – алгоритм Кохонена – предусматривает подстройку синапсов на основании их значений от предыдущей итерации.

(4.20)

Из вышеприведенной формулы видно, что обучение сводится к минимизации разницы между входными сигналами нейрона, поступающими с выходов нейронов предыдущего слоя , и весовыми коэффициентами его синапсов.

Полный алгоритм обучения имеет примерно такую же структуру, как в методах Хебба, но на шаге 3 из всего слоя выбирается нейрон, значения синапсов которого максимально походят на входной образ, и подстройка весов по формуле (4.20) проводится только для него. Эта так называемая аккредитация может сопровождаться затормаживанием всех остальных нейронов слоя и введением выбранного нейрона в насыщение. Выбор такого нейрона может осуществляться, например, расчетом скалярного произведения вектора весовых коэффициентов с вектором входных значений. Максимальное произведение дает выигравший нейрон.

Другой вариант – расчет расстояния между этими векторами в p-мерном пространстве, где p – размер векторов.

(4.21)

где j – индекс нейрона в слое n, i – индекс суммирования по нейронам слоя (n-1), wij – вес синапса, соединяющего нейроны; выходы нейронов слоя (n-1) являются входными значениями для слоя n. Корень в формуле (4.21) брать не обязательно, так как важна лишь относительная оценка различных Dj.

В данном случае, "побеждает" нейрон с наименьшим расстоянием. Иногда слишком часто получающие аккредитацию нейроны принудительно исключаются из рассмотрения, чтобы "уравнять права" всех нейронов слоя. Простейший вариант такого алгоритма заключается в торможении только что выигравшего нейрона.



При использовании обучения по алгоритму Кохонена существует практика нормализации входных образов, а также – на стадии инициализации – и нормализации начальных значений весовых коэффициентов.

(4.22)

где xi – i-ая компонента вектора входного образа или вектора весовых коэффициентов, а n – его размерность. Это позволяет сократить длительность процесса обучения.

Инициализация весовых коэффициентов случайными значениями может привести к тому, что различные классы, которым соответствуют плотно распределенные входные образы, сольются или, наоборот, раздробятся на дополнительные подклассы в случае близких образов одного и того же класса. Для избежания такой ситуации используется метод выпуклой комбинации [3]. Суть его сводится к тому, что входные нормализованные образы подвергаются преобразованию:

(4.23)

где xi – i-ая компонента входного образа, n – общее число его компонент, – коэффициент, изменяющийся в процессе обучения от нуля до единицы, в результате чего вначале на входы сети подаются практически одинаковые образы, а с течением времени они все больше сходятся к исходным. Весовые коэффициенты устанавливаются на шаге инициализации равными величине

(4.24)

где n – размерность вектора весов для нейронов инициализируемого слоя.

На основе рассмотренного выше метода строятся нейронные сети особого типа – так называемые самоорганизующиеся структуры – self-organizing feature maps (этот устоявшийся перевод с английского, на мой взгляд, не очень удачен, так как речь идет не об изменении структуры сети, а только о подстройке синапсов). Для них после выбора из слоя n нейрона j с минимальным расстоянием Dj (4.21) обучается по формуле (4.20) не только этот нейрон, но и его соседи, расположенные в окрестности R. Величина R на первых итерациях очень большая, так что обучаются все нейроны, но с течением времени она уменьшается до нуля. Таким образом, чем ближе конец обучения, тем точнее определяется группа нейронов, отвечающих каждому классу образов.

Общая схема построения алгоритмов метода группового учета аргументов (МГУА)

Рис. 4.7.  Селекция самого черного тюльпана при расширяющемся опытном поле (эквивалент полного перебора), и при постоянном размере поля (эквивалент селекции при сохранении свободы выбора решений F = const)

Заимствование алгоритмов переработки информации у природы является одной из основных идей кибернетики. "Гипотеза селекции" утверждает, что алгоритм массовой селекции растений или животных является оптимальным алгоритмом переработки информации в сложных задачах. При массовой селекции высевается некоторое количество семян. В результате опыления образуются сложные наследственные комбинации. Селекционеры выбирают некоторую часть растений, у которых интересующее их свойство выражено лучше всего (эвристический критерий). Семена этих растений собирают и снова высевают для образования новых, еще более сложных комбинаций. Через несколько поколений селекция останавливается и ее результат является оптимальным. Если чрезмерно продолжать селекцию, то наступит "инцухт" — вырождение растений. Существует оптимальное число поколений и оптимальное количество семян, отбираемых в каждом из них.

Алгоритмы МГУА воспроизводят схему массовой селекции [5], показанной на рис. 4.7. В них есть генераторы усложняющихся из ряда в ряд комбинаций и пороговые самоотборы лучших из них. Так называемое "полное" описание объекта

,

где f — некоторая элементарная функция, например степенной полином, заменяется несколькими рядами "частных" описаний:

1-ряд селекции: y1= f(x1x2), y2= f(x1x3),..., ys= f(xm-1xm),

2-ряд селекции: z1= f(y1y2), z2= f(y1y2),..., zp= f(ys-1ys), где s=c2,

и т.д.

Входные аргументы и промежуточные переменные сопрягаются попарно, и сложность комбинаций на каждом ряду обработки информации возрастает (как при массовой селекции), пока не будет получена единственная модель оптимальной сложности.

Каждое частное описание является функцией только двух аргументов.
Поэтому его коэффициенты легко определить по данным обучающей последовательности при малом числе узлов интерполяции [4]. Исключая промежуточные переменные (если это удается), можно получить "аналог" полного описания. Математика не запрещает обе эти операции. Например, по десяти узлам интерполяции можно получить в результате оценки коэффициентов полинома сотой степени и т. д.

Из ряда в ряд селекции пропускается только некоторое количество самых регулярных переменных. Степень регулярности оценивается по величине среднеквадратичной ошибки (средней для всех выбираемых в каждом поколении переменных или для одной самой точной переменой) на отдельной проверочной последовательности данных. Иногда в качестве показателя регулярности используется коэффициент корреляции.

Ряды селекции наращиваются до тех пор, пока регулярность повышается. Как только достигнут минимум ошибки, селекцию, во избежание "инцухта", следует остановить. Практически рекомендуется остановить селекцию даже несколько раньше достижения полного минимума, как только ошибка начинает падать слишком медленно. Это приводит к более простым и более достоверным уравнениям.

Персептроны

Пока о проблеме обучения распознаванию образов удавалось говорить в общих чертах, не выделяя конкретные методы или алгоритмы, — не возникало и трудностей, появляющихся всяких раз, когда приходится иметь дело с огромным множеством примеров, у которых общий подход к решению проблемы ОРО. Коварство самой проблемы состоит в том, что, на первый взгляд, все методы и алгоритмы кажутся совершенно различными и, что самое неприятное, часто никакой из них не годится для решения той задачи, которую крайне необходимо срочно решить. И тогда появляется желание выдумать новый алгоритм, который, может быть, достигнет цели. Очевидно, именно это привело к возникновению огромного множества алгоритмов, в котором не так-то легко разобраться.

Один из методов решения задач обучения распознаванию образов основан на моделировании гипотетического механизма человеческого мозга. Структура модели заранее постулируется. При таком подходе уровень биологических знаний или гипотез о биологических механизмах является исходной предпосылкой, на которой базируются модели этих механизмов. Примером такого направления в теории и практике проблемы ОРО является класс устройств, называемых персептронами. Нужно отметить, что персептроны на заре своего возникновения рассматривались только как эвристические модели механизма мозга. Впоследствии они стали основополагающей схемой в построении кусочно-линейных моделей, обучающихся распознаванию образов.

Рис. 4.1.  Персептрон

В наиболее простом виде персептрон (рис. 4.1.) состоит из совокупности чувствительных (сенсорных) элементов (S-элементов), на которые поступают входные сигналы. S-элементы случайным образом связаны с совокупностью ассоциативных элементов (А-элементов), выход которых отличается от нуля только тогда, когда возбуждено достаточно большое число S-элементов, воздействующих на один А-элемент. А-элементы соединены с реагирующими элементами (R-элементами) связями, коэффициенты усиления (v) которых переменны и изменяются в процессе обучения. Взвешенные комбинации выходов R-элементов составляют реакцию системы, которая указывает на принадлежность распознаваемого объекта определенному образу.
Если распознаются только два образа, то в персептроне устанавливается только один R-элемент, который обладает двумя реакциями — положительной и отрицательной. Если образов больше двух, то для каждого образа устана вливают свой R-элемент, а выход каждого такого элемента представляет линейную комбинацию выходов A-элементов:

(4.1)

где Rj — реакция j-го R-элемента; xi — реакция i-го A-элемента; vij — вес связи от i-го A-элемента к j-му R элементу; — порог j-го R-элемента.

Аналогично записывается уравнение i-го A-элемента:

(4.2)

Здесь сигнал yk может быть непрерывным, но чаще всего он принимает только два значения: 0 или 1. Сигналы от S-элементов подаются на входы А-элементов с постоянными весами, равными единице, но каждый А-элемент связан только с группой случайно выбранных S-элементов. Предположим, что требуется обучить персептрон различать два образа V1 и V2. Будем считать, что в персептроне существует два R-элемента, один из которых предназначен образу V1, а другой — образу V2. Персептрон будет обучен правильно, если выход R1 превышает R2, когда распознаваемый объект принадлежит образу V1, и наоборот. Разделение объектов на два образа можно провести и с помощью только одного R-элемента. Тогда объекту образа V1 должна соответствовать положительная реакция R-элемента, а объектам образа V2 — отрицательная.

Персептрон обучается путем предъявления обучающей последовательности изображений объектов, принадлежащих образам V1 и V2. В процессе обучения изменяются веса vi А-элементов. В частности, если применяется система подкрепления с коррекцией ошибок, прежде всего учитывается правильность решения, принимаемого персептроном. Если решение правильно, то веса связей всех сработавших А-элементов, которые ведут к R-элементу, выдавшему правильное решение, увеличиваются, а веса несработавших А-элементов остаются неизменными. Можно оставлять неизменными веса сработавших А-элементов, но уменьшать веса несработавших. В некоторых случаях веса сработавших связей увеличивают, а несработавших — уменьшают.


После процесса обучения персептрон сам, без учителя, начинает классифицировать новые объекты.

Если персептрон действует по описанной схеме и в нем допускаются лишь связи, идущие от бинарных S-элементов к A-элементам и от A-элементов к единственному R-элементу, то такой персептрон принято называть элементарным -персептроном. Обычно классификация C(W) задается учителем. Персептрон должен выработать в процессе обучения классификацию, задуманную учителем.

О персептронах было сформулировано и доказано несколько основополагающих теорем, две из которых, определяющие основные свойства персептрона, приведены ниже.

Теорема 1. Класс элементарных -персептронов, для которых существует решение для любой задуманной классификации, не является пустым.

Эта теорема утверждает, что для любой классификации обучающей последовательности можно подобрать такой набор (из бесконечного набора) А-элементов, в котором будет осуществлено задуманное разделение обучающей последовательности при помощи линейного решающего правила .

Теорема 2. Если для некоторой классификации C(W) решение существует, то в процессе обучения -персептрона с коррекцией ошибок, начинающегося с произвольного исходного состояния, это решение будет достигнуто в течение конечного промежутка времени.

Смысл этой теоремы состоит в том, что если относительно задуманной классификации можно найти набор А-элементов, в котором существует решение, то в рамках этого набора оно будет достигнуто в конечный промежуток времени.

Обычно обсуждают свойства бесконечного персептрона, т. е. персептрона с бесконечным числом А-элементов со всевозможными связями с S-элементами (полный набор A-элементов). Для таких персептронов решение всегда существует, а раз оно существует, то оно и достижимо в -персептронах с коррекцией ошибок.

Очень интересную область исследований представляют собой многослойные персептроны и персептроны с перекрестными связями, но теория этих систем практически еще не разработана.

Быстрый кластерный анализ

Процедура иерархического кластерного анализа хороша для малого числа объектов. Ее преимущество в том, что каждый объект можно, образно говоря, пощупать руками. Но эта процедура не годится для огромных социологических данных из-за трудоемкости агломеративного алгоритма и слишком больших размеров дендрограмм.

Здесь наиболее приемлем быстрый алгоритм, носящий название метода "k-средних". Он реализуется в пакете командой QUICK CLUSTER или командой меню k-means.

Алгоритм заключается в следующем: выбирается заданное число k-точек и на первом шаге эти точки рассматриваются как "центры" кластеров. Каждому кластеру соответствует один центр. Объекты распределяются по кластерам по такому принципу: каждый объект относится к кластеру с ближайшим к этому объекту центром. Таким образом, все объекты распределились по k кластерам.

Затем заново вычисляются центры этих кластеров, которыми после этого момента считаются покоординатные средние кластеров. После этого опять перераспределяются объекты. Вычисление центров и перераспределение объектов происходит до тех пор, пока не стабилизируются центры.

Синтаксис команды:

QUICK CLUSTER W3d1 TO W3D6/CRITERIA CLUSTERS(3) /MISSING=PAIRWISE /SAVE CLUSTER(SAVCLU) /PRINT ANOVA.

За именем команды располагаются переменные, по которым происходит кластеризация. Параметр /CRITERIA CLUSTERS задает в скобках число кластеров. Подкомандой /SAVE CLUSTER можно сохранить полученную классификацию в виде переменной, имя которой дается в скобках. Подкоманда /PRINT ANOVA позволяет провести по каждой переменной одномерный дисперсионный анализ — сравнение средних в кластерах. Этот анализ имеет лишь описательное значение и позволяет определить переменные, которые не оказывают никакого влияния на классификацию.

Команда использует только евклидово расстояние. При этом часть переменных может иметь неопределенные значения, расстояния до центров определяются по определенным значениям. Для использования такой возможности следует употребить подкоманду /MISSING=PAIRWISE.

Часто переменные имеют разный диапазон изменений, так как измерены они в различных шкалах или просто из-за того, что характеризуют разные свойства объектов (например, рост и вес, килограммы и граммы). В этих условиях основное влияние на кластеризацию окажут переменные, имеющие большую дисперсию. Поэтому перед кластеризацией полезно стандартизовать переменные. К сожалению, в "быстром" кластерном анализе средства стандартизации не предусмотрены непосредственно, как в процедуре иерархического кластерного анализа.

Для этого можно использовать команду DESCRIPTIVE. Напомним, что подкоманда /save в ней позволяет автоматически сохранить стандартизованные переменные. Кроме того, хорошие средства стандартизующих преобразований шкал дает команда RANK.

В выдаче распечатываются центры кластеров (средние значения переменных кластеризации для каждого кластера), получаемые на каждой итерации алгоритма. Однако для нас полезна лишь часть выдачи, помеченная текстом "Final centres".

Интерпретация кластеров осуществляется на основе сравнения средних значений, выдаваемых процедурой, а также исследования сохраненной переменной средствами статистического пакета.

Пример использования QUICK CLUSTER. Для иллюстрации построим классификацию по предварительно отобранным данным городских семей по жилплощади и душевому доходу. Такая классификация может грубо, но наглядно показать различие семей по благосостоянию.

В данных, полученных из обследования RLMS 1998 г. имеются переменные: c5 — жилплощадь, приходящаяся на семью, memb — число членов семьи, df14 — суммарные денежные доходы семьи.

В ранее проведенном анализе выяснилось, что не только доходы имеют близкое к логарифмически нормальному распределение, но и жилплощадь. Для того, чтобы кластерный анализ не конструировал кластеры из "выбросов" больших доходов и жилплощади, мы работаем со стандартизованным логарифмам душевых доходов и логарифмам жилплощади, приходящейся на члена семьи.

*вычисление логарифма жилплощади на члена семьи.



compute lns=Ln(dc5/memb).

*вычисление логарифма душевого дохода.

compute lincome=ln(df14/memb).

*стандартизация переменных.

DESCRIPTIVES VARIABLES=lincome lns/SAVE .

QUICK CLUSTER zlincome zlns /MISSING=PAIRWISE /CRITERIA= CLUSTER(3) /SAVE CLUSTER /PRINT ANOVA.

На основании таблицы 7. 5 центров классов интерпретация полученных кластеров следующая:

Кластер 1 — зажиточные семьи, имеющие относительно большой доход и жилплощадь.

Кластер 2 — семьи, проживающие в квартирах с небольшой площадью, но имеющие относительно высокий доход.

Кластер 3 — семьи, имеющие низкий доход и ограниченные в жилплощади.

Кластер 4 — семьи, имеющие несколько больший доход, чем в среднем, но ограниченные в жилплощади.

Таблица 5.3. Центры кластеров (Final Cluster Centers)Cluster

	1	2	3	4
Zscore(LINCOME)	1.26	0.52	-1.08	-0.40
Zscore(LNS)	1.35	-0.56	-0.86	0.58

Таблица 5.4. Дисперсионный анализ в методе k-средних (ANOVA, имееет только описательное значение)ClusterErrorFSig

	Mean Square	Df		Mean Square	Df
ZLINCOME Zscore(LINCOME)	513.006	3	.370	2440	1384.7	0
ZLNS Zscore(LNS)	530.153	3	.363	2491	1461.6	0

Рис. 5.5.  Классификация семей по душевому доходу Lincome и жилплощади на человека LNS (в логарифмических шкалах).

Дисперсионный анализ (табл. 5.4) показал, что по обоим переменным различие кластеров существенно. Но о статистической значимости переменных говорить бессмысленно, поскольку гипотеза дисперсионного анализа — по сути, независимость групп и "зависимой" переменной, а в данном случае группы сформированы на основе значений "независимых" переменных.

Полезно рассмотреть график рассеяния данных по кластерам (рис. 5.5). В нашем случае, пожалуй, не стоит говорить о выделении "сгущений" точек в признаковом пространстве, скорее, программа нашла разумные границы для описания типов, выделив их в непрерывном двумерном распределении.

Иерархический кластерный анализ

Процедура иерархического кластерного анализа в SPSS предусматривает группировку как объектов (строк матрицы данных), так и переменных (столбцов). Можно считать, что в последнем случае роль объектов играют переменные, а роль переменных — столбцы.

Этот метод реализует иерархический агломеративный алгоритм. Его смысл заключается в следующем. Перед началом кластеризации все объекты считаются отдельными кластерами, которые в ходе алгоритма объединяются. Вначале выбирается пара ближайших кластеров, которые объединяются в один кластер. В результате количество кластеров становится равным N-1. Процедура повторяется, пока все классы не объединятся. На любом этапе объединение можно прервать, получив нужное число кластеров. Таким образом, результат работы алгоритма агрегирования определяют способы вычисления расстояния между объектами и определения близости между кластерами.

Для определения расстояния между парой кластеров могут быть сформулированы различные разумные подходы. С учетом этого в SPSS предусмотрены следующие методы, определяемые на основе расстояний между объектами:

Среднее расстояние между кластерами (Between-groups linkage).Среднее расстояние между всеми объектами пары кластеров с учетом расстояний внутри кластеров(Within-groups linkage).Расстояние между ближайшими соседями — ближайшими объектами кластеров (Nearest neighbor).Расстояние между самыми далекими соседями (Furthest neighbor).Расстояние между центрами кластеров (Centroid clustering).Расстояние между центрами кластеров (Centroid clustering), или центроидный метод. Недостатком этого метода является то, что центр объединенного кластера вычисляется как среднее центров объединяемых кластеров, без учета их объема.Метод медиан — тот же центроидный метод, но центр объединенного кластера вычисляется как среднее всех объектов (Median clustering).Метод Варда (Ward's method). В качестве расстояния между кластерами берется прирост суммы квадратов расстояний объектов до центров кластеров, получаемый в результате их объединения.

Расстояния и меры близости между объектами.
У нас нет возможности сделать полный обзор всех коэффициентов, поэтому остановимся лишь на характерных расстояниях и мерах близости для определенных видов данных.

Меры близости отличаются от расстояний тем, что они тем больше, чем более похожи объекты.

Пусть имеются два объекта X=(X1,…,Xm) и Y=(Y1,…,Ym). Применяя эту запись для объектов, определить основные виды расстояний, используемых процедуре CLUSTER:

Евклидово расстояние

(Euclidian distance).Квадрат евклидова расстояния (Squared Euclidian distance)Эвклидово расстояние и его квадрат целесообразно использовать для анализа количественных данных.

Мера близости — коэффициент корреляции , где и — компоненты стандартизованных векторов X и Y. Эту меру целесообразно использовать для выявления кластеров переменных, а не объектов.Расстояние хи-квадрат получается на основе таблицы сопряженности, составленной из объектов X и Y , которые, предположительно, являются Таблица 5.1. Таблица для пары объектов — строк частот

X	X1	...	Xm	X.
Y	Y1	...	Ym	Y.
X+Y	X1+Y1	...	Xm+Ym	X.+Y.

векторами частот. Здесь рассматриваются ожидаемые значения элементов, равные E(Xi)=X.*(Xi+Yi)/(X.+Y.) и E(Yi)=Y.*(Xi+Yi)/(X.+Y.), а расстояние хи-квадрат имеет вид корня из соответствующего показателя .Расстояние Фи-квадрат является расстоянием хи-квадрат, нормированным "число объектов" в таблице сопряженности, представляемой строками X и Y, т.е. на корень квадратный из N=X.+Y..В иерархичесом кластерном анализе в SPSS также имеется несколько видов расстояний для бинарных данных (векторы X и Y состоят из нулей и единиц, обозначающих наличие или отсутствие определенных свойств объектов). Наиболее естественными из них, по видимому, являются евклидово расстояние и его квадрат.

Иерархическое группирование

Рис. 5.7.  Результаты работы иерархической агломеративной процедуры группирования объектов, представленные в виде дендрограммы

Классификационные процедуры иерархического типа предназначены для получения наглядного представления о стратификационной структуре всей исследуемой совокупности объектов. Эти процедуры основаны на последовательном объединении кластеров (агломеративные процедуры) и на последовательном разбиении (дивизимные процедуры). Наибольшее распространение получили агломеративные процедуры. Рассмотрим последовательность операций в таких процедурах.

На первом шаге все объекты считаются отдельными кластерами. Затем на каждом последующем шаге два ближайших кластера объединяются в один. Каждое объединение уменьшает число кластеров на один так, что в конце концов все объекты объединяются в один кластер. Наиболее подходящее разбиение выбирает чаще всего сам исследователь, которому предоставляется дендрограмма, отображающая результаты группирования объектов на всех шагах алгоритма (рис. 5.7). Могут одновременно также использоваться и математические критерии качества группирования.

Различные варианты определения расстояния между кластерами дают различные варианты иерархических агломеративных процедур. Учитывая специфику подобных процедур, для задания расстояния между классами оказывается достаточным указать порядок пересчета расстояний между классом wl и классом w(m, n) являющимся объединением двух других классов wm и wn по расстояниям qmт = q(wm, wn) и qlт = q(wl, wn) между этими классами. В литературе предлагается следующая общая формула для вычисления расстояния между некоторым классом wl и классом w(m, n):

где

и — числовые коэффициенты, определяющие нацеленность агломеративной процедуры на решение той или иной экстремальной задачи. В частности, полагая и , приходим к расстоянию, измеряемому по принципу ближайшего соседа. Если положить и , то расстояние между двумя классами определится как расстояние между двумя самыми далекими объектами этих классов, то есть это будет расстояние дальнего соседа. И, наконец, выбор коэффициентов соотношения по формулам

приводит к расстоянию qcр между классами, вычисленному как среднее расстояние между всеми парами объектов, один из которых берется из одного класса, а другой из другого.

Использование следующей модификации формулы

дает агломеративный алгоритм, приводящий к минимальному увеличению общей суммы квадратов расстояний между объектами внутри классов на каждом шаге объединения этих классов. В отличие от оптимизационных кластерных алгоритмов предоставляющих исследователю конечный результат группирования объектов, иерархические процедуры позволяют проследить процесс выделения группировок и иллюстрируют соподчиненность кластеров, образующихся на разных шагах какого-либо агломеративного или дивизимного алгоритма. Это стимулирует воображение исследователя и помогает ему привлекать для оценки структуры данных дополнительные формальные и неформальные представления.

Кластерный анализ

Кластерный анализ предназначен для разбиения множества объектов на заданное или неизвестное число классов на основании некоторого математического критерия качества классификации (cluster (англ.) — гроздь, пучок, скопление, группа элементов, характеризуемых каким-либо общим свойством). Критерий качества кластеризации в той или иной мере отражает следующие неформальные требования:

внутри групп объекты должны быть тесно связаны между собой; объекты разных групп должны быть далеки друг от друга; при прочих равных условиях распределения объектов по группам должны быть равномерными.

Требования 1) и 2) выражают стандартную концепцию компактности классов разбиения; требование 3) состоит в том, чтобы критерий не навязывал объединения отдельных групп объектов.

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

Другой важной величиной в кластерном анализе является расстояние между целыми группами объектов. Приведем примеры наиболее распространенных расстояний и мер близости, характеризующих взаимное расположение отдельных групп объектов. Пусть wi — i-я группа (класс, кластер) объектов, Ni — число объектов, образующих группу wi, вектор

— среднее арифметическое объектов, входящих в wi (другими словами, — "центр тяжести" i-й группы), a q ( wl, wm ) — расстояние между группами wl и wm.

Рис. 5.6.  Различные способы определения расстояния между кластерами wl и wm: 1 — по центрам тяжести, 2 — по ближайшим объектам, 3 — по самым далеким объектам

Расстояние ближайшего соседа есть расстояние между ближайшими объектами кластеров:

Расстояние дальнего соседа — расстояние между самыми дальними объектами кластеров:

Расстояние центров тяжести равно расстоянию между центральными точками кластеров:



Обобщенное (по Колмогорову) расстояние между классами, или обобщенное K-расстояние, вычисляется по формуле

В частности, при и при имеем



Выбор той или иной меры расстояния между кластерами влияет, главным образом, на вид выделяемых алгоритмами кластерного анализа геометрических группировок объектов в пространстве признаков. Так, алгоритмы, основанные на расстоянии ближайшего соседа, хорошо работают в случае группировок, имеющих сложную, в частности, цепочечную, структуру. Расстояние дальнего соседа применяется, когда искомые группировки образуют в пространстве признаков шаровидные облака. И промежуточное место занимают алгоритмы, использующие расстояния центров тяжести и средней связи, которые лучше всего работают в случае группировок эллипсоидной формы.

Нацеленность алгоритмов кластерного анализа на определенную структуру группировок объектов в пространстве признаков может приводить к неоптимальным или даже неправильным результатам, если гипотеза о типе группировок неверна. В случае отличия реальных распределений от гипотетических указанные алгоритмы часто "навязывают" данным не присущую им структуру и дезориентируют исследователя. Поэтому экспериментатор, учитывающий данный факт, в условиях априорной неопределенности прибегает к применению батареи алгоритмов кластерного анализа и отдает предпочтение какому-либо выводу на основании комплексной оценки совокупности результатов работы этих алгоритмов.

Алгоритмы кластерного анализа отличаются большим разнообразием. Это могут быть, например, алгоритмы, реализующие полный перебор сочетаний объектов или осуществляющие случайные разбиения множества объектов. В то же время большинство таких алгоритмов состоит из двух этапов. На первом этапе задается начальное (возможно, искусственное или даже произвольное) разбиение множества объектов на классы и определяется некоторый математический критерий качества автоматической классификации.


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

Многообразие алгоритмов кластерного анализа обусловлено также множеством различных критериев, выражающих те или иные аспекты качества автоматического группирования. Простейший критерий качества непосредственно базируется на величине расстояния между кластерами. Однако такой критерий не учитывает "населенность" кластеров — относительную плотность распределения объектов внутри выделяемых группировок. Поэтому другие критерии основываются на вычислении средних расстояний между объектами внутри кластеров. Но наиболее часто применяются критерии в виде отношений показателей "населенности" кластеров к расстоянию между ними. Это, например, может быть отношение суммы межклассовых расстояний к сумме внутриклассовых (между объектами) расстояний или отношение общей дисперсии данных к сумме внутриклассовых дисперсий и дисперсии центров кластеров.

Функционалы качества и конкретные алгоритмы автоматической классификации достаточно полно и подробно рассмотрены в специальной литературе. Эти функционалы и алгоритмы характеризуются различной трудоемкостью и подчас требуют ресурсов высокопроизводительных компьютеров. Разнообразные процедуры кластерного анализа входят в состав практически всех современных пакетов прикладных программ для статистической обработки многомерных данных.

Методы и алгоритмы анализа структуры многомерных данных

Если процедура факторного анализа сжимает в малое число количественных переменных данные, описанные количественными переменными, то кластерный анализ сжимает данные в классификацию объектов. Синонимами термина "кластерный анализ" являются "автоматическая классификация объектов без учителя" и "таксономия".

Если данные понимать как точки в признаковом пространстве, то задача кластерного анализа формулируется как выделение "сгущений точек", разбиение совокупности на однородные подмножества объектов.

При проведении кластерного анализа обычно определяют расстояние на множестве объектов; алгоритмы кластерного анализа формулируют в терминах этих расстояний. Мер близости и расстояний между объектами существует великое множество. Их выбирают в зависимости от цели исследования. В частности, евклидово расстояние лучше использовать для количественных переменных, расстояние хи-квадрат — для исследования частотных таблиц, имеется множество мер для бинарных переменных.

Кластерный анализ является описательной процедурой, он не позволяет сделать никаких статистических выводов, но дает возможность провести своеобразную разведку — изучить "структуру совокупности".

Стандартизация

Непосредственное использование переменных в анализе может привести к тому, что классификацию будут определять переменные, имеющие наибольший разброс значений. Поэтому применяются следующие виды стандартизации:

Z-шкалы (Z-Scores). Из значений переменных вычитается их среднее, и эти значения делятся на стандартное отклонение.Разброс от -1 до 1. Линейным преобразованием переменных добиваются разброса значений от -1 до 1.Разброс от 0 до 1. Линейным преобразованием переменных добиваются разброса значений от 0 до 1. Максимум 1. Значения переменных делятся на их максимум.Среднее 1. Значения переменных делятся на их среднее.Стандартное отклонение 1. Значения переменных делятся на стандартное отклонение.Кроме того, возможны преобразования самих расстояний, в частности, можно расстояния заменить их абсолютными значениями, это актуально для коэффициентов корреляции. Можно также все расстояния преобразовать так, чтобы они изменялись от 0 до 1.

Таким образом, работа с кластерным анализом может превратиться в увлекательную игру, связанную с подбором метода агрегирования, расстояния и стандартизации переменных с целью получения наиболее интерпретируемого результата. Желательно только, чтобы это не стало самоцелью и исследователь получил действительно необходимые содержательные сведения о структуре данных.

Процесс агрегирования данных может быть представлен графически деревом объединения кластеров (Dendrogramm) либо "сосульковой" диаграммой (Icicle).

Рис. 5.2.  Дендрограмма классификации

Но подробнее о процессе кластеризации можно узнать по протоколу объединения кластеров (Schedule).

Пример иерархического кластерного анализа. Проведем кластерный анализ по полученным нами ранее факторам на агрегированном файле Курильского опроса:

Рис. 5.3.  Классификация городов

CLUSTER fac1_1 fac2_1 /METHOD BAVERAGE /MEASURE= SEUCLID /ID=name /PRINT SCHEDULE CLUSTER(3,5) /PLOT DENDROGRAM .

В команде указаны переменные fac1_1 fac2_1 для кластеризации. По умолчанию расстояние между кластерами определяется по среднему расстоянию между объектами (METHOD BAVERAGE), а расстояние между объектами — как квадрат евклидова (MEASURE= SEUCLID).
Кроме того, распечатывается протокол (PRINT SCHEDULE), в качестве переменных выводятся классификации из 3, 4, 5 кластеров (CLUSTER(3,5)) и строится дендрограмма (PLOT DENDROGRAM).

Разрез дерева агрегирования (рис. 5.2) вертикальной чертой на четыре части дал два кластера, состоящих из уникальных по своим характеристикам городов Александровск-Сахалинский и Черемхово; кластер из 5 городов (Оха, Елизово, Южно-Сахалинск, Хабаровск, Курильск); еще один кластер из 14 городов составили последний кластер.

Естественность такой классификации демонстрирует полученное поле рассеяния данных (рис.5.3).

Таблица 5.2. Протокол объединения кластеровCluster CombinedCoefficientsStage Cluster First AppearsNext StageStageCluster 1Cluster 2Cluster 1Cluster 2

1	5	20	0.0115	0	0	2
2	5	11	0.0175	1	0	3
3	5	19	0.0464	2	0	11
4	6	12	0.0510	0	0	8
5	3	16	0.0549	0	0	9
6	13	21	0.0808	0	0	10
7	10	14	0.1082	0	0	14
8	6	15	0.1349	4	0	11
9	3	8	0.1538	5	0	13
10	1	13	0.2818	0	6	12
11	5	6	0.4560	3	8	13
12	1	2	0.5768	10	0	16
13	3	5	0.5861	9	11	16
14	10	17	0.6130	7	0	17
15	7	18	0.8098	0	0	17
16	1	3	1.5406	12	13	18
17	7	10	2.5726	15	14	19
18	1	4	3.5613	16	0	19
19	1	7	5.2217	18	17	20
20	1	9	14.9146	19	0	0

Процесс объединения подробно показан в протоколе объединения (табл. 5.2). В нем указаны стадии объединения, объединяемые кластеры (после объединения кластер принимает минимальный номер из номеров объединяемых кластеров). Далее следует расстояние между кластерами, номер стадии, на которой кластеры ранее уже участвовали в объединении; затем следующая стадия, где произойдет объединение с другим кластером.

На практике интерпретация кластеров требует достаточно серьезной работы, изучения разнообразных характеристик объектов для точного описания типов объектов, которые составляют тот или иной класс.

Алгоритмические модели

Алгоритмические модели основаны на понятии алгоритма. Исторически первые точные определения алгоритма, возникшие в 30-х годах, были связаны с понятием вычислимости. С тех пор было предложено множество, как выяснилось, эквивалентных определений алгоритма.

В практике программирования алгоритмы принято описывать с помощью алгоритмических языков программирования. Широко используются также разного рода блок-схемы алгоритмов, позволяющие представить алгоритмы в наглядном и общедоступном виде, не привлекая в тоже время сложных конструкций из конкретных языков программирования.

Чтобы оценить возможности использования алгоритмов для представления неформальных процедур, рассмотрим простую задачу.

ЗАДАЧА. Описать процедуру, реализующую преобразование из именительного падежа в родительный для существительных следующих типов: ДОМ, МАМА, ВИЛКА, КИНО, НОЧЬ, ТОКАРЬ, КИЛЬ.

Решение 1 указано на рис. 6.1 в виде блок-схемы соответствующего алгоритма.

Рис. 6.1.  Решение 1. Алгоритм

С точки зрения программирования на алгоритмических языках достоинства подобного представления очевидны — эта блок-схема без затруднений переводится в текст программы, например, на языке Ассемблер или С++. Однако само составление подобной блок-схемы при появлении существительных новых типов становится, очевидно, все более и более утомительным занятием. Для иллюстрации этого предположим, что дана

ДОПОЛНИТЕЛЬНАЯ ЗАДАЧА. Расширить алгоритм, представленный на рис. 1.1, на слова ВАСЯ, ВРЕМЯ, АКЦИЯ, ЗАДАЧА.

Разумеется, программист без особого труда составит соответствующую блок-схему алгоритма. И все же, если учесть, что подобные изменения и расширения алгоритма при программировании неформальных процедур происходят многократно (реальная сложность неформальной процедуры как раз и проявляется в практической невозможности предусмотреть заранее все случаи), следует признать, что, вполне правильное в статике, решение 1 в динамике неудачно!

Язык Рефал

Название языка происходит от "РЕкурсивных Функций АЛгоритмический язык". Нас будут также интересовать соображения, которые привели к построению этого языка — эти соображения имеют, на наш взгляд, весьма общий характер и полезны для лучшего понимания причин возникновения продукционного подхода в программировании.

Разработчики языка Рефал делят алгоритмические языки на две группы. Первую группу образуют языки, которые называются языками операторного, или процедурного типа. Элементарными единицами программы являются здесь операторы, т.е. приказы, выполнение которых сводится к четко определенному изменению четко определенной части памяти машины. Типичным представителем этой группы является язык машины Поста. Сюда же относятся машинные языки конретных ЭВМ, а также массовые языки программирования типа Фортран, Алгол, ПЛ/1.

Языки второй группы называются языками сентенциального, или декларативного типа (sentence — высказывание, предложение). Программа на таком языке представляется в виде набора предложений (соотношений, правил, формул), которые машина, понимающая данный язык, умеет каким-то образом применять к обрабатываемой информации. Простейшим примером сентенциального языка, созданного с теоретическими целями, является язык нормальных алгоритмов Маркова.

Можно назвать прообразы указанных типов алгоритмических языков в естественных языках. Для операторных языков это повелительное наклонение (императив, приказание), для сентенциальных – изъявительное наклонение (описание, повествование). Обращаясь к естественному языку, нетрудно заметить, что "изъявительное наклонение является несравненно более распространенным и образует, в сущности, основу языка, в то время как повелительное наклонение предстает в виде некоторой специальной модификации". Таким образом, можно сделать вывод о том, что "относительный вес изъявительного наклонения является мерой развитости языка".

Язык РЕФАЛ является сентенциальным в своей основе, а вся информация в этом языке представляется в виде правил конкретизации. Каждое правило записывается в виде предложения, которое представляет собой продукцию с определенными синтаксисом и семантикой. Предложения в Рефал-программе отделяются друг от друга знаком § (параграф).

Каждое правило конкретизации определяет раскрытие смысла некоторого понятия через более элементарные. Операцию конкретизации можно также определить как переход от имени к значению. Введем два знака: k и

, которые будем называть конкретизационными скобками, и которые будут содержать объект, подлежащий конкретизации. Так, если х — некоторая переменная, то (конкретизация х) будет изображать значение этой величины. Другой пример: объект при правильном определении операции сложения рано или поздно будет заменен на объект 35.

Выполнение конкретизации — переход от имени к значению — объявляется основной и, по существу, единственной операцией в языке Рефал. Эту операцию будет выполнять Рефал-машина (имеется в виду машина на логическом уровне, имитируемая соответствующим транслятором на универсальной ЭВМ; возможно, разумеется, и построение реальной "физической" Рефал-машины).

Поскольку правило конкретизации есть указание для замены одного объекта (слова в некотором алфавите) на другой, предложения языка Рефал должны состоять из левой части (заменяемый объект) и правой части (объект, заменяющий левую часть). Для разделения правой и левой части мы будем использовать знак стрелки "

".

Пример. Предложение, выражающее тот факт, что значение переменной Х есть 137, записывается в виде

.

Между знаком § и первым знаком k можно вставлять последовательность знаков, которая будет служить номером предложения, или комментарием к нему, например:

. (ф. 1)

Опишем теперь структуру Рефал-машины, которая, используя предложения Рефал-программы, будет выполнять конкретизации. Будем считать, что объектом обработки является некоторое выражение (слово), которое находится в поле зрения машины. Работа машины осуществляется по шагам, каждый из которых представляет выполнение одного акта, конкретизации.

Пусть программа машины состоит из единственного предложения (ф. 1), а в поле зрения находится выражение

. Тогда за один шаг машина заменит содержимое поля зрения на 137, после чего она остановится, т. к. знаков конкретизации больше нет и, следовательно, делать ей больше нечего.

Так как Рефал-программа содержит, вообще говоря, набор (последовательность) предложений, может оказаться, что для выполнения данной конкретизации пригодно не одно, а несколько предложений. Например, в поле памяти, кроме (ф. 1), может находиться еще предложение

.

Неоднозначность, которая отсюда может возникнуть, устраняется так же, как это принято в нормальных алгоритмах Маркова (читатель, видимо, уже заметил, что Рефал-машина следует идеологии этих алгоритмов): машина просматривает предложения в том порядке, в котором они расположены в Рефал-программе, и применяет первое из них, которое окажется подходящим.

Поле зрения может содержать сколько угодно конкретизационных скобок, причем они могут быть как угодно вложены друг в друга. В этом случае Рефал-машина начинает процесс конкретизации с первого из знаков k, в области действия которого (т.е. в последовательности знаков до парной скобки

) нет ни одного знака k. Выражение, находящееся в области этого знака k, последовательно сравнивается с левыми частями предложений Рефал-программы. Найдя подходящее предложение, машина выполняет в поле зрения необходимую замену и переходит к следующему шагу конкретизации.

Пример. Пусть Рефал-программа имеет вид

,

а поле зрения содержит выражение

.

На первом шаге замене подлежит подвыражение

— получим в поле зрения . Теперь в первую очередь конкретизируется — получим в результате применения третьего предложения и на последнем шаге получим 139, не содержащее символов k. (Разумеется для реального сложения используются соответствующие встроенные функции, а этот пример — лишь простейшая иллюстрация принципов работы машины).

Чтобы иметь возможность представлять обобщенные предложения, используются три типа переменных: е — для представления выражений; t — для термов; s — для символов. В простейшем случае переменные записываются в виде указателя типа (е, t, s) и индекса; например, е1, e2 — переменные, пробегающие в качестве значений выражения. Выражением в языке Рефал называется последовательность знаков, правильно построенная в соответствии с синтаксисом языка Рефал. Терм языка Рефал — это либо символ, либо выражение в круглых или конкретизационных скобках. Выражения строятся из термов.

Пример. Предположим, требуется написать программу, которая выполняет раскрытие скобок в алгебраических выражениях, построенных из букв с помощью скобок, знаков сложения "+" и умножения"*". Рассмотрим процесс написания такой программы. Если некоторое выражение е имеет вид е1 + e1, где е1, e1 — выражения, то для раскрытия скобок надо: раскрыть скобки в e1, раскрыть скобки в е2, полученные результаты сложить. Эту мысль в компактном, но в то же время и наглядном виде выражает предложение:

Если же выражение е имеет вид e1 * e2, то, вообще говоря, необходимо учитывать две возможности:

хотя бы один из сомножителей есть сумма (например, е = (А + В) *С),ни одно из выражений е1 или е2 не представимо в виде суммы (например, е = (А * В) * (С * Л)).

В первом случае надо описать законы дистрибутивности:

,

,

.

Во втором случае по аналогии со сложением имеем

.

Наконец, осталось выразить возможность "снятия внешних скобок" и условие "терминальности" символов, что определяют предложения:

,

(буквы не подлежат конкретизации).

Приведенные семь предложений § 2.1 — § 2.7 решают задачу. Рассмотрим как эта программа обрабатывает выражение

.

Последовательно получим в результате работы программы (для удобства слева указываем номер правила, которое непосредственно привело к данному выражению):

,

,

.

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

,

,

§ 2.7 А * С + ... .

После аналогичной обработки остальных слагаемых получим искомое выражение

А*С+D*С+А * D + В * D.

Если на вход поступит выражение

,

то получим последовательно:

,

,

,

§2.1, 2.7 A + B + С.

Обратите внимание, что если расположить правило § 2.5 перед правилами § 2.2 и § 2.3, то мы придем к абсурду! Например, выражение А *(В+С) будет приведено к виду: А *В + С.

Логический вывод

Важность логического вывода становится очевидной уже при рассмотрении простейших информационно-логических процедур. Предположим, что некоторая база данных содержит сведения об отношениях "х — ОТЕЦ у" и "х — МАТЬ у". Чтобы обработать запросы типа:

ИВАНОВ А.И. — ДЕД ПЕТРОВА В.А.?

ПЕТРОВ В.А. — ВНУК ИВАНОВА А.И.?

необходимо либо ввести в базу данных также и сведения об отношениях "х — ДЕД у" и "х — ВНУК у", либо объяснить системе, как из отношений ОТЕЦ, МАТЬ извлечь искомую информацию. Реализация первой возможности связана с неограниченным ростом избыточности базы данных. Вторая возможность при традиционном алгоритмическом подходе требует написания все новых и новых программ для реализации новых типов запросов.

Логический вывод позволяет расширять возможности "общения" наиболее просто и наглядно. Так, для приведенных типов запросов системе достаточно будет сообщить три правила:

х—ДЕД у если х—ОТЕЦ а и а—РОДИТЕЛЬ у;х—РОДИТЕЛЬ у если х—ОТЕЦ у или х—МАТЬ у;х—ВНУК у если у—ДЕД х.

Эти правила содержат естественные и очевидные определения понятий ДЕД, РОДИТЕЛЬ, ВНУК. Поясним, в чем состоит логический вывод для запроса "А—ДЕД В?" в предположении, что в базе данных имеются факты: А—ОТЕЦ Б и Б—МАТЬ В. При этом для упрощения опустим тонкости, связанные с падежными окончаниями. Пользуясь определением 1, система придет к необходимости проверки существования такого индивидуума а, что факты А—ОТЕЦ а и а—РОДИТЕЛЬ В истинны. Если такой а существует, то А—ДЕД В, если не существует такого а, то А не является дедом В.

Неформальные процедуры

Говоря о неформальных процедурах, мы обычно хорошо понимаем, что имеется в виду, и без затруднений можем привести примеры таких процедур, связанных с пониманием текстов естественного языка, переводом с одного естественного языка на другой, информационным поиском по смыслу и т. д.

Трудности возникают при попытке точного определения подобных процедур. Так, если рассматривать неформальные процедуры всего лишь как абстрактные функции, которые для каждого значения аргумента "выдают" некоторое значение, то категория неформальности вообще исчезает из рассмотрения.

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

Продукционные модели

В подобных случаях для обеспечения динамичности процессов модификации программ используются те или иные варианты таблиц решений. С учетом этого для исходной задачи более приемлемо решение 2.

Таблица 6.1. Решение 2СитуацияДействиеСитуацияДействие

КИНО	КИНО	-Ь	-И
-ча	-чи	-ие	-ия
-КА	-КИ	-мя	-мени
-А	-Ы	-я	-и
-АРЬ	-АРЯ	-	-А
-Ь & М:хЬ	-Я

Соответствующая таблица решений содержит две графы: слева приведены описания ситуаций, справа — соответствующие действия. Предполагается, что программист разработал интерпретирующую программу для подобных таблиц. Эта программа работает следующим образом. Для конкретного входного слова, пусть это будет для примера слово РОЗА, осуществляется последовательный просмотр ситуаций, указанных в таблице, и сравнение их со входным словом. Если слово соответствует некоторой ситуации, то выполняется действие, указанное для этой ситуации.

Для слова РОЗА будет обнаружено соответствие с ситуацией "-А". В результате выполнения действия "-Ы" будет получено выходное слово РОЗЫ.

Теперь значительно упрощается расширение на новые классы слов — необходимо лишь обеспечить внесение вставок на нужное место в таблице решений.

Таблицы решений представляют собой частный случай так называемых продукционных систем. В этих системах правила вычислений представляются в виде продукций. Продукции представляют собой операторы специального вида и состоят из двух основных частей, для краткости называемых обычно "ситуация — действие".

"Ситуация" содержит описание ситуации, в которой применима продукция. Это описание задается в виде условий, называемых посылками продукции. "Действие" — это набор инструкций, подлежащих выполнению в случае применимости продукции.

Продукционные системы с исключениями

Если отношение "правило—исключение" встроено в систему, она сама может понять, что преобразование ПАЛКА -> ПАЛКЫ незаконно. При этом система должна руководствоваться простым принципом: если применимо исключение, общее правило запрещено. Соответствующие системы будем называть системами с исключениями.

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

исключение "вытесняет" общее правило;при пересечении разрешены оба правила.

Разумеется, возможны ситуации, когда необходимо поступать наоборот:

исключение не запрещает общего правила;при пересечении одно из правил запрещено.

Пусть дано, например, общее правило

и его исключение . Таким образом, для произвольного слова необходима реакция р1. Для слова же, начинающегося с буквы А, исполняется реакция р2 — по умолчанию для таких слов реакция р1 незаконна.

Предположим, однако, что по условию конкретной задачи для слов, начинающихся с А, реакция р1 также допустима. В этом случае введение нового правила

снимает запрет на реакцию р1 в ситуации Ах.

Аналогичный способ годится для пересечения правил.

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

При развитии продукционной системы с исключениями программист сосредотачивает свое внимание на выявлении новых правил и на обобщении уже имеющихся. Аппарат исключений освобождает программиста от решения трудоемких вопросов согласования правил — распознавание и интерпретация исключений осуществляется автоматически.

Режим возвратов

Таблица решений, приведенная в Таблице 6.1, иллюстрирует так называемую безвозвратную процедуру. В этом случае на каждом шаге выбирается единственное решение — так, для слова РОЗА таким решением будет РОЗЫ, — проблема выбора решения не возникает. В общем случае неформальные процедуры являются многозначными, а правильность конкретного выбора, сделанного на некотором шаге, проверяется на следующих шагах. При этом используется так называемый режим возвратов.

МАТЬ ——————> ЛЮБИТ ——————> ? что делать? кого? МАТЬ <—————— ЛЮБИТ <—————— ? кого? что делать?

Пусть предложение начинается со слов МАТЬ ЛЮБИТ ... . Проанализировав эти слова в первоначальном предположении именительного падежа для слова МАТЬ, система вправе построить структуру, представленную в случае 1). Если следующее слово после слова ЛЮБИТ представляет собой существительное в винительном падеже, например, вся фраза имеет вид МАТЬ ЛЮБИТ СЫНА, то эта структура является окончательной. Если же фраза имеет вид МАТЬ ЛЮБИТ СЫН, то возникает противоречие или, как говорят, сигнал неуспеха — очередное слово СЫН противоречит ожиданию прямого дополнения. В этом случае система должна вернуться на ближайший из предыдущих шагов, где можно принять другую альтернативу анализа. В данном примере это шаг анализа слова МАТЬ — система должна принять теперь альтернативу винительного падежа для этого слова. Далее будет построена структура, указанная в случае 2).

Тривиальность рассмотренного примера убеждает в необходимости режима возвратов при реализации неформальных процедур.

Зависимость продукций

Продукционные системы, содержащие аппарат логического вывода, отличает высокая степень общности правил обработки данных. Однако именно эта общность приводит к ухудшению динамических свойств соответствующих продукционных программ, к трудностям их модификации и развития. Чтобы понять, в чем тут причина, обратимся снова к Таблице 6. Пока эта таблица содержит несколько строк, не представляет особого труда установление правильного порядка их следования, но если учесть, что реальное количество продукций в подобных задачах исчисляется сотнями и более, трудоемкость их правильного взаимного расположения становится очевидной. Практически, при программировании неформальных "человеческих" процедур, подобные таблицы можно вручную создавать и сопровождать для нескольких десятков продукций, максимум — для 100-200. Продукции зависимы, и за правильное выявление этой зависимости отвечает программист. Новые продукции необходимо вручную вставлять на нужное место.

Мы могли бы использовать в таблице решений только конкретные факты, например правила ДОМ -> ДОМА, МАМА -> МАМЫ и т. д., и динамичность соответствующей таблицы решений была бы восстановлена — подобные правила можно было бы вводить в произвольном порядке! Однако цена подобной "динамичности" окажется непомерно высокой — полный отказ от обобщенных правил.

Желательно восстановить динамичность продукционно-логических систем, сохранив при этом в полном объеме возможность использования обобщенных правил. Продукционная система должна взять на себя функции распознавания и интерпретации приоритета продукций — программист должен только описывать ситуации и соответствующие им действия.

---

---