Минский М., Пейперт С.
ПЕРСЕПТРОНЫ
*** 1969 ***
|
ФPAГMEHT КНИГИ (...) 13.6. Источники идей и их развитие
Нашу признательность всем, кто прямо или косвенно помог нам в написании этой книги, лучше всего выразить в виде краткого исторического очерка нашей работы. Мы начали сотрудничать в 1963 г., когда Маккаллок свел нас друг с другом. Мы благодарны ему не только за это, но и за то, что он первым серьезно задумался над проблемами, которые мы рассмотрели. 13.6.1. Теорема об инвариантности относительно групп. Оба мы заинтересовались персептроном с момента его провозглашения Розенблаттом в 1957 г. Мы оба представили доклады, относящиеся к «обучению» персептрона, на симпозиум по теории информации в 1960 г. в Лондоне. Наше серьезное наступление на геометрические проблемы персептрона развернулось весной 1965 г. К тому времени было известно, что персептроны первого порядка не могут вычислять никаких функций, инвариантных относительно переноса, кроме функций от |Х|, но не было и намека на то, каким образом это можно обобщить. Если оглянуться назад, то наиболее очевидным препятствием было отсутствие понятия порядка. Первоначальные исследования возможностей персептронов опирались на множества Ф частных предикатов, определенных при помощи стохастических порождающих процессов или отвечающих таким не имеющим никакого отношения к делу условиям, как требование, чтобы сами частные предикаты были линейными пороговыми функциями малого числа переменных. Подобные ограничения (в противоположность нашему |5(ф)| k) всегда, по-видимому, приводили к ситуациям, плохо поддающимся математической обработке, и тем самым усиливали господствующую тенденцию подходить к проблеме статистическими средствами, а не алгебраическими. Ближе всего к перелому во взглядах, за который мы ратуем, стояли Бледсоу и Броунинг [1959], рассмотревшие строгое ограничение порядка на одной разновидности конъюнктивно-локальной машины. С введением понятия порядка стал возможным общий вид теоремы об инвариантности относительно групп. Но сначала нужно было преодолеть по крайней мере четыре других препятствия, различных с эвристической точки зрения. 1. Мы должны были признать важность изучения геометрически тривиального предиката ФЧЕТность- ^Ри Доказательстве тео- ремы об инвариантности относительно групп, теоремы и/или, при объяснении принципа стратификации ссылки на этот предикат логически не требуются (и даже бесполезны). Но мы уверены, что эвристически он сыграл решающую роль. Его абсолютная геометрическая тривиальность позволила нам увидеть алгебраические идеи, лежащие в основе изучаемых ситуаций. То же относится и к роли положительной нормальной формы: все наши результаты можно доказать без ее помощи. Но тогда, когда мы были в совершеннейшем замешательстве относительно всего на свете, она позволила нам взамен ставящего в тупик разнобоя множества всех логических функций иметь дело лишь с простыми комбинациями масок. 2. Замысел усреднения мы вынашивали с тех самых пор, как прочли Питтса и Маккаллока [1947]. Его подкрепило красивое доказательство, предложенное Мериллом в ответ на наши первоначальные соображения по этому поводу, высказанные на семинаре в Массачусетском технологическом институте. Мерилл заметил, что если |5(ф)| |Д| для всех ср, то в множестве {Х|ср(А')} фигур X с четным числом точек столько же, сколько и с нечетным. Отсюда немедленно следует, что для любого множества Ф таких предикатов ср два множества векторов {Ф(Х)\\Х | —четное число} и (Ф (Х)| |Х | — нечетное число} должны иметь один и тот же центр тяжести. Поэтому их нельзя отделить гиперплоскостью! Это доказательство, хотя и наталкивает на полезные размышления, все еще отличается основной слабостью, присущей всем первоначальным рассуждениям о персептронах: с самого начала принимается, что предикаты представляются как множества точек в |Ф|-мерном евклидовом пространстве. Чтобы прийти к теореме об инвариантности относительно групп, нам нужно было покончить с этим представлением. Доказательство Мерилла усредняло по всему множеству |Ф|-мерных точек, наше же — по множеству функционалов, определенных на подмножествах пространства R. 3. Из-за отсутствия точек соприкосновения с классическими математическими методами, глубина которых проверена, возникали препятствия совсем другого рода. Общность фундаментальных свойств многочленов, неприводимых кривых, интегралов Хаара и т. п. создавала ощущение настоящей математики в противоположность чисто комбинаторным методам ранних работ по персеп-тронам. В науке о вычислительных машинах это встречается слишком редко и потому имеет большое значение. Мы убеждены, что уважение к настоящей математике является мощным эвристическим принципом, но оно должно соизмеряться с практическими соображениями. 4. Мы с большой неохотой присоединили к теореме об инвариантности относительно групп условие замкнутости множества Ф относительно группы, так как оно казалось нам сильным ограничением. Некоторое время спустя мы поняли, что это скорее усилило, нежели ослабило теорему (!), поскольку последняя используется главным образом для того, чтобы показать невозможность реализации различных предикатов при помощи тех или иных пер-септронов. В этом случае условие замкнутости означает, что некоторый предикат нельзя реализовать даже при помощи персеп-трона, содержащего все соответствующие предикаты ср каждого типа. Поэтому такой предикат нельзя реализовать и никаким меньшим персептроном, скажем, полученным случайным выбором из подобных частных предикатов. 13.6.2. Предикат грсвязность. Наши первые неуверенные поиски были в значительной мере стимулированы тем, что мы очень расстроились своей неспособностью доказать даже эвристически тот очевидный факт, что предикат Фсвязность не обладает конечным порядком. Уход в сторону предиката ФЧЕТНость мотивировался отчасти желанием отыскать более простой случай для изучения, отчасти надеждой найти способ свести его к интересующему нас предикату с помощью переключательных элементов1), похожих на те, которые использовались при доказательстве теоремы в случае ограничения по диаметру. К нашей первой теореме о порядке предиката Фсвязность мы пришли другим путем, через теорему «один-в-блоке». Это (в логическом смысле) решило исходную задачу, но мы продолжали изучать переключательные элементы, опираясь на интуицию, и позднее это окупилось сторицей. В то же время мы не можем сделать вид, что получили именно то, что ожидали. Пока мы разрабатывали довольно сложные переключательные цепи (гл. 5), мы полностью упустили из виду то более простое соображение, которое нам предложил Хаффмеи (§ 5.5). Хотя его построение дает только слабую нижнюю границу для скорости, с которой возрастает порядок предиката Фсвязность, оно достаточно, чтобы доказать, что этот предикат не обладает конечным порядком. Более того, оно показывает, как можно свести любой предикат на сетчатке из I R | точек к вычислению предиката т|>свяЗНОСТЬ на сетчатке примерно из точек. Тем самым формально показана определенная универсальность этого предиката для изучаемых параллельных машин, напоминающая универсальность поиска по дереву в случае обычной последовательной машины (причем обе процедуры в равной мере наталкиваются на трудности, связанные с экспоненциальным ростом). 13.6.3. Еще раз о топологии. Изучая свойство связности, мы получили привлекательный (и, быть может, загадочный) положительный результат, относящийся к предикату Эйлера. В раннем наброске этой книги мы добавили к этому результату неверное доказательство того, что в классе (...) не может быть никаких других топологических инвариантов. Доказав теорему (§ 8.4) о том, что нет никаких других топологических инвариантов, ограниченных по диаметру, мы решительно выдвинули предположение, что для случая ограниченного порядка понадобятся совершенно другие методы. Мы поэтому очень удивились, когда Майк Петерсон, молодой британский теоретик в области вычислений, которому предложили прорецензировать нашу рукопись, показал, как можно применить идеи § 5.7, чтобы свести все к переключательной цепи, предназначенной для проверки четности, и доказать тем самым теорему из § 5.9. 13.6.4. Стратификация. Это та область, в которой наши первоначальные интуитивные представления оказались катастрофически неверными. Основные результаты нашей книги были впервые формально представлены в апреле 1966 г. на симпозиуме по математическим аспектам науки о вычислительных машинах, проведенном Американским математическим обществом. К этому времени мы смогли доказать, что предикат Фсвязность не обладает конечным порядком, и предположили, что то же верно и для таких явно «глобальных» предикатов, как ^симметрия и 'Фвлизнецы (§ ^-3 и 7.5). Нас обрадовал и подбодрил восторженный прием, оказанный нам многими из коллег на симпозиуме Американского математического общества, и в не меньшей степени обрадовал скорбный прием аналогичного выступления на совещании по бионике. Но поскольку нас включили в организацию лаборатории искусственного мышления при Массачусетском технологическом институте, в значительной мере направленной на разработку реальных «видящих машин», мы не уделяли никакого внимания персептронам, пока однажды не посетили рабочее" совещание по распознаванию образов, организованное Институтом инженеров по электротехнике и радиоэлектронике США в самом начале 1967 г. в Пуэрто-Рико. Напуганные стойким влиянием персептронов (и подобных направлений мысли) на прикладное распознавание образов, мы решили выпустить нашу работу в виде книги. По иронии судьбы первыми результатами, полученными на этой новой стадии нашего увлечения, оказались псевдоположительные приложения страти-фикациц. Мы впервые столкнулись с этим явлением, когда наш студент Джон Уайт показал, что порядок предиката 'Фполыи квадрат Ра" вен трем. Мы были убеждены, что у этого предиката порядок 4. Наша уверенность станет понятной читателю, если он попытается реализовать этот предикат, используя ограниченные коэффициенты, причем ограничения не должны зависеть от размеров квадрата. Возможно, мы были настолько уверены в исключительной параллельности персептрона, что не хотели видеть, что можно закодировать в алгоритме персептрона некоторые ограниченные формы последовательных вычислений, если построить иерархию подчинения по размерам. Короче говоря, мы потратили не один месяц, чтобы выявить сущность стратификации и тем самым понять, почему нас постигла неудача при доказательстве теоремы об инвариантности относительно групп в случае бесконечных сетчаток. Ясно, что стратификация — это не просто «хитрая уловка», помогающая снизить порядок предиката: неограниченные коэффициенты позволяют осуществить гораздо более широкий диапазон последовательных (условных) вычислений, правда, такой ценой, что это представляет только математический интерес. Мы убеждены, что большинство предикатов из гл. 7 при условии ограниченности коэффициентов не обладают конечным порядком, а стратификация проводит различие между конечностью и бесконечностью порядков. Впрочем, это еще не доказано. 13.6.5. Обучение и память. Теория, изложенная в гл. 11 и 12, резко отличается по духу от нашей геометрической теории. Прежде всего, противоположны цели исследования: формулировки теорем об обучении имеют вид: «Если данный предикат принадлежи7 Т(Ф), то некоторая методика дает возможность найти набор коэффициентов, реализующий этот предикат», тогда как основная часть наше'й работы состояла в том, чтобы выяснить, когда и почему определенные предикаты принадлежат определенным классам В(Ф). Кроме того, подходящим языком для теории обучения, по-видимому, в самом деле служит язык «-мерного пространства коэффициентов, в котором фигуры и предикаты трактуются как точки и гиперплоскости. Мы уже неоднократно подчеркивали, что добиться успехов в отношении геометрической теории предикатов мы могли только тогда, когда отбрасывали подобное представление. Тем не менее мы сначала решили обсудить теорему о сходимости в основном по той причине, что нас не удовлетворяла нечеткая форма всех прежних ее формулировок. В частности, стало обычаем не обращать внимание на следующие вопросы: Является ли персептрон эффективным средством запоминания? Не становится ли время обучения слишком долгим и потому практически не оправданным, даже если разделение в принципе возможно? В какой мере результаты по сходимости персептрона выдерживают сравнение с результатами, полученными на основе более тщательно разработанных методов? Какова взаимосвязь персептрона с другими вычислительными устройствами? Чем дальше, тем все более и более важным становился для нас последний вопрос. Сравнение с гомеостатом усилило наш интерес к персептрону скорее как к хорошему объекту для изучения в математической теории вычислений, чем как к практической машине, и мы стали задаваться такими вопросами: могли ли бы мы рассматривать теорему о сходимости персептрона как яркое проявление конечности числа состояний? как она связана с подъемом на холм и другими методами поиска экстремума? отличается ли она коренным образом от других способов решения линейных неравенств? Мы несколько самонадеянно считали, что на первый вопрос легко дать ответ, пока наша студентка Терри Бейер не привлекла наше внимание к ряду трудностей. Она здраво рассудила, что выходом из положения было бы доказательство чего-то такого, что в конце концов превратилось бы в теорему 11.6. Общими усилиями при помощи Доны Штраусс было получено интересное, но непригодное для публикации доказательство. Вскоре затем мы узнали, что Брэдли Эфрон уже доказал подобную теорему, и обнаружили, что, беря на вооружение его идею, мы можем получить доказательство, приведенное в § 11.6. Эфрон, не опубликовавший свое доказательство, считает себя обязанным Нильсу Нильсону за одну догадку, которая привела его к этой теореме. Теорему об обучении персептрона мы сейчас рассматриваем как простой пример более широкой проблемы памяти (хранения и поиска информации), подобно тому как необучающийся персеп-трон служит исходным пунктом в теории вычислений. Главу 12 можно считать декларацией важности этой проблемы. 13.7. Вычислительная геометрия Нам приятно думать, что персептрон воочию демонстрирует возможность более согласованного взаимодействия между традиционными разделами математики и вычислительной математикой. Когда мы первоначально рассматривали предикат Фсвязность’ мы считали, что изучаем единичный факт, касающийся разновидности вычислительного устройства. Через некоторое время, когда мы уже выдвинули некоторые предположения и приступили к доказательству того, что единственными топологическими предикатами конечного порядка служат предикаты Эйлера, мы ощутили, что изучаем геометрию. Можно было бы принять это за нездоровую тенденцию людей, воспитанных на классической математике, переносить новую вычислительную дисциплину обратно на знакомую им почву. С другой стороны, это можно рассматривать как черты вычислительной математики будущего не просто как новой и самостоятельной науки, но и как способа рассуждений, который проникнет во все остальные отрасли знания. Истина должна находиться где-то между этими крайностями. В любом случае неуклонный рост и успех исследований, который мы наблюдаем в Массачусетском технологическом институте, убеждает нас как в жизненности концепции вычислительной геометрии, так и в способностях наших коллег и учеников. 13.8. Благодарности Блюм и Хьюитт получили первый новый результат о геометрических способностях машин с конечным числом состояний. Позже Блюм, Хеннеман и Фелл обнаружили интересные соотношения между фигурами на евклидовой плоскости при наложении дискретной сетки. Бейер открыла весьма неожиданные алгоритмы для геометрических вычислений в итеративных ансамблях автоматов. Не приходится и говорить, что эти лица внесли свой вклад в теорию, изложенную в этой книге как своим влиянием на творческую атмосферу, в которой создавалась книга, так и большим числом советов, замечаний и критических высказываний. Многие детали математических построений и изложения улучшены благодаря советам Армстронга, Берда, Лайонса, Петерсона и Сассмена. Наряду с названными выше коллегами мы также многим обязаны Бледсоу, Штраусс, Селфриджу, Соломонову, Фано. Из дипломатических и эвристических соображений мы хотели бы отметить, что большинство новых идей возникало в новой для нас обстановке: на пляжах, среди болот, на вершинах гор. Организация перспективных исследовательских проектов (Advanced Research Projects Agency) не только поддержала нас в финансовом отношении. Мы хотим отметить выдающуюся роль в развитии вычислительной математики ее отдела Информационных наук, и особенно группы основателей этого отдела: Ликлай-дера, Сазерленда, Тейлора, Робертса. Финансирование большей части нашей работы осуществлялось организацией ARPA через Массачусетский технологический институт и Управление военно-морских исследований. |
