Бессмертный И.А. Искусственный интеллект
Подождите немного. Документ загружается.
61
не используются для подбора параметров сети, они могут служить критерием
качества обучения. По аналогии с обучением человека тестирование можно
уподобить экзамену.
В качестве примера рассмотрим задачу оптического распознавания
текстов. Пусть на вход сети в качестве входных сигналов подается матрица
точек выделенного фрагмента изображения, соответствующая распознаваемому
символу (рис.5.7). Пусть на вход сети
подается матрица точек распознаваемого
знака. На выходе формируются сигналы, соответствующие распознанному
знаку. Обучение сети заключается в многократном «предъявлении» сети
разных вариантов начертания символов вместе с готовыми «ответами».
Рис.5.7. Нейронная сеть в задаче распознавания символов
Заметим, что сеть не пытается запомнить все возможные варианты
начертания каждого символа, а лишь формирует выходной сигнал
Y
j
= f(X
1
, X
2
,…X
n
)
как функцию от входных переменных. Заметим, что такой подход к
распознаванию текстов обладает существенным преимуществом перед прочими
в быстродействии. Так же и человек: чтобы прочитать текст, не спрашивает
названия шрифта, и не ищет в памяти все возможные начертания символов.
Ассоциации в мозгу устанавливаются мгновенно.
Задача обучения сети имеет огромную размерность.
Так, для обучения
сети, состоящей всего из 10 нейронов, в каждом из которых по 3 синапса,
необходимо подобрать значения по меньшей мере 40 параметров (30 значений
W
i
– синаптических весов, и 10 параметров функций активации λ
i
). Если
каждый из параметров подбирать с дискретностью 1/100, то общее число
прогонов сети на множестве тренировочных данных составит 100
40
. Очевидно,
что такая задача не под силу даже суперкомпьютерам.
Данная задача удовлетворительно решается с помощью алгоритма
обратного распространения (back propagation), который заключается в
следующем.
Вначале все параметры сети устанавливаются произвольно.
1. Через сеть прогоняются тренировочные данные, и вычисляется
суммарная функция ошибки E = sum(E
i
2
), где E
i
= Y
i
- y
i
, Y
i
–
вычисленное значений выходной величины, y
i
– ожидаемое значение.
Нейронная сеть
ASCII код
символа
62
2. Вычисляется значение производных функции ошибки по каждому па-
раметру, а на их основе – расчет поправок к параметрам нейронной сети.
3. Параметры сети корректируются на величину поправок, после чего шаги
2 и 3 повторяется с начала до тех пор, пока функция ошибки не снизится
до заданного уровня.
Несмотря на простоту, данный алгоритм является весьма трудоемким, и
его ускорение представляет собой актуальную задачу.
Если в результате обучения не был получен удовлетворительный
результат, то необходимо изменить структуру сети. Это может быть сделано
вручную, либо структура может выбираться из заранее созданного набора
(библиотеки структур). Программные продукты, поддерживающие такие
решения, существуют.
Но наиболее удачным следует признать подход, при
котором структура сети формируется автоматически. Примером может служить
нейросеть NGO компании BioComp Systems Inc. (www.biocompsystems.com)
.
Данный подход заключается в применении к этой задаче генетических
алгоритмов. Дело в том, что в процессе обучения сети выявляются «сильные»
нейроны и связи между ними (чувствительные к изменению параметров) и
«слабые» (параметры которых можно менять произвольно без существенного
влияния на конечный результат). Используя эти данные, можно управлять
популяцией нейронов. Слабые
нейроны и синапсы должны отмирать, а для
развития структуры, а также чтобы предотвратить всеобщее «вымирание», сеть
подвергается «мутации»: в нее случайным образом или другим способом,
например, для усиления «сильных» нейронов добавляются новые нейроны и
синаптические связи. Таким образом, через множество поколений, количество
которых может достигать десятков тысяч, сеть будет иметь
оптимальную
структуру.
В связи с этим может возникнуть вопрос: а зачем тратить такое количество
времени на оптимизацию структуры сети, если обучение сети максимальной
размерности с полным набором связей займет заведомо меньшее время? К тому
же ранее было сказано, что быстродействие обученной нейронной сети
достаточно велико.
Причины здесь две. Первая заключается в
том, что зачастую обученная
сеть в дальнейшем реализуется на другой платформе, в частности, на
аппаратном уровне. Вторая причина – оптимизация часто приводит к
существенному снижению количества входных переменных за счет
исключения избыточных, не влияющих на конечный результат. Этот факт
придает нейросетям качественно новое свойство: можно не заботиться о том,
какие входные
данные являются важными, а какие нет – в процессе обучения
лишние будут отброшены. В статистике подобную функцию выполняют
пошаговая линейная регрессия, дисперсионный и факторный анализ.
Например, мы пытаемся использовать нейросеть для предсказания курса
доллара. В качестве исходных данных мы можем подставить поведение этого
курса в течение нескольких лет (кстати, такой способ предсказания
величин на
63
основе только их поведения в прошлом называется «технический анализ»),
экономические индикаторы и индексы (Dow Jones, NASDAQ, потребительские
цены), а также любые другие, вплоть до данных метеонаблюдений. Если на
всех этих данных будет получена нейросеть, дающая хорошие прогнозы, то
пользоваться ею будет довольно утомительно, а иногда и дорого. При этом
выявление значимых параметров само по
себе представляет ценный результат.
Если окажется, что на курс доллара оказывает влияние температура воздуха,
можно исследовать природу данного феномена. Мне могут возразить, что
такую связь можно обнаружить, сравнивая графики температуры воздуха и
курса доллара. Однако, прямое сравнение позволяет обнаружить, главным
образом, линейную зависимость, к тому же здесь в работу включается
интеллект человека.
5.3. Особенности использования нейронных сетей
Полная автоматизация выбора топологии и параметров нейросети,
предоставляемая пакетами программ, подобным NGO, может создать иллюзию
того, что можно совсем не управлять процессом моделирования с помощью
нейронной сети. Однако, применение нейронных сетей, как и статистических
методов анализа, является творческим процессом, требующим понимания
принципов работы данного инструмента.
Следствиями неправильного
построения и обучения нейросети, в основном, являются обобщение или
переобучение. Обобщением называется излишнее упрощение сети, при
котором она не воспроизводит мелкие зависимости. Например, обобщение сети
для прогнозирования погоды приведет к тому, что она будет выдавать среднюю
температуру для данного сезона. Крайняя степень обобщения в этой задаче –
среднегодовая температура. Естественно
, пользы от такого прогноза будет
немного. Переобучение – это другая крайность, при которой нейронная сеть
имеет излишне сложную структуру и в процессе обучения слишком тщательно
подгоняет результаты к желаемым. Как результат, на данных, не участвующих
в обучении, сеть показывает худшие результаты. Признак переобучения –
существенная разница погрешностей на этапе обучения и на
этапе
тестирования. Еще одна опасность слишком длительного обучения в сочетании
с генетической модификацией топологии сети – обесценивание результатов
тестирования. Если при однократной процедуре обучения данные тестирования
заведомо не участвуют в процессе обучения, то при модификациях сети данные
тестирования используются для отбраковки неудачных топологий и, тем
самым, оказывают влияние на конечную сеть.
Существенный
недостаток нейронных сетей — неспособность к
экстраполяции. Иными словами, нейросеть, обученная в некотором диапазоне
значений входных переменных, не в состоянии прогнозировать за пределами
этого диапазона. На практике это обычно выражается в том, что за пределами
области обучения выходная переменная не меняется, как показано на рис.5.8.
Если сеть обучена в диапазоне -0,5 < X < 0,5, то
за пределами этого диапазона
64
график выходной функции обычно лежит горизонтально.
Рис. 5.8. Поведение нейронной сети вне области обучения
Несмотря на то, что нейронная сеть берет на себя любое, даже самое
сложное преобразование входных переменных в выходные, предварительная
обработка данных обычно не лишена смысла. Так, в случае прогнозирования на
фондовом рынке, вероятно, целесообразным является переход от
абсолютных
значений котировок к относительным, т.е. к приращениям от одного
наблюдения к другому. В таком случае для нейронной сети безразлично,
колебания вокруг каких уровней использовать для обучения, если нас
интересует лишь направление изменения котировок, вверх или вниз. В
абсолютных же значениях сеть, обученная на колебаниях котировок вокруг
значений 1000 или 5000
абсолютно бесполезна для прогнозирования в
окрестности цифры 3000.
Факт
Прогноз
65
6. Экспертные системы
Экспертная система – это программа, которая в состоянии заменить собой
человека-эксперта в его профессиональной деятельности. Структурно
экспертная система состоит из базы знаний, машины вывода и
пользовательского интерфейса.
База знаний имеет тот же смысл, что и в Прологе, т.е. состоит из фактов и
правил. Машина вывода (inference engine) обращается к базе знаний
(knowledge base) и преобразует запрос пользователя в ответ, задавая ему при
необходимости вопросы, используя пользовательский интерфейс. Такая
структура позволяет развивать экспертные системы, добавляя в нее новые
знания, и при этом не требуется переписывать программу. Пустая экспертная
система (без базы знаний) называется оболочкой (expert system shell) и может
использоваться для многих предметных областей.
Создание экспертной
системы заключается в формализации, т.е.
преобразования знаний эксперта в форму, которая требуется для оболочки
экспертной системы. Иными словами, требуется человек-эксперт, который
является носителем знаний и в состоянии эти знания сформулировать для
занесения в базу знаний. Этот факт является определяющим для выбора
экспертной системы в качестве инструмента решения задачи.
Человек-эксперт
далеко не всегда в состоянии изложить свои знания в том виде, как этого
требует формат базы знаний. В таких случаях вступает в действие инженер по
знаниям (knowledge engineer), который является «переводчиком» между
экспертом и базой знаний.
Рассмотрим работу экспертной системы на простом примере. Пусть наша
база знаний предназначена для классификации животных
. Предположим, что
мы увидели животное и хотим ее идентифицировать. Пусть база знаний
содержит всего двух животных, зебру и леопарда. Правила для описания этих
животных (не в синтаксисе конкретной базы знаний, а в вольном переводе на
русский язык) выглядят следующим образом:
«ЕСЛИ животное относится к классу млекопитающих И животное
относится к
виду хищников И животное имеет черные пятна, ТО животное
– леопард»
«ЕСЛИ животное относится к классу млекопитающих И животное
относится к виду травоядных И животное имеет черные и белые
поперечные полосы, ТО животное – зебра»
Экспертная система начинает проверять гипотезы в порядке их
расположения в базе знаний, в данном случае, начиная
с леопарда. Чтобы
установить истинность этой гипотезы, экспертная система должна сначала
установить, относится ли животное к классу млекопитающих. Для этого она
должна найти в базе знаний правило:
«ЕСЛИ женская особь животного имеет молочные железы, ТО
животное относится к классу млекопитающих».
66
Теперь, чтобы установить принадлежность животного к млекопитающим,
предстоит выяснить, имеет ли оно молочные железы. Если соответствующего
правила в базе знаний нет, то пользователь должен сам дать ответ на этот
вопрос. В этом случае экспертная система должна задать вопрос: «ВЕРНО ЛИ,
ЧТО женская особь животного имеет молочные железы?»
Если пользователь ответит
утвердительно, то факт «животное относится к
классу млекопитающих» считается установленным (для простоты не будем
рассматривать ситуацию, когда мы встретили самца). После этого правило для
определения леопарда требует установить, является ли животное хищником.
Установить это факт достоверно можно только будучи съеденным, поэтому, из
гуманных соображений, в базу знаний помещено правило: «ЕСЛИ
животное
имеет когти ИЛИ животное имеет клыки ТО животное относится к виду
хищников»
Пользователь не увидел ни клыков, ни когтей, а напротив, заметил копыта.
Следовательно, гипотеза «леопард» отвергается, и экспертная система
переходит к проверке следующей гипотезы «зебра». Факт «млекопитающее»
уже установлен, и теперь нужно установить, относится ли животное к виду
травоядных
. Соответствующее правило выглядит следующим образом:
«ЕСЛИ животное имеет рога ИЛИ животное имеет копыта, ТО животное
относится к виду травоядных».
Экспертная система сначала задаст вопрос: «ВЕРНО ЛИ, ЧТО животное имеет
рога?»
Пользователь отвечает отрицательно, а поскольку условия в данном правиле
связаны операцией ИЛИ, задается следующий вопрос: «ВЕРНО ЛИ, ЧТО
животное
имеет копыта?»
Пользователь отвечает утвердительно, следовательно, факт «животное
относится к виду травоядных» считается установленным. Для проверки
гипотезы «зебра» остается проверить последнее условие: «ВЕРНО ЛИ, ЧТО
животное имеет черные и белые поперечные полосы?»
Если полосы имеются, то гипотеза «зебра» подтверждается, а задача,
поставленная перед экспертной системой, считается выполненной. Рис.6.1
содержит фрагмент простой
экспертной системы, реализованной в среде
VISIRULE, разработанной компанией LPA (http://lpa.co.uk
).
67
Рис.6.1. Пример представления правил
Основное требование к проектированию экспертных систем заключается в
том, что пользователю должны задаваться такие вопросы, на которые он в
состоянии ответить. Иными словами, экспертная система преобразует знания
пользователя в знания эксперта. В приведенном выше примере идентификации
животных явно неудачным вопросом является вопрос о молочных железах
(особенно
, если речь идет о случайно встреченном нами леопарде). Вместо него
следует использовать правило:
«ЕСЛИ животное имеет волосяные покровы ТО животное относится к
классу млекопитающих»
Другим важным свойством экспертной системы является способность
объяснить, как был получен тот или другой вывод, что является лучшим
подтверждением истинности полученного вывода. Если вспомнить рассказы А
.
Конан-Дойла, то нас, как и доктора Ватсона вывод вначале любой Шерлока
Холмса кажется парадоксальным и выдуманным, но после объяснения, как этот
вывод был сделан, мы удивляемся, что сами об этом не догадались.
Экспертные системы используются в самых различных областях знаний, в
том числе в медицине (диагностика и лечение), геологоразведке (
определение
перспективности месторождений), химии (прогнозирование свойств
органических соединений). В последнее время экспертные системы активно
используются в Интернет-торговле для помощи покупателям в выборе товара.
Наиболее известной является экспертная система ГУРУ на Яндексе
(http://market.yandex.ru/guru-categories.xml
), которая заменяет
квалифицированного продавца-консультанта по самому широкому перечню
товаров.
68
7. Семантические сети
7.1. Определение
Семантическая сеть - структура для представления знаний с помощью
графа, в виде узлов, соединенных дугами. Узлы соответствуют понятиям, а
дуги – отношениям между ними. Элементом семантической сети в простейшем
случае является триплет следующего вида:
Одно и то же понятие может присутствовать в нескольких триплетах, что и
обуславливает сетевую структуру. Основным свойством семантических
отношений является арность, т.е. количество аргументов. Выше приведен
пример бинарного отношения, т.е. отношения с арностью 2. Если все
отношения в сети однотипные, то сеть называется однородной. Пример
однородной сети – классификация биологических
видов. В неоднородной сети
количество типов отношений больше одного.
Основная цель применения семантических сетей для представления знаний
– обеспечение независимости от языка, а также устранение неточностей и
двусмысленностей, свойственных естественным языкам. Естественный язык –
как живой организм, развивается и эволюционирует в сторону
совершенствования основной своей цели – обеспечения понимания участников
разговора. Однако, в
силу природной лени носителей языка, эта оптимизация
зачастую сводится к предельному упрощению конструкций, в результате чего
смысл отдельной фразы выявить можно только из контекстного окружения.
Хрестоматийный пример даже не двусмысленности, а «трехсмысленности»
являет фраза «Он встретил ее на поляне с цветами». Совершенно непонятно,
где цветы: у него, у нее или на
поляне. От неоднозначности страдают все языки,
включая английский. Так, вопрос “Tell me, what has four wheels and flies”
заставляет нас вспомнить, какой летательный аппарат имеет четыре колеса.
Речь при этом идет о “garbage truck”, и «flies» означает «мухи», а не «летает».
Семантическая же сеть должна содержать знания в математически точной
форме.
7.2. Историческая справка
Математика позволяет описать большинство явлений в окружающем мире
в виде логических высказываний. Семантические сети возникли как попытка
визуализации математических формул. Прародителями современных
семантических сетей можно считать экзистенциальные графы, предложенные
Чарльзом Сандерзом Пирсом в 1909г. Они использовались в органической
химии для представления логических высказываний в виде особых диаграмм.
Пирс
назвал этот способ «логикой будущего».
субъект
объект
предикат
69
Важным начинанием в исследовании сетей стали работы немецкого
психолога Отто Зельца 1913 и 1922гг. В них для организации структур понятий
и ассоциаций, а также изучения методов наследования свойств он использовал
графы и семантические отношения. Научные изыскания Зельца имели огромное
влияние на изучение тактики в шахматах, которые в свою очередь повлияли на
таких
теоретиков, как Саймон и Ньюэлл. Исследователи Дж. Андерсон (1973),
Д. Норман (1975) и другие использовали эти работы для моделирования
человеческой памяти и интеллектуальных свойств.
Что касается лингвистики, то первым ученым, занимавшимся разработкой
графических описаний, стал Теньер. Он использовал графическую запись для
своей грамматики зависимостей. Теньер существенно повлиял на развитие
лингвистики в Европе.
Компьютерные семантические сети были детально
разработаны Ричардом Риченсом в 1956 году в рамках проекта Кембриджского
центра изучения языка по машинному переводу. Процесс машинного перевода
подразделяется на 2 части: перевод исходного текста в промежуточную форму
представления, а затем эта промежуточная форма транслируется на нужный
язык. Такой промежуточной формой как раз и были семантические сети
.
Первая такая система, которую создала Мастерман, включала в себя 100
примитивных концептов таких, как, например, НАРОД, ВЕЩЬ, ДЕЛАТЬ,
БЫТЬ. С помощью этих концептов она описала словарь объемом 15000 единиц,
в котором также имелся механизм переноса характеристик с гипертипа на
подтип. Некоторые системы машинного перевода базировались на
корреляционных сетях Цеккато, которые представляли собой
набор 56
различных отношений, некоторые из которых - падежные отношения,
отношения подтипа, члена, части и целого. Он использовал сети, состоящие из
концептов и отношений для руководства действиями программы текстового
разбора и разрешения неоднозначностей. Эти исследования были продолжены
Робертом Симмонсом (1966), Уилксом (1972) и другими учёными [4].
В системах искусственного интеллекта семантические сети используются
для ответа на
различные вопросы, изучение процессов обучения, запоминания
и рассуждений. В конце 70-х сети получили широкое распространение. В 80-х
годах границы между сетями, фреймовыми структурами и линейными формами
записи постепенно стирались. Выразительная сила больше не является
решающим аргументом в пользу выбора сетей или линейных форм записи,
поскольку идеи, записанные с помощью одной
формы записи, могут быть легко
переведены в другую. И наоборот, особо важную роль стали играть такие е
факторы, как читаемость, эффективность, неискусственность и теоретическая
элегантность, также учитываются легкость введения в компьютер, редак-
тирование и распечатка [5].
На понимание проблем представления знаний с помощью семантических
сетей большое влияние оказало эссе Дрю МакДермота «Искусственный
интеллект сталкивается с естественной глупостью» [6], которое цитируется уже
в течение 30 лет.
Наиболее продвинутой отечественной разработкой в области применения
70
аппарата семантических сетей в задачах анализа и поиска текстовой
информации является набор программных продуктов под торговой маркой RCO
(Russian Context Optimizer) компании «Гарант Парк Интернет» (www.rco.ru
).
Наконец, следует упомянуть концепцию Семантической Паутины
(Semantic Web), которая будет подробнее рассмотрена в подразд. 7.7 и 7.8.
Семантическая Паутина – это дальнейшее развитие Всемирной паутины,
заключающееся в том, что документы, размещаемые на ее ресурсах, содержат
семантическую разметку, позволяющую извлечь смысл информации,
содержащейся в этих документах. Такие семантические документы создаются,
в основном, в формате RDF (Resource Description Framework) – расширении
языка
XML, дополненном средствами представления триплетов субъект-
предикат-объект.
7.3. Типы семантических сетей
Семантическая сеть, в которой все отношения бинарные, образует
реляционный граф (рис. 7.1.).
Рис.7.1. Пример реляционного графа
Несмотря на то, что понятия “Larry Smith” и “Man” обозначаются на графе
одинаковыми эллипсами, их смысловое качество различно. “Larry Smith” –
экземпляр класса мужчин, а “Man” – множество мужчин. В свою очередь,
“Man” и “Woman” являются подмножествами более мощного множества людей
(“Person”). Таким образом, как и в реляционных базах данных, здесь имеют
место отношения «один к
одному», «один ко многим», «многие к многим».
Если арность отлична от двух, изобразить семантическую сеть в виде
графа уже сложнее. Но, как и в базах данных, можно провести нормализацию и
привести все к бинарным отношениям. Например, унарное отношение типа
«мотор – работает» можно привести к виду «мотор» -> «состояние» ->
«работа». Отношение с
арностью 3 типа «Самолет летит из Петербурга в
Москву» оперирует с тремя понятиями: субъект – это самолет, а объекты –
Москва и Петербург. Предикат – выполнение полета («летит»). Введя
дополнительное понятие «полет», данное отношение можно представить
a_kind_of
a
a_kind_of is_a
husband wife
Larry Smith Man
Person Mammal
a_kind_of
is_a
Laura Smith Woman