БИБЛИОГРАФИЧЕСКИЕ И ИСТОРИЧЕСКИЕ ЗАМЕТКИ

Хотя вполне очевидно, что одной из главных тем философии науки должно быть использование априорных знаний в обучении, до последнего времени в этой области был проведен лишь небольшой объем работы. В книге Fact, Fiction, and Forecast, написанной философом Нельсоном Гудманом [578], была опровергнута применявшаяся ранее гипотеза о том, что индукция сводится просто к изучению достаточного количества примеров некоторого высказывания с квантором всеобщности, а затем принятия его в качестве гипотезы. Рассмотрим, например, гипотезу "Цвета всех изумрудов изменчивы", где под изменчивым подразумевается "зеленый, если наблюдения проводятся до времени t, но голубой, если наблюдения проводятся после этого". В любое время, предшествующее t, человеком могли бы рассматриваться миллионы примеров, подтверждающих правило, что цвета изумрудов изменчивы, и ни одного опровергающего примера, и тем не менее не была бы выражена готовность принять это правило. Такое свойство человеческой психики можно объяснить только с помощью анализа той роли, которую играют в процессе индукции релевантные априорные знания. Гудман предложил рассматривать различные виды априорных знаний, которое могли бы оказаться применимыми в логическом выводе, включая одну из версий способа формулировки определений, называемую определением сверхгипотез. К сожалению, идеи Гудмана никогда не применялись в исследованиях по машинному обучению.
Истоками подхода к обучения на основе объяснения явились методы, используемые в планировщике Strips [465]. После формирования какого-то плана его обобщенная версия сохраняется в библиотеке планов и используется в дальнейшем планировании в качестве макрооператора. Аналогичные идеи просматриваются в архитектуре ACT* Андерсона, где они выступают под названием компиляции знаний [31], и в архитектуре Soar под названием формирование фрагментов [881]. Непосредственными причинами быстрого повышения интереса к методам обучения на основе объяснения стало появление методов приобретения схемы [379], аналитического обобщения [1062] и обобщения на основе ограничений [1056], которые были подытожены в статьях [381] и [1065]. Хирш [659] предложил алгоритм EBL, описанный в данной книге, и показал, что этот алгоритм можно непосредственно включить в систему логического программирования. Ван Хармелен и Банди [1531] показали, что метод обучения на основе объяснения представляет собой один из вариантов метода частичной оценки, используемого в системах анализа программ [742].
Проведенный в последнее время строгий анализ привел к лучшему пониманию потенциальных затрат и выгод, связанных с применением метода EBL, с точки зрения его влияния на скорость решения задач. Минтон [1057] показал, что использование метода EBL без значительных дополнительных усилий со стороны пользователя вполне может привести к существенному замедлению работы любой программы. Тамб и др. [1488] обнаружили, что аналогичная проблема возникает при формировании фрагментов знаний, предназначенных для запоминания, и предложили способ уменьшения выразительной мощи языка правил, позволяющий свести к минимуму стоимость операции согласования правил с содержимым рабочей памяти. В этой работе обнаружились явные аналогии с полученными недавно результатами анализа сложности логического вывода в ограниченных версиях логики первого порядка (см. главу 9). Формальный вероятностный анализ ожидаемых преимуществ использования метода EBL можно найти в [595] и [1471]. Превосходный обзор этого метода приведен в [396].
Вместо использования примеров в качестве материала для обобщения их можно применять непосредственно для решения новых задач в процессе, называемом формированием рассуждений по аналогии. Такой метод формирования рассуждений осуществляется в нескольких вариантах, во-первых, в виде формирования приемлемых рассуждений с учетом степени подобия [540], во-вторых, в виде дедуктивного логического вывода, основанного на определениях, но требующего привлечения примеров [330], и, в-третьих, в виде метода EBL с "отложенным принятием решений", который позволяет корректировать направление обобщения старого примера с учетом потребностей решения новой задачи. Последняя разновидность процесса формирования рассуждений по аналогии наиболее часто встречается в системах формирования рассуждения на основе конкретных случаев [830] и системах создания деривационной аналогии [1540].
Подход к использованию информации о релевантности в форме функциональных зависимостей был впервые разработан в сообществе пользователей баз данных, где он служит для структуризации больших множеств атрибутов на более легко управляемые подмножества. Функциональные зависимости применялись для формирования рассуждений по аналогии Карбонеллом и Коллинзом [222], а их трактовка, более подходящая для использования в логике, была предложена Бобровым и Рафаэлем [144]. Зависимости были повторно открыты независимо и подверглись всестороннему логическому анализу в работах Дэвиса и Рассела [329], [330]. Кроме того, зависимости использовались в методе декларативного смещения Расселом и Грософом [1327]. Эквивалентность таких понятий, как определения и пространства гипотез с ограниченным словарем, была доказана в [1323]. Возможность применения алгоритмов обучения к определениям и достижения повышенной производительности с помощью метода RBDTL впервые была показана на примере алгоритма Focus в [20]. Тадепалли [1485] описал остроумный алгоритм обучения на основе определений, который демонстрирует существенное увеличение скорости обучения.
Идею о том, что индуктивное обучение может осуществляться по методу обратной дедукции, можно проследить до работы B.C. Джевонса [736], который писал: "Изучение формальной логики и теории вероятностей привело меня к тому, что я стал приверженцем мнения, что не существует такой вещи, как отдельный метод индукции, противопоставляемый дедукции, но индукция является просто обратным воплощением дедукции". Исследования в области вычислительных алгоритмов начались с замечательных тезисов докторской диссертации Гордона Плоткина [1216], опубликованных в Эдинбурге. Хотя Плоткин разработал множество теорем и методов, которые в настоящее время находят применение в индуктивном логическом программировании, он был разочарован некоторыми результатами, показывающими неразрешимость определенных подзадач методами индукции. В системе MIS [1396] снова была предпринята попытка решения задачи изучения логических программ, но самим автором эта работа в основном рассматривалась как вклад в теорию автоматизированной отладки. Работа в области индуктивного вывода правил, подобная проведенной при создании систем ID3 [1257] и CN2 [263], привела к появлению системы Foil [1258], которая впервые позволила осуществлять на практике методы индуктивного вывода реляционных правил. Исследования в области реляционного обучения получили новый стимул после публикации работы Магглтона и Бантайна [1100], в которой была описана программа Cigol, реализующая немного неполную версию метода обратной резолюции, но способную вырабатывать новые предикаты5. Задачи изобретения предикатов рассматриваются также в [1604]. Следующей важной системой стала Golem [1102], в которой используется алгоритм формирования покрытия, основанный на выдвинутом Плоткином понятии относительного наименьшего общего обобщения. Тогда как система Foil была нисходящей, системы Cigol и Golem действовали в восходящем направлении. К примерам других систем, появившихся в тот период, относятся Itou [1312] и Clint [352]. В разработанной в дальнейшем системе Progol [1098] был принят гибридный (нисходящий и восходящий) подход к формированию обратного логического следствия; эта система применялась для решения целого ряда практических задач, особенно в области биологии и обработки естественного языка. В [1099] описано расширение системы Progol, позволяющее учитывать неопределенность, в форме стохастических логических программ.
Формальный анализ методов ILP приведен в [1096], большая подборка статей представлена в [1097], а описания методов и приложений собраны в [897]. В [1163] можно найти более современный обзор истории развития этой области и описание проблем, которые должны быть решены в будущем. Первые результаты анализа сложности, опубликованные в [632], свидетельствовали о том, что задача изучения высказываний в логике первого порядка является безнадежно сложной. Однако благодаря лучшему пониманию важности синтаксических ограничений различного рода, налагаемых на выражения, удалось получить положительные результаты даже для выражений с рекурсией [426]. Результаты изучения возможности обучения для методов ILP изложены в [279] и [794].
Несмотря на то что в настоящее время индуктивное логическое программирование, по-видимому, является доминирующим подходом к решению задач конструктивной индукции, это — не единственный опробованный подход. Разработаны так называемые системы открытий, которые направлены на моделирование процесса научного открытия новых понятий, обычно путем прямого поиска в пространстве определений понятий. В системе AM, или Automated Mathematician (автоматизированный математик), Дуга Лената [337] использовались эвристики открытий, выраженные в виде правил экспертной системы для управления осуществляемым в ней поиском понятий и научных предположений в области элементарной теории чисел. В отличие от большинства систем, предназначенных для формирования математических рассуждений, в системе AM отсутствовало понятие доказательства, поэтому она могла выдвигать только предположения. Эта система повторно открыла предположение Гольдбаха и теорему уникального разложения на простые множители. Архитектура системы AM была обобщена в системе Eurisko [907] в результате введения механизма, способного перезаписывать собственные эвристики открытия этой системы. Система Eurisko применялась во многих областях, отличных от области поиска математических открытий, хотя и с меньшим успехом, чем AM. Но методология систем AM и Eurisko оказалась противоречивой [909], [1292].
Еще один класс систем открытия предназначен для обработки реальных научных данных в целях поиска новых законов. Системы Dalton, Glauber и Stahl [885] представляют собой системы на основе правил, предназначенные для поиска количественных связей в экспериментальных данных, полученных из физических систем; в каждом случае системы показали свою способность снова выдвинуть широко известное открытие из истории науки. Системы открытия, основанные на вероятностных методах (в частности, алгоритмы кластеризации, позволяющие обнаруживать новые категории), рассматриваются в главе 20.







Материалы

Яндекс.Метрика