Ray Соломоны (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]
Хотя он больше всего известен алгоритмической вероятностью и своей общей теорией индуктивного вывода , за всю свою жизнь он сделал много других важных открытий, большинство из которых были направлены на достижение его цели в области искусственного интеллекта: разработка машины, которая могла бы решать сложные задачи с использованием вероятностных методов.
История жизни до 1964 года
Рэй Соломонов родился 25 июля 1926 года в Кливленде, штат Огайо , в семье еврейских иммигрантов из России Филиппа Джулиуса и Сары Машман Соломоновы. Он учился в средней школе Гленвилля, которую окончил в 1944 году. В 1944 году он поступил на военно-морской флот США в качестве инструктора по электронике. В 1947–1951 годах он учился в Чикагском университете у таких профессоров, как Рудольф Карнап и Энрико Ферми , и получил степень магистра физики в 1951 году.
С ранних лет его двигала чистая радость математических открытий и желание исследовать то, чего раньше никто не делал. [16] В возрасте 16 лет, в 1942 году, он начал искать общий метод решения математических задач.
В 1952 году он встретил Марвина Мински , Джона Маккарти и других, интересовавшихся машинным интеллектом. В 1956 году Мински, Маккарти и другие организовали Дартмутскую летнюю исследовательскую конференцию по искусственному интеллекту , на которую Соломонов был одним из первых 10 приглашенных - он, Маккарти и Мински были единственными, кто остался все лето. Именно для этой группы искусственный интеллект был впервые назван наукой. Компьютеры в то время могли решать очень конкретные математические задачи, но не более того. Соломонов хотел задать более важный вопрос: как сделать машины более разумными и как компьютеры могут использовать для этой цели вероятность.
История работы до 1964 года
Он написал три статьи, две с Анатолем Рапопортом , в 1950–52 годах [17] , которые считаются самым ранним статистическим анализом сетей.
Он был одним из 10 участников Летнего исследовательского проекта по искусственному интеллекту в Дартмуте 1956 года . Он написал и распространил среди участников доклад: «Машина индуктивного вывода». [6] Машинное обучение рассматривалось как вероятностное, с упором на важность обучающих последовательностей и на использование частей предыдущих решений проблем при построении пробных решений для новых задач. Он опубликовал версию своих открытий в 1957 году. [18] Это были первые статьи о вероятностном машинном обучении.
В конце 1950-х он изобрел вероятностные языки и связанные с ними грамматики. [19] Вероятностный язык присваивает значение вероятности каждой возможной строке.
Обобщение концепции вероятностных грамматик привело его к открытию в 1960 году «Алгоритмической вероятности и общей теории индуктивного вывода».
До 1960-х годов обычный метод расчета вероятности основывался на частоте: взятии отношения благоприятных результатов к общему количеству испытаний. В своей публикации 1960 года и, более полно, в своих публикациях 1964 года Соломонов серьезно пересмотрел это определение вероятности. Он назвал эту новую форму вероятности «алгоритмической вероятностью» и показал, как использовать ее для предсказания в своей теории индуктивного вывода. В рамках этой работы он разработал философское основание для использования правила причинности Байеса для предсказания.
Основная теорема того, что позже было названо колмогоровской сложностью, была частью его общей теории. Написав в 1960 году, он начинает: «Рассмотрим очень длинную последовательность символов ... Мы будем считать такую последовательность символов« простой »и имеющей высокую априорную вероятность, если существует очень краткое описание этой последовательности - используя, конечно, какой-то предусмотренный метод описания. Точнее, если мы будем использовать только символы 0 и 1 для выражения нашего описания, мы присвоим вероятность 2 - N последовательности символов, если ее кратчайшее возможное двоичное описание содержит N цифры ". [20]
Вероятность относится к конкретной универсальной машине Тьюринга . Соломонов показал и в 1964 году доказал, что выбор машины, хотя она и может добавлять постоянный множитель, не сильно изменит отношения вероятностей. Эти вероятности не зависят от машины.
В 1965 году аналогичные идеи независимо опубликовал русский математик Колмогоров . Когда он узнал о работе Соломонова, он признал Соломонова, и в течение нескольких лет работы Соломонова были более известны в Советском Союзе, чем в западном мире. Однако общее мнение в научном сообществе заключалось в том, чтобы связывать этот тип сложности с Колмогоровым, которого больше интересовала случайность последовательности. Алгоритмическая вероятность и универсальная (Соломонова) индукция стали ассоциироваться с Соломоновым, который был сосредоточен на предсказании - экстраполяции последовательности.
Позже, в той же публикации 1960 года, Соломонов описывает свое расширение теории единственного кратчайшего кода. Это алгоритмическая вероятность. Он заявляет: «Казалось бы, если существует несколько различных методов описания последовательности, каждому из этих методов следует придать определенный вес при определении вероятности этой последовательности». [21] Затем он показывает, как эту идею можно использовать для генерации универсального априорного распределения вероятностей и как она позволяет использовать правило Байеса в индуктивном выводе. Индуктивный вывод путем суммирования прогнозов всех моделей, описывающих конкретную последовательность, с использованием подходящих весов, основанных на длинах этих моделей, позволяет получить распределение вероятностей для расширения этой последовательности. С тех пор этот метод предсказания получил название индукции Соломонова .
Он расширил свою теорию, опубликовав ряд отчетов, приведших к публикациям в 1964 году. В статьях 1964 года дается более подробное описание алгоритмической вероятности и индукции Соломонова, представляющих пять различных моделей, включая модель, широко известную как универсальное распределение.
История работы с 1964 по 1984 год
Другие ученые, участвовавшие в Дартмутской летней конференции 1956 года (например, Ньюэлл и Саймон ), разрабатывали ветвь искусственного интеллекта, в которой использовались машины, управляемые правилами «если-то», основанные на фактах. Соломонов развивал ветвь искусственного интеллекта, которая фокусировалась на вероятности и предсказании; его конкретный взгляд на ИИ описывал машины, которые управлялись распределением алгоритмической вероятности. Машина генерирует теории вместе с соответствующими вероятностями для решения проблем и по мере развития новых проблем и теорий обновляет распределение вероятностей теорий.
В 1968 году он нашел доказательство эффективности алгоритмической вероятности [22], но, главным образом, из-за отсутствия всеобщего интереса в то время, опубликовал его только через 10 лет. В своем отчете он опубликовал доказательство теоремы о сходимости.
Спустя годы после открытия алгоритмической вероятности он сосредоточился на том, как использовать эту вероятность и индукцию Соломонова в реальном прогнозировании и решении проблем для ИИ. Он также хотел понять более глубокие последствия этой системы вероятностей.
Одним из важных аспектов алгоритмической вероятности является то, что она является полной и невычислимой.
В отчете 1968 года он показывает, что алгоритмическая вероятность полна ; то есть, если есть какая-либо описываемая закономерность в теле данных, алгоритм алгоритмической вероятности в конечном итоге обнаружит эту закономерность, требуя относительно небольшой выборки этих данных. Алгоритмическая вероятность - единственная система вероятностей, которая, как известно, завершена таким образом. Как необходимое следствие своей полноты, это не поддается расчету . Невозможно вычислить, потому что некоторые алгоритмы - подмножество частично рекурсивных - никогда не могут быть оценены полностью, потому что это займет слишком много времени. Но эти программы, по крайней мере, будут признаны возможными решениями. С другой стороны, любая вычислимая система неполна . Всегда будут описания вне области поиска этой системы, которые никогда не будут признаны или рассмотрены, даже через бесконечное количество времени. Вычислимые модели прогнозирования скрывают этот факт, игнорируя такие алгоритмы.
Во многих своих статьях он описывал, как искать решения проблем, и в 1970-х и начале 1980-х разработал то, что, по его мнению, было лучшим способом обновить машину.
Однако использование вероятности в ИИ не было полностью гладким. В первые годы развития искусственного интеллекта актуальность вероятности была проблематичной. Многие в сообществе ИИ считали, что вероятность неприменима в их работе. В области распознавания образов действительно использовалась форма вероятности, но поскольку не было широко обоснованной теории того, как включить вероятность в какую-либо область ИИ, в большинстве областей она вообще не использовалась.
Однако были такие исследователи, как Перл и Питер Чизмен, которые утверждали, что вероятность можно использовать в искусственном интеллекте.
Примерно в 1984 году на ежегодном собрании Американской ассоциации искусственного интеллекта (AAAI) было решено, что вероятность никоим образом не имеет отношения к ИИ.
Сформировалась группа протеста, и в следующем году на собрании AAAI был проведен семинар, посвященный «Вероятности и неопределенности в ИИ». Этот ежегодный семинар продолжается и по сей день. [23]
В рамках протеста на первом семинаре Соломонов представил доклад о том, как применять универсальное распределение к задачам в ИИ [24]. Это была ранняя версия системы, которую он разрабатывал с тех пор.
В этом отчете он описал разработанную им методику поиска. В задачах поиска лучший порядок поиска - это время, где время, необходимое для проверки испытания и вероятность успеха этого испытания. Он назвал это «концептуальным размером прыжка» проблемы. Методика поиска Левина приближается к этому порядку [25], поэтому Соломонов, изучавший работы Левина, назвал эту технику поиска Lsearch.
История работы - более поздние годы
В других статьях он исследовал, как ограничить время, необходимое для поиска решений, писал о поиске с ограничением ресурсов. Пространство поиска ограничено доступным временем или стоимостью вычислений, а не вырезанием пространства поиска, как это делается в некоторых других методах прогнозирования, таких как минимальная длина описания.
На протяжении всей своей карьеры Соломонов был обеспокоен потенциальными преимуществами и опасностями ИИ, обсуждая их во многих своих опубликованных отчетах. В 1985 году он проанализировал вероятную эволюцию ИИ, предложив формулу, предсказывающую, когда он достигнет «Точки бесконечности». [26] Эта работа - часть истории размышлений о возможной технологической сингулярности .
Первоначально методы алгоритмической индукции экстраполировали упорядоченные последовательности строк. Нужны были методы для работы с другими видами данных.
В отчете 1999 г. [27] универсальное распределение и связанные теоремы сходимости обобщены на неупорядоченные наборы строк, а в отчете 2008 г. [28] - на неупорядоченные пары строк.
В 1997, [29] 2003 и 2006 годах он показал, что невычислимость и субъективность являются необходимыми и желательными характеристиками любой высокопроизводительной индукционной системы.
В 1970 году он основал свою собственную компанию Oxbridge Research и продолжил там свои исследования, за исключением периодов работы в других учреждениях, таких как Массачусетский технологический институт, Саарский университет в Германии и Институт искусственного интеллекта Далле Молле в Лугано, Швейцария. В 2003 году он стал первым лауреатом Колмогоровской премии Исследовательского центра компьютерного обучения при Лондонском университете Ройал Холлоуэй, где он прочитал первую лекцию Колмогорова. Соломонов совсем недавно был приглашенным профессором в CLRC.
В 2006 году он выступил на AI @ 50 , «Дартмутская конференция по искусственному интеллекту: следующие пятьдесят лет», посвященной пятидесятилетию первоначальной летней исследовательской группы в Дартмуте. Соломонов был одним из пяти первоначальных участников, которые присутствовали на нем.
В феврале 2008 г. он выступил с основным докладом на конференции «Современные тенденции в теории и применении компьютерных наук» (CTTACS), проходившей в Университете Нотр-Дам в Ливане. После этого он прочитал короткую серию лекций и начал исследования новых приложений алгоритмической вероятности.
Алгоритмическая вероятность и индукция Соломонова имеют много преимуществ для искусственного интеллекта. Алгоритмическая вероятность дает чрезвычайно точные оценки вероятности. Эти оценки можно пересмотреть с помощью надежного метода, чтобы они оставались приемлемыми. Он очень эффективно использует время поиска. Помимо оценок вероятности, «алгоритмическая вероятность» имеет для ИИ еще одно важное значение: множество моделей дает нам множество различных способов понимания наших данных;
Описание жизни и работы Соломонова до 1997 г. содержится в "The Discovery of Algorithmic Probability", Journal of Computer and System Sciences, Vol 55, No. 1, pp 73–88, August 1997. Статья, а также большая часть остальные, упомянутые здесь, доступны на его веб-сайте на странице публикаций .
В статье, опубликованной в год его смерти, в журнальной статье о Соломонове говорилось: «Ученый, придерживающийся самых традиционных взглядов, понимает свою науку, используя единственную« текущую парадигму »- способ понимания, который наиболее популярен в настоящее время. Более творческий подход ученый понимает свою науку по-разному, и ему легче создавать новые теории, новые способы понимания, когда «текущая парадигма» больше не соответствует текущим данным ». [30]
Смотрите также
- Мин Ли и Пол Витаньи , Введение в сложность Колмогорова и ее приложения. Springer-Verlag, NY, 2008, включает исторические заметки о Соломонове, а также описание и анализ его работ.
- Универсальный искусственный интеллект Маркуса Хаттера
Рекомендации
- ^ «Рэй Соломонов, 1926–2009,« Третья конференция по искусственному интеллекту » .
- ^ Марков, Джон (9 января 2010 г.). «Рэй Соломонов, пионер в области искусственного интеллекта, умер в возрасте 83 лет» . Нью-Йорк Таймс . Проверено 11 января 2009 года . CS1 maint: обескураженный параметр ( ссылка )
- ^ Витани, Пол; Легг, Шейн; Хаттер, Маркус (2007). «Алгоритмическая вероятность» . Scholarpedia . 2 (8): 2572. Bibcode : 2007SchpJ ... 2.2572H . DOI : 10,4249 / scholarpedia.2572 .
- ^ a b Сэмюэл Ратманнер и Маркус Хаттер . Философский трактат универсальной индукции. Энтропия, 13 (6): 1076–1136, 2011
- ^ Витани, П. " Некролог: Рэй Соломонофф, отец-основатель теории алгоритмической информации"
- ^ a b "Машина индуктивного вывода", Дартмутский колледж, Нью-Хэмпшир, версия от 14 августа 1956 г. (сканированная копия оригинала в формате pdf)
- ↑ Статья с конференции «Церебральные системы и компьютеры», Калифорнийский технологический институт, 8–11 февраля 1960 г., цитируется в «Формальная теория индуктивного вывода, часть 1, 1964 г., стр. 1».
- ^ Соломонофф, Р., « Предварительный отчет по общей теории индуктивного вывода », Отчет V-131, Zator Co., Кембридж, Массачусетс. 4 февраля 1960 г., редакция , ноябрь 1960 г.
- ^ Соломонофф, Р., " Формальная теория индуктивного вывода, часть I " Информация и управление , Том 7, № 1, стр. 1-22, март 1964 г.
- ^ a b Соломонофф Р., " Формальная теория индуктивного вывода, часть II " Информация и управление , Том 7, № 2, стр. 224–254, июнь 1964 г.
- ^ Введение: От Колмогорова и Соломонова до Де Финетти и обратно к Колмогорову Дж. Дж. МакКолл - Metroeconomica, 2004 - Интернет-библиотека Wiley.
- ^ Основы бритвы Оккама и экономия в обучении от ricoh.com D Stork - NIPS 2001 Workshop, 2001
- ↑ Бритва Оккама как формальная основа физической теории с сайта arxiv.org Соклаков А.Н. - Основы литературы по физике, 2002 - Спрингер.
- ^ Вне теста Тьюринга из uclm.es J HERNANDEZ-ORALLO - Journal of Logic, Language, and…, 2000 - dsi.uclm.es
- ^ Мин Ли и Пол Витани, Введение в сложность Колмогорова и ее приложения. Springer-Verlag, NY, 2008, стр. 339 и далее.
- ^ Эстин, АЕ (1989-12-07), "Римское правительство и политика, 200-134 до н.э.", Кембридж История древнего мира ., Cambridge University Press, стр 163-196, DOI : 10,1017 / chol9780521234481.007 , ISBN 978-1-139-05436-2
- ^ " Точный метод вычисления связности случайных сетей ", Бюллетень математической биофизики , том 14, стр. 153, 1952 г.
- ^ Машина индуктивного вывода, IRE Convention Record, раздел по теории информации, часть 2, стр. 56–62. (Версия в формате pdf)
- ^ « Отчет о достижениях в области машин, позволяющих научиться переводить языки и извлекать информацию », «Достижения в области документации и библиотековедения», Том III, pt. 2. С. 941–953. (Материалы конференции в сентябре 1959 г.)
- ^ «Предварительный отчет по общей теории индуктивного вывода», 1960, стр. 1
- ^ "Предварительный отчет по общей теории индуктивного вывода", 1960, стр. 17
- ^ "Системы индукции на основе сложности, сравнения и теоремы сходимости" IEEE Trans. по теории информации Vol. ИТ-24, № 4, с. 422–432, июль 1978 г. (версия в формате pdf)
- ^ « Универсальное распределение и машинное обучение », лекция Колмогорова, 27 февраля 2003 г., Royal Holloway, Univ. Лондона. Компьютерный журнал, Том 46, № 6, 2003 г.
- ^ « Применение алгоритмической вероятности к проблемам в искусственном интеллекте », в Kanal and Lemmer (Eds.), Неопределенность в искусственном интеллекте , Elsevier Science Publishers BV, стр 473–491, 1986.
- ^ Левин, Л.А., "Универсальные проблемы поиска", в Проблемах передачи информации, 9, стр. 115–116, 1973
- ^ «Временная шкала искусственного интеллекта: размышления о социальных эффектах», Управление человеческими системами, том 5, стр. 149–153, 1985 (версия в формате PDF)
- ^ "Два вида вероятностной индукции", Компьютерный журнал, Том 42, № 4, 1999 г. (версия в формате pdf)
- ^ "Три вида вероятностной индукции, универсальные распределения и теоремы сходимости" 2008. (версия в формате pdf)
- ^ «Открытие алгоритмической вероятности», Журнал компьютерных и системных наук, Том 55, № 1, стр. 73–88 (версия в формате pdf)
- ^ «Алгоритмическая вероятность, теория и приложения», «Теория информации и статистическое обучение», ред. Фрэнк Эммерт-Стрейб и Маттиас Демер, Springer Science and Business Media, 2009, стр. 11
Внешние ссылки
- Домашняя страница Рэя Соломонова
- Подробное описание алгоритмической вероятности см. В «Алгоритмической вероятности» Хаттера, Легга и Витани в научном журнале.
- Рэй Соломонофф (1926–2009) 85-я мемориальная конференция, Мельбурн, Австралия, ноябрь / декабрь 2011 г. и материалы «Алгоритмическая вероятность и друзья. Байесовское предсказание и искусственный интеллект», Springer, LNAI / LNCS 7070 .
- Пионеру машинного обучения отпраздновали 14 декабря 2011 г.