Рэй Соломонофф (25 июля 1926 г. – 7 декабря 2009 г.) [1] [2] был американским математиком, который изобрёл алгоритмическую вероятность , [3] его Общую теорию индуктивного вывода (также известную как Универсальный индуктивный вывод), [4] и был основателем алгоритмической теории информации . [5] Он был создателем ветви искусственного интеллекта, основанной на машинном обучении , прогнозировании и вероятности . Он распространил первый отчёт о несемантическом машинном обучении в 1956 году. [6]
Соломонов впервые описал алгоритмическую вероятность в 1960 году, опубликовав теорему, которая положила начало теории сложности Колмогорова и алгоритмической теории информации . Он впервые описал эти результаты на конференции в Калтехе в 1960 году [7] и в докладе от февраля 1960 года «Предварительный отчет об общей теории индуктивного вывода». [8] Он более полно разъяснил эти идеи в своих публикациях 1964 года «Формальная теория индуктивного вывода», часть I [9] и часть II. [10]
Алгоритмическая вероятность — это математически формализованная комбинация бритвы Оккама [11] [ 12] [13] [14] и принципа множественных объяснений. [15] Это машинно-независимый метод присвоения значения вероятности каждой гипотезе (алгоритму/программе), объясняющей данное наблюдение, при этом самая простая гипотеза (самая короткая программа) имеет самую высокую вероятность, а все более сложные гипотезы получают все меньшие вероятности.
Соломонов основал теорию универсального индуктивного вывода , которая базируется на прочных философских основах [4] и имеет свои корни в теории сложности Колмогорова и алгоритмической теории информации . Теория использует алгоритмическую вероятность в байесовском каркасе. Универсальная априорная вероятность берется по классу всех вычислимых мер; ни одна гипотеза не будет иметь нулевой вероятности. Это позволяет использовать правило Байеса (причинно-следственной связи) для прогнозирования наиболее вероятного следующего события в серии событий и того, насколько оно будет вероятным. [10]
Хотя он наиболее известен благодаря своей алгоритмической вероятности и общей теории индуктивного вывода , на протяжении своей жизни он сделал много других важных открытий, большинство из которых были направлены на достижение его цели в области искусственного интеллекта: разработать машину, которая могла бы решать сложные задачи с использованием вероятностных методов.
Рэй Соломонофф родился 25 июля 1926 года в Кливленде, штат Огайо , в семье еврейских иммигрантов из России Филиппа Джулиуса и Сары Машман Соломонофф. Он учился в средней школе Гленвилля, которую окончил в 1944 году. В 1944 году он поступил на службу в ВМС США в качестве инструктора по электронике. С 1947 по 1951 год он учился в Чикагском университете , где учился у таких профессоров, как Рудольф Карнап и Энрико Ферми , и окончил его со степенью магистра физики в 1951 году.
С самых ранних лет его мотивировала чистая радость математических открытий и желание исследовать то, чего еще никто не достиг. [ необходима цитата ] В возрасте 16 лет, в 1942 году, он начал искать общий метод решения математических задач.
В 1952 году он встретил Марвина Мински , Джона Маккарти и других, интересующихся машинным интеллектом. В 1956 году Мински, Маккарти и другие организовали Дартмутскую летнюю исследовательскую конференцию по искусственному интеллекту , где Соломонофф был одним из первых 10 приглашенных — он, Маккарти и Мински были единственными, кто остался на все лето. Именно для этой группы искусственный интеллект был впервые назван наукой. Компьютеры в то время могли решать очень конкретные математические задачи, но не более того. Соломонофф хотел заняться более масштабным вопросом: как сделать машины более интеллектуальными в целом и как компьютеры могли бы использовать вероятность для этой цели.
Он написал три статьи, две из которых были написаны совместно с Анатолем Рапопортом в 1950–1952 годах [16] , которые считаются самым ранним статистическим анализом сетей.
Он был одним из 10 участников Летнего исследовательского проекта Дартмута 1956 года по искусственному интеллекту . Он написал и распространил среди участников доклад: «Машина индуктивного вывода». [6] В нем машинное обучение рассматривалось как вероятностное, с акцентом на важность обучающих последовательностей и на использование частей предыдущих решений проблем при построении пробных решений для новых проблем. Он опубликовал версию своих выводов в 1957 году. [17] Это были первые статьи, написанные по вероятностному машинному обучению.
В конце 1950-х годов он изобрел вероятностные языки и связанные с ними грамматики. [18] Вероятностный язык присваивает значение вероятности каждой возможной строке.
Обобщение концепции вероятностных грамматик привело его к открытию в 1960 году алгоритмической вероятности и общей теории индуктивного вывода.
До 1960-х годов обычный метод расчета вероятности основывался на частоте: на соотношении благоприятных результатов к общему числу испытаний. В своей публикации 1960 года и, более полно, в своих публикациях 1964 года Соломонофф серьезно пересмотрел это определение вероятности. Он назвал эту новую форму вероятности «алгоритмической вероятностью» и показал, как использовать ее для прогнозирования в своей теории индуктивного вывода. В рамках этой работы он создал философское обоснование для использования правила причинно-следственной связи Байеса для прогнозирования.
Основная теорема того, что позже было названо сложностью Колмогорова, была частью его Общей теории. В 1960 году он начал: «Рассмотрим очень длинную последовательность символов... Мы будем считать такую последовательность символов «простой» и имеющей высокую априорную вероятность, если существует очень краткое описание этой последовательности — используя, конечно, какой-то установленный метод описания. Точнее, если мы используем только символы 0 и 1 для выражения нашего описания, мы присвоим вероятность 2 − N последовательности символов, если ее кратчайшее возможное двоичное описание содержит N цифр». [19]
Вероятность относится к конкретной универсальной машине Тьюринга . Соломонов показал и в 1964 году доказал, что выбор машины, хотя и может добавлять постоянный множитель, не сильно изменит отношения вероятностей. Эти вероятности не зависят от машины.
В 1965 году русский математик Колмогоров независимо опубликовал похожие идеи. Когда он узнал о работе Соломонова, он признал Соломонова, и в течение нескольких лет работа Соломонова была более известна в Советском Союзе, чем в западном мире. Однако общее мнение в научном сообществе состояло в том, чтобы ассоциировать этот тип сложности с Колмогоровым, которого больше интересовала случайность последовательности. Алгоритмическая вероятность и универсальная (Соломоновская) индукция стали ассоциироваться с Соломоновым, который был сосредоточен на предсказании — экстраполяции последовательности.
Позже в той же публикации 1960 года Соломонофф описывает свое расширение теории одного кратчайшего кода. Это алгоритмическая вероятность. Он утверждает: «Казалось бы, что если есть несколько различных методов описания последовательности, каждому из этих методов следует придать некоторый вес при определении вероятности этой последовательности». [20] Затем он показывает, как эту идею можно использовать для генерации универсального априорного распределения вероятностей и как она позволяет использовать правило Байеса в индуктивном выводе. Индуктивный вывод, путем сложения предсказаний всех моделей, описывающих конкретную последовательность, с использованием подходящих весов, основанных на длинах этих моделей, получает распределение вероятностей для расширения этой последовательности. Этот метод предсказания с тех пор стал известен как индукция Соломоноффа .
Он расширил свою теорию, опубликовав ряд отчетов, предшествовавших публикациям в 1964 году. Статьи 1964 года дают более подробное описание алгоритмической вероятности и индукции Соломонова, представляя пять различных моделей, включая модель, широко называемую универсальным распределением.
Другие ученые, присутствовавшие на летней конференции в Дартмуте 1956 года (например, Ньюэлл и Саймон ), разрабатывали ветвь искусственного интеллекта, которая использовала машины, управляемые правилами «если-то», основанными на фактах. Соломонофф разрабатывал ветвь искусственного интеллекта, которая фокусировалась на вероятности и прогнозировании; его особый взгляд на ИИ описывал машины, которые управлялись алгоритмическим распределением вероятностей. Машина генерирует теории вместе с их связанными вероятностями для решения проблем, и по мере появления новых проблем и теорий обновляет распределение вероятностей в теориях.
В 1968 году он нашел доказательство эффективности алгоритмической вероятности, [21] но, главным образом из-за отсутствия общего интереса в то время, не публиковал его до 10 лет спустя. В своем отчете он опубликовал доказательство теоремы о сходимости.
В последующие годы после открытия алгоритмической вероятности он сосредоточился на том, как использовать эту вероятность и индукцию Соломонова в реальном прогнозировании и решении задач для ИИ. Он также хотел понять более глубокие последствия этой вероятностной системы.
Одним из важных аспектов алгоритмической вероятности является то, что она полна и невычислима.
В отчете 1968 года он показывает, что алгоритмическая вероятность является полной ; то есть, если в массиве данных есть какая-либо описываемая закономерность, алгоритмическая вероятность в конечном итоге обнаружит эту закономерность, требуя относительно небольшой выборки этих данных. Алгоритмическая вероятность является единственной вероятностной системой, известной как полная таким образом. Как необходимое следствие ее полноты она невычислима . Невычислимость заключается в том, что некоторые алгоритмы — подмножество тех, которые являются частично рекурсивными — никогда не могут быть полностью оценены, потому что это заняло бы слишком много времени. Но эти программы, по крайней мере, будут распознаны как возможные решения. С другой стороны, любая вычислимая система является неполной . Всегда будут описания за пределами пространства поиска этой системы, которые никогда не будут признаны или рассмотрены, даже за бесконечное количество времени. Вычислимые модели прогнозирования скрывают этот факт, игнорируя такие алгоритмы.
Во многих своих работах он описывал, как искать решения проблем, и в 1970-х и начале 1980-х годов разработал то, что он считал наилучшим способом модернизации машины.
Однако использование вероятности в ИИ не имело полностью гладкого пути. В первые годы ИИ релевантность вероятности была проблематичной. Многие в сообществе ИИ считали, что вероятность не может быть использована в их работе. Область распознавания образов использовала форму вероятности, но поскольку не было широко обоснованной теории того, как включить вероятность в любую область ИИ, большинство областей вообще ее не использовали.
Однако были исследователи, такие как Перл и Питер Чизман, которые утверждали, что вероятность можно использовать в искусственном интеллекте.
Около 1984 года на ежегодном собрании Американской ассоциации искусственного интеллекта (AAAI) было решено, что вероятность не имеет никакого отношения к ИИ.
Образовалась группа протеста, и в следующем году на встрече AAAI состоялся семинар, посвященный «Вероятности и неопределенности в ИИ». Этот ежегодный семинар продолжается и по сей день. [22]
В рамках протеста на первом семинаре Соломонофф выступил с докладом о том, как применять универсальное распределение к проблемам ИИ [23]. Это была ранняя версия системы, которую он разрабатывал с тех пор.
В этом отчете он описал разработанную им технику поиска. В задачах поиска наилучшим порядком поиска является время , где — время, необходимое для проверки испытания, а — вероятность успеха этого испытания. Он назвал это «концептуальным размером прыжка» проблемы. Техника поиска Левина приближается к этому порядку, [24] и поэтому Соломонофф, изучавший работу Левина, назвал эту технику поиска Lsearch.
В других работах он исследовал, как ограничить время, необходимое для поиска решений, описывая поиск с ограниченным ресурсом. Пространство поиска ограничивается доступным временем или стоимостью вычислений, а не путем урезания пространства поиска, как это делается в некоторых других методах прогнозирования, таких как минимальная длина описания.
На протяжении всей своей карьеры Соломонофф был обеспокоен потенциальными преимуществами и опасностями ИИ, обсуждая это во многих своих опубликованных отчетах. В 1985 году он проанализировал вероятную эволюцию ИИ, предсказав формулу, предсказывающую, когда он достигнет «Точки бесконечности». [25] Эта работа является частью истории мысли о возможной технологической сингулярности .
Первоначально методы алгоритмической индукции экстраполировали упорядоченные последовательности строк. Для работы с другими типами данных требовались методы.
В отчете 1999 года [26] универсальное распределение и связанные с ним теоремы сходимости обобщаются на неупорядоченные наборы строк, а в отчете 2008 года [27] — на неупорядоченные пары строк.
В 1997, [28] 2003 и 2006 годах он показал, что неисчислимость и субъективность являются необходимыми и желательными характеристиками любой высокопроизводительной индукционной системы.
В 1970 году он основал собственную компанию Oxbridge Research и продолжил там свои исследования, за исключением периодов в других учреждениях, таких как MIT, Университет Саара в Германии и Институт искусственного интеллекта Далле Молле в Лугано, Швейцария. В 2003 году он стал первым обладателем премии Колмогорова от Исследовательского центра компьютерного обучения в Royal Holloway, Лондонский университет, где он прочитал первую лекцию Колмогорова. Соломонофф в последнее время был приглашенным профессором в CLRC.
В 2006 году он выступил на AI@50 , «Dartmouth Artificial Intelligence Conference: the Next Fifty Years», посвященной пятидесятилетию оригинальной летней учебной группы Дартмута. Соломонофф был одним из пяти первоначальных участников, которые присутствовали.
В феврале 2008 года он выступил с программной речью на конференции «Современные тенденции в теории и применении компьютерных наук» (CTTACS), состоявшейся в Университете Нотр-Дам в Ливане. Затем он прочитал короткую серию лекций и начал исследования новых приложений алгоритмической вероятности.
Алгоритмическая вероятность и индукция Соломонова имеют много преимуществ для искусственного интеллекта. Алгоритмическая вероятность дает чрезвычайно точные оценки вероятности. Эти оценки могут быть пересмотрены надежным методом, чтобы они продолжали быть приемлемыми. Он использует время поиска очень эффективно. В дополнение к оценкам вероятности, алгоритмическая вероятность «имеет для ИИ еще одну важную ценность: ее множественность моделей дает нам много разных способов понимать наши данные;
Описание жизни и работы Соломоноффа до 1997 года можно найти в статье «Открытие алгоритмической вероятности», журнал «Компьютерные и системные науки», том 55, № 1, стр. 73–88, август 1997 года. Статья, а также большинство других упомянутых здесь работ, доступны на его веб-сайте на странице публикаций.
В статье, опубликованной в год его смерти, в журнальной статье о Соломонове говорилось: «Очень традиционный ученый понимает свою науку, используя одну-единственную «текущую парадигму» — способ понимания, который наиболее популярен в настоящее время. Более творческий ученый понимает свою науку очень многими способами и может легче создавать новые теории, новые способы понимания, когда «текущая парадигма» больше не соответствует текущим данным». [29]
