Предсказание и моделирование в алгоритмическом пространстве
Споры о методе (о "правильном" научном методе познания), разгоревшиеся в филосифии Нового Времени, закончились признанием того, что абсолютно достоверного знания не существует. Однако это признание вовсе не отменило науку как таковую, а лишь поставило вопрос некоторого критерия ("критерия рациональности"), с помощью которого можно было выбирать наиболее правильную научную гипотезу (иными словами, осуществлять индуктивный вывод). Под правильностью же гипотезы или модели всегда понималась возможность предсказывать с ее помощью ранее ненаблюдавшиеся феномены. Удивительно, но в области ИИ опыт научной методологии был воспринят далеко не всеми и не сразу. Главенствующей тенденцией в ИИ долгое время оставалось (и частично остается сейчас) построение детерминированных логических (дедуктивных) систем, оперирующих с "достоверными знаниями". Например, в 1984 на годовом собрании AAAI голосованием было решено, что методы, имеющие дело с вероятностыми или недостоверными данными, никакого отношения к ИИ не имеют. В ответ на это была даже организована группа протеста, чья деятельность была посвящена вопросам вероятности и недостоверности в ИИ. И только когда машинное обучение стало одним из основных вопросов ИИ, значимость индуктивного вывода была оценена.
На определенном уровне абстракции многие вопросы: распознавание образов,
формирование понятий, навигация во внешнем мире, интерпретация сенсорной
информации, обучение и т.д., - оказываются идентичными. При решении всех эти
проблем, по сути, строится модель на основе некоторых исходных данных. Более
того, и такие проблемы, как принятие решений, планирование или предсказание
можно рассматривать в качестве сопутствующих проблем моделирования. Таким
образом, решение проблемы построения модели должно стать ключом к построению
системы искусственного интеллекта. Существует множество частных методов
построения моделей, которые применяются в конкретных задачах.
К сожалению,
принципиальная ограниченность этих методов часто не замечается (поскольку сами
методы хорошо работают в рамках специализированных задач). Однако эта
ограниченность отчетливо проявляется при попытке создать на их основе системы
машинного обучения. Подобные системы оказываются не способными выучить многие
понятия. К ним вполне применим лозунг противников возможности создания ИИ:
"компьютер не способен сделать то, что в него не было заложено
человеком".
Рассмотрим простой пример на распознавание образов. Пусть есть
векторы, принадлежащие двум классам: {(10, 17.3), (12, 11.5), (15, 12.2)} и
{(13.4, 16), (14.1, 11), (20.9, 13)}. И требуется определить, к какому классу
принадлежит вектор (19.1, 18). В классическом подходе к распознаванию образов
считается, что классы принадлежать областям (то есть, "непрерывным" множествам).
Ни один современный метод (ни метод опорных векторов, ни различные нейронные
сети), какие бы сложные и нелинейные модели он не использовал, не сможет
правильно разделить эти два класса (если, конечно, человек специально не заложит
эту возможность, выбрав, например, такое исходное представление данных, в
котором целые и дробные числа были бы разделены). Подобной ограниченностью и
страдают имеющиеся методы построения моделей. Главное здесь то, что сколь бы
большой ни была обучающая выборка, они не смогут сформировать нужное понятие.
Если заранее известно, что система чему-то (точнее многому) не может научиться,
то какая может быть речь об ИИ?
Подобные ограничения часто пытаются
преодолеть некими эвристическими ухищрениями, вручную расширяя пространство
моделей, доступное системе обучения. Однако этот подход исходно порочен, так как
соответствует тому же лозунгу, что компьютер не может делать того, что в него не
заложено человеком.
В этой связи особый интерес представляет алгоритмический подход к проблеме построения моделей. В этом подходе модель для некоторого исходного массива данных - это программа для универсальной машины Тьюринга (УТМ), которая эти данные порождает на выходе. Здесь необходимо сделать два замечания.
1. Помимо УТМ может использоваться любая другая эквивалентная формализация понятия алгоритма, например, нормальные алгорифмы Маркова, лямбда-исчисление, рекурсивные функции, нейронные сети и т.д. Здесь принципиально именно то, что пространство моделей является алгоритмически полным.
2. Программ, генерирующих исходный набор данных, бесконечно много. В частности, может быть просто программа, которая содержит сам массив данных, а ее работа заключается просто в том, чтобы напечатать его. Тогда возникает естественный вопрос: а где же тут, собственно, модель??? В действительности, любая программа, печатающая на выходе исходные данные является моделью, но у них есть одно принципиальное отличие - их длина. Длина программы непосредственно связана с вероятностью соответствующей модели. Чем длиннее программа, тем хуже модель. Программа, в которую данные зашиты в исходном виде, - это ad hoc модель (классическая ad hoc модель озвучивается как "на то божья воля"). Ее длина равна длине самих данных (плюс оператор печати), то есть это наихудшая (наименее вероятная) модель. Чем короче программа, тем эффективнее она выявляет закономерности, скрытые в данных. Как раз длина модели (описывающая ее сложность) и является критерием рациональности, единым для индуктивного вывода и машинного обучения. Однако обсуждение этого критерия - отдельный вопрос.
Оказывается, что с помощью алгоритма можно представить любую вообразимую
человеком модель. Удивительно, но для всех иррациональных чисел, которые
известны человеку, существуют короткие программы их генерации. То есть, имея,
скажем миллион знаков числа пи, их можно сжать в программу на языке Си длиной
порядка 150 байт. И хотя многие могут возразить, что это является моделью числа
пи, однако подобная модель может использоваться для генерации последующих знаков
числа пи, причем сделает это правильно.
На первый взгляд может быть не совсем
понятно, как такой подход может использоваться для прогнозирования. Основная
идея заключается в следующем. Пусть у нас есть строка исходных данные X. Мы к
этой строке можем присоединять произвольные строки Yi и искать алгоритмическую
модель для конкатенации строк XYi. Вероятность продолжения Yi строки X будет
выражаться через длину наикратчайшей программы, которая генерирует строку XYi на
выходе. Действительно, если мы возьмем миллион знаков числа пи и добавим еще
один правильный знак, то программа практически не изменится. Если же знак будет
"неправильный", то программа будет состоять из двух шагов: сначала генерируется
миллион знаков числа пи, а потом дописывается "неправильный" знак, то есть ее
длина будет больше, а вероятность - меньше.
Итак, алгоритмический подход к построению моделей позволяет преодолеть принципиальную ограниченность классических методов машинного обучения. Системы, построенные на основе этого подхода, демонстрируют возможность научиться тому, что никак не учитывалось (и просто не могло быть принято во внимание) человеком-разработчиком.
Описания двух наиболее значительных проектов на эту тему можно найти по
ссылкам:
Jurgen
Schmidhuber
(см., напр., описание системы OOPS : Optimal Ordered Problem
Solver, а также работы по метаобучению и машине Гёделя)
Ray Solomonoff
(см.,
напр., "Progress in Incremental Machine Learning; Revision 2.0, 30 Oct. 2003" и
другие его работы)
