Антология машинного обучения. Важнейшие исследования в области ИИ за последние 60 лет - Терренс Дж. Сейновски
У клеточных автоматов обычно лишь несколько дискретных значений, которые изменяются со временем в зависимости от состояния других клеток. Один из простейших клеточных автоматов – одномерный массив ячеек, каждая из которых имеет значение «0» или «1» (блок 7). Пожалуй, самый известный клеточный автомат – игра «Жизнь», которую в 1968 году изобрел Джон Конвей, Фоннеймановский профессор из Принстонского университета, и популяризировал Мартин Гарднер в своей колонке «Математические игры» в журнале Scientific American. Игра показана на рис. 13.2. Доска представляет собой двумерный массив ячеек, которые могут быть включены или выключены, и правило обновления зависит только от четырех ближайших соседей. При каждом шаге обновляются все состояния. В массиве генерируются сложные шаблоны, часть даже имеет имена – например, «планеры», которые пролетают через массив и сталкиваются с другими шаблонами. Начальные условия крайне важны для поиска конфигурации, отображающей сложные шаблоны.
Насколько распространены правила, создающие сложность? Стивен хотел узнать простейшее правило клеточных автоматов, которое может привести к сложному поведению, и поэтому начал перебирать их одно за другим. Правила под номерами от 0 до 29 создавали шаблоны, которые всегда возвращались к скучному поведению: в итоге все ячейки имели либо повторяющийся рисунок, либо фрактальный, с вложенными копиями самого себя. Однако правило 30 поражало непрерывно изменяющимися сложными моделями (блок 7). В конечном счете было доказано, что «правило 110» способно к универсальным вычислениям. То есть некоторые из простейших клеточных автоматов обладают возможностями машины Тьюринга, которая способна вычислить любую вычислимую функцию, поэтому она теоретически столь же мощна, как и любой компьютер.
Рис. 13.2. Game of life. Снимок Планерного ружья Госпера (сверху), которое излучает последовательность «планеров», движущихся по диагонали, от «материнского корабля» сверху к правому нижнему углу
Одно из следствий этого открытия – вывод, что удивительная сложность, которую мы находим в природе, могла методом проб и ошибок развиться в простейшей среде химического взаимодействия между молекулами. То, что в ходе эволюции возникнут сложные комбинации молекул, ожидаемо и не должно считаться чудом. Однако клеточные автоматы – не достаточно хорошая модель зарождения жизни, и остается открытым вопрос, какие простые химические системы способны создавать сложные молекулы[362]. Возможно, только особые биохимические системы обладают таким свойством, и это сужает вероятный набор взаимодействий, из которых могла возникнуть жизнь. Теперь мы знаем, что избыточность[363] в мозге основана на разнообразии, а не на дублировании.
Важнейшее свойство жизни – способность клетки к самовоспроизведению. Джон фон Нейман из Института перспективных исследований в Принстоне прорабатывал этот вопрос в 1940-х годах с использованием клеточных автоматов. Фон Нейман – венгерский ученый, оказавший сильное влияние на многие области математики, включая его основополагающие работы по теории игр, упомянутые в главе 1. Какой простейший клеточный автомат может точно воспроизвести себя? Фон Нейман нашел очень сложный клеточный автомат с 29 внутренними состояниями и большим объемом памяти, позволяющим тому самовоспроизводиться. Это имеет определенный биологический интерес, так как у клеток с такой же способностью есть много внутренних состояний и память, выраженная в виде ДНК. С тех пор были найдены еще более простые клеточные автоматы, умеющие самовоспроизводиться.
Мозг – это компьютер?
В 1943 году Уоррен Маккалок и Уолтер Питтс показали, что можно построить цифровой компьютер с помощью простых двоичных элементов с заданным порогом, таких как перцептрон, который можно включить в компьютер в качестве элементарного логического вентиля[364]. Теперь мы знаем, что мозг обладает смешанными аналоговыми и цифровыми свойствами и что нейронные сети обычно не вычисляют логические функции. Но в то время эта статья привлекла много внимания и, в частности, вдохновила Джона фон Неймана задуматься о компьютерах. Он построил один из первых цифровых компьютеров, в котором хранились программы, – необычный проект для математика того времени. Когда в 1957 году фон Нейман умер, Институт перспективных исследований не продолжил его начинание и выбросил компьютер[365].
Фон Нейман также интересовался мозгом. В своих Силлимановских лекциях[366] в Йельском университете он размышлял о том, как мозг может надежно функционировать с такими ненадежными компонентами[367]. Когда транзистор в цифровом компьютере допускает ошибку, весь компьютер может выйти из строя, но когда нейрон в мозге дает сбой, остальная часть мозга адаптируется к сбою и продолжает работать. Фон Нейман полагал, что причиной устойчивости мозга может быть запас «лишних» связей, так как в каждой операции участвует множество нейронов. Избыточность, как правило, нужна для резервной копии на случай отказа основной системы. Но сейчас мы знаем, что избыточность в мозге основана на разнообразии, а не на дублировании. Фон Неймана также волновала логическая глубина: сколько логических шагов может сделать мозг, прежде чем накопленные ошибки испортят результат. В отличие от компьютера, который может отлично выполнять каждый логический шаг, в мозге множество источников помех. Мозг не может достичь совершенства, но поскольку так много нейронов работают параллельно и одновременно, за каждый шаг он выполняет гораздо больше, чем компьютер, и ему требуется меньшая логическая глубина.
Пространство алгоритмов
Сколько всего алгоритмов? Представьте себе пространство всех возможных алгоритмов. Каждая точка в пространстве – алгоритм, который что-то делает. Некоторые из них удивительно полезны и удобны. В прошлом их создавали вручную математики и программисты, трудясь как ремесленники в артели. Стивен Вольфрам автоматизировал процесс для клеточных автоматов путем полного перебора алгоритмов, начиная с самых простых, некоторые из которых выдавали очень сложные рисунки. Этот принцип обобщен в выведенном Вольфрамом правиле, которое гласит: вам не нужно углубляться в пространство алгоритмов, чтобы найти тот, что решает интересующий вас класс проблем. Примерно как отправлять ботов играть в StarCraft в Сети, чтобы опробовать все возможные стратегии. Согласно правилу Вольфрама, где-то во вселенной алгоритмов должна быть галактика алгоритмов, которые приведут к победе.
Вольфрам сосредоточился на пространстве клеточных автоматов – небольшой части в пространстве всех возможных алгоритмов. Теперь у нас есть подтверждение правила Вольфрама и в пространстве нейронных сетей. Каждая сеть глубокого обучения была найдена с помощью обучающего алгоритма, который представляет собой метаалгоритм для поиска новых алгоритмов. Для большой сети и большого набора данных обучение из разного исходного состояния может создавать галактику сетей, примерно одинаково
