Рэй Соломонов

Рэй Соломонов (25 июля 1926 г. - 7 декабря 2009 г.) был американским математиком, который изобрел алгоритмическую вероятность , его Общая теория индуктивного вывода (также известная как универсальный индуктивный вывод), и был основателем алгоритмической теории информации . Он был создателем отрасли искусственного интеллекта, основанной на машинном обучении , предсказании и вероятности . Он распространил первый отчет о несемантическом машинном обучении в 1956 году.

Соломонов впервые описал алгоритмическую вероятность в 1960 году, опубликовав теорему, положившую начало колмогоровской теории сложности и алгоритмической теории информации . Впервые он описал эти результаты на конференции в Калифорнийском технологическом институте в 1960 году. и в отчете от февраля 1960 г. «Предварительный отчет по общей теории индуктивного вывода». Он более полно разъяснил эти идеи в своей публикации 1964 года «Формальная теория индуктивного вывода», часть I. и Часть II.

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

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

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

История жизни до 1964 года

Рэй Соломонов родился 25 июля 1926 года в Кливленде, штат Огайо , в семье еврейских иммигрантов из России Филиппа Джулиуса и Сары Машман Соломонов. Он учился в средней школе Гленвилля, которую окончил в 1944 году. В 1944 году он поступил на службу в ВМС США в качестве инструктора по электронике. В 1947–1951 годах он учился в Чикагском университете , обучаясь у таких профессоров, как Рудольф Карнап и Энрико Ферми , и окончил его со степенью магистра физики в 1951 году.

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

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

История работы до 1964 года

Он написал три статьи, две с Анатолем Рапопортом , в 1950–52 гг. которые считаются самым ранним статистическим анализом сетей.

Он был одним из 10 участников Летнего исследовательского проекта по искусственному интеллекту в Дартмуте в 1956 году . Он написал и распространил среди присутствующих доклад: «Машина индуктивного вывода». Он рассматривал машинное обучение как вероятностный, с упором на важность обучающих последовательностей и на использование частей предыдущих решений проблем при построении пробных решений для новых проблем. Он опубликовал версию своих результатов в 1957 году. Это были первые статьи по вероятностному машинному обучению.

В конце 1950-х годов он изобрел вероятностные языки и связанные с ними грамматики. Вероятностный язык присваивает значение вероятности каждой возможной строке.

Обобщение концепции вероятностных грамматик привело его к открытию в 1960 году «Алгоритмической вероятности и общей теории индуктивного вывода».

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

Основная теорема того, что позже было названо колмогоровской сложностью, была частью его общей теории. В 1960 году он начинает: «Рассмотрим очень длинную последовательность символов... Мы будем считать такую ​​последовательность символов «простой» и имеющей высокую априорную вероятность, если существует очень краткое описание этой последовательности – используя, конечно, какой-то предусмотренный метод описания. Точнее, если мы используем только символы 0 и 1 для выражения нашего описания, мы присвоим вероятность 2. ^{− Н} к последовательности символов, если ее кратчайшее двоичное описание содержит N цифр».

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

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

Позже в той же публикации 1960 года Соломонов описывает свое расширение теории единственного кратчайшего кода. Это алгоритмическийВероятность. Он утверждает: «Казалось бы, если существует несколько различных методов описания последовательности, каждому из этих методов следует придать некоторый вес при определении вероятности этой последовательности». Затем он показывает, как эту идею можно использовать для создания универсального априорного распределения вероятностей и как она позволяет использовать правило Байеса в индуктивном выводе. Индуктивный вывод, складывая предсказания всех моделей, описывающих конкретную последовательность, с использованием подходящих весов, основанных на длинах этих моделей, позволяет получить распределение вероятностей для расширения этой последовательности. Этот метод предсказания с тех пор стал известен как индукция Соломонова .

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

История работы с 1964 по 1984 год

Другие ученые, принимавшие участие в Летней конференции в Дартмуте 1956 года (например, Ньюэлл и Саймон ), разрабатывали раздел искусственного интеллекта, который использовал машины, управляемые правилами «если-то», основанными на фактах. Соломонов развивал раздел искусственного интеллекта, специализирующийся на вероятности и предсказаниях; его особый взгляд на ИИ описывал машины, управляемые алгоритмическим распределением вероятностей. Машина генерирует теории вместе со связанными с ними вероятностями для решения проблем и по мере развития новых проблем и теорий обновляет распределение вероятностей для теорий.

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

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

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

В отчете 1968 года он показывает, что алгоритмическая вероятность полна ; то есть, если в массиве данных есть какая-либо описуемая закономерность, алгоритмическая вероятность в конечном итоге обнаружит эту закономерность, требуя относительно небольшой выборки этих данных. Алгоритмическая вероятность - единственная вероятностная система, которая, как известно, является полной в этом смысле. Как необходимое следствие его полноты, оно неисчислимо . Неисчислимость связана с тем, что некоторые алгоритмы (подмножество частично рекурсивных) никогда не могут быть вычислены полностью, поскольку это займет слишком много времени. Но эти программы, по крайней мере, будут признаны возможными решениями. С другой стороны, любая вычислимая система неполна . За пределами пространства поиска этой системы всегда будут описания, которые никогда не будут признаны или рассмотрены, даже через бесконечное количество времени. Вычислимые модели прогнозирования скрывают этот факт, игнорируя такие алгоритмы.

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

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

Однако были такие исследователи, как Перл и Питер Чизмэн, которые утверждали, что вероятность можно использовать в искусственном интеллекте.

Примерно в 1984 году на ежегодном собрании Американской ассоциации искусственного интеллекта (AAAI) было решено, что вероятность никоим образом не имеет отношения к ИИ.

Сформировалась группа протеста, и в следующем году на встрече AAAI состоялся семинар, посвященный «Вероятности и неопределенности в ИИ». Этот ежегодный семинар продолжается и по сей день.

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

В этом отчете он описал разработанную им технику поиска. В задачах поиска лучший порядок поиска — это время. $T_{i}/P_{i}$, где $T_{i}$ время, необходимое для тестирования пробного и $P_{i}$ вероятность успеха этого испытания. Он назвал это «концептуальным размером скачка» проблемы. Техника поиска Левина приближается к этому порядку: и поэтому Соломонов, изучавший работы Левина, назвал эту технику поиска «поиском».

История работы — последующие годы

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

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

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

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

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

В 1970 году он основал свою собственную компанию Oxbridge Research и продолжал там свои исследования, за исключением периодов в других местах.такие учреждения, как Массачусетский технологический институт, Саарский университет в Германии и Институт искусственного интеллекта Далле Молле в Лугано, Швейцария. В 2003 году он стал первым лауреатом Колмогоровской премии Исследовательского центра компьютерного обучения в Ройял Холлоуэй Лондонского университета, где он прочитал первую Колмогоровскую лекцию. Совсем недавно Соломонов был приглашенным профессором в CLRC.

В 2006 году он выступил на AI@50 , «Дартмутская конференция по искусственному интеллекту: следующие пятьдесят лет», посвященная пятидесятилетию.из первоначальной летней учебной группы Дартмута. Соломонов был одним из пяти первоначальных участников, присутствовавших на мероприятии.

В феврале 2008 года он выступил с основным докладом на конференции «Современные тенденции в теории и применении информатики» (CTTACS), проходившей в Университете Нотр-Дам в Ливане. После этого он прочитал короткую серию лекций и начал исследования новых приложений алгоритмической вероятности.

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

Описание жизни и работы Соломонова до 1997 года находится в «Открытие алгоритмической вероятности», Журнал компьютерных и системных наук, том 55, № 1, стр. 73–88, август 1997 года. Эта статья, как и большая часть остальные, упомянутые здесь, доступны на его сайте на странице публикаций .

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

См. также

• Минг Ли и Пол Витани , Введение в колмогоровскую сложность и ее приложения. Springer-Verlag, Нью-Йорк, 2008 г., включает исторические заметки о Соломонове, а также описание и анализ его работы.
• Маркуса Хаттера Универсальный искусственный интеллект

Внешние ссылки

• Домашняя страница Рэя Соломонова
• Подробное описание алгоритмической вероятности см. в «Алгоритмической вероятности» Хаттера, Легга и Витани в стипендии.
• Рэй Соломонов (1926–2009), 85-я мемориальная конференция, Мельбурн, Австралия, ноябрь/декабрь 2011 г., и материалы «Алгоритмическая вероятность и ее друзья. Байесовское предсказание и искусственный интеллект», Springer, LNAI/LNCS 7070 .
• Пионер машинного обучения празднуется 14 декабря 2011 г.