Perceptrons (1969)

Материал из MachineLearning.

Статья написана с использованием LLM Gemini 3.1 Pro и проверена участником Osman Osmanov 17:24, 18 июля 2026 (MSD)

Промпт приводится полностью в Обсуждение:Perceptrons (1969).

Содержание

1 Введение
2 Персептрон
3 Алгебраическая теория линейных предикатов
4 Технические барьеры реализации
- 4.1 Экспоненциальный рост весовых коэффициентов
- 4.2 Проблема времени сходимости алгоритмов обучения
5 Историческое влияние
6 Критика
7 См. также
8 Литература

Введение

Perceptrons: An Introduction to Computational Geometry (1969) — монография Марвина Минского и Сеймура Пейперта, впервые опубликованная в 1969 году и дополненная в переиздании 1988 года^[1]. Книга представляет собой математически строгий анализ вычислительных возможностей и фундаментальных ограничений класса параллельных машин, вычисляющих предикаты с помощью взвешенного суммирования элементарных признаков, — так называемых персептронов. Центральная цель работы — переход от эмпирического поиска алгоритмов обучения к систематическому исследованию репрезентационной ёмкости архитектур. Авторы вводят понятие порядка предиката и доказывают, что многие значимые с вычислительной точки зрения свойства (чётность, связность) не могут быть реализованы персептронами конечного порядка. Все вычисления в модели оперируют строгими булевыми значениями ( $0$ или $1$ ), что принципиально отличает формализм персептрона от современных нейросетей с непрерывными функциями активации.

Персептрон

От нейронов Маккалока-Питтса к персептрону Розенблатта

В 1943 году Уоррен Маккалок и Уолтер Питтс предложили формальную модель нейрона, оперирующую строгими булевыми значениями и универсальную в смысле реализации логических функций^[1]. В конце 1950-х — начале 1960-х годов Фрэнк Розенблатт разработал персептрон — вычислительную машину, способную обучаться на примерах, и доказал теорему сходимости: если существует набор весов, правильно классифицирующий обучающую выборку, то алгоритм коррекции ошибки найдёт его за конечное число шагов^[1]. Успех демонстрационных экспериментов породил представление о персептроне как об универсальном самонастраивающемся классификаторе.

Смена парадигмы: от обучения к анализу репрезентации

Минский и Пейперт в своей книге противопоставили холистическому взгляду аналитический подход: способность алгоритма сходиться к решению бесполезна, если архитектура сети в принципе не может представить требуемое понятие. Таким образом, фокус был перенесён с обучения на репрезентацию знаний^[1].

Математический формализм персептрона

Определение и пороговая функция

В монографии персептрон рассматривается как устройство, вычисляющее бинарный предикат $\psi(X)$ , где $X \subset R$ — множество возбуждённых точек на сетчатке $R$ . Решение принимается линейной пороговой функцией от набора частных предикатов $\Phi = \{\varphi_1, \dots, \varphi_n\}$ :

$\psi(X) = 1 \quad \Leftrightarrow \quad \sum_{\varphi \in \Phi} \alpha_\varphi \varphi(X) > \theta$

Здесь $\alpha_\varphi$ — весовые коэффициенты, $\theta$ — порог. Все $\varphi(X)$ принимают значения $0$ или $1$ .

Понятие порядка предиката

Ключевым ограничением является локальность: каждый предикат $\varphi$ зависит лишь от малого подмножества точек $R$ . Авторы вводят меру этой локальности — порядок предиката, определяемый как минимальное число точек, от которых должны зависеть частные предикаты $\varphi$ , чтобы обеспечить вычисление $\psi$ . Персептроны классифицируются как машины конечного порядка, если существует конечное $k$ , такое что все $\varphi$ зависят не более чем от $k$ точек.

Алгебраическая теория линейных предикатов

Маски и теорема о положительной нормальной форме

Для анализа ограничений авторы разрабатывают алгебраический аппарат, основанный на понятии маски — конъюнктивного предиката, принимающего значение 1, если заданное подмножество точек $A \subseteq R$ полностью активно. Порядок маски равен мощности $|A|$ . Фундаментальный результат — теорема о положительной нормальной форме: любой предикат, вычислимый персептроном порядка $k$ , представим как линейная пороговая функция над масками размера не более $k$ ^[1]. Это позволяет свести геометрические вопросы к комбинаторике масок.

Теорема об инвариантности групп (Group Invariance Theorem)

Важнейшим инструментом выступает теорема об инвариантности групп. Если предикат $\psi$ инвариантен относительно группы преобразований $G$ , действующей на сетчатке $R$ , то существует эквивалентное линейное представление, в котором веса $\alpha$ постоянны на орбитах частных предикатов $\varphi$ под действием $G$ . Формально, для инвариантного предиката можно выбрать веса так, что $\alpha_\varphi = \alpha_{\varphi \circ g}$ для любого $g \in G$ . Теорема превращает геометрическую симметрию в алгебраические ограничения на коэффициенты и широко используется для доказательства невозможности вычисления тех или иных предикатов персептронами конечного порядка.

Топологические ограничения

Анализ предиката чётности

Предикат чётности ( $\psi_{\text{parity}}$ ) истинен, если число возбуждённых точек нечётно. Доказано, что любой персептрон, вычисляющий чётность на сетчатке из $N$ точек, обязан иметь порядок не менее $N$ . Следовательно, чётность невычислима персептроном ограниченного порядка.

Предикат "Один в ящике" (One-in-a-box)

Сетчатка разбивается на непересекающиеся области (ящики) $A_1, A_2, \dots, A_m$ . Предикат истинен тогда и только тогда, когда в каждом ящике содержится хотя бы одна точка:

$\psi(X) = 1 \Leftrightarrow \forall i \, (|X \cap A_i| > 0)$

Необходимость проверки наличия точки в каждом из $m$ независимых ящиков создает сложность, эквивалентную задаче чётности. Как следствие, порядок такого предиката растёт пропорционально числу ящиков $m$ , что делает его невыразимым для машин конечного порядка при больших $m$ .

Невычислимость связности

Предикат связности ( $\psi_{\text{connected}}$ ) проверяет, образуют ли возбуждённые точки связную фигуру (по соседству). Через редукцию к чётности и "Один в ящике" с помощью топологических деформаций и коммутационных сетей Хаффмана авторы показывают, что связность не может быть вычислена персептроном конечного порядка. Этот результат демонстрирует принципиальную ограниченность однослойных архитектур в отношении глобальных топологических свойств^[1].

Геометрические паттерны и их границы

Положительные результаты: выпуклость и прямоугольники

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

Выпуклость ( $\psi_{\text{convex}}$ ): фигура $X$ выпукла, если для любых двух точек $a, b \in X$ отрезок, их соединяющий, целиком лежит в $X$ . Это свойство является конъюнктивно локальным и может быть вычислено персептроном порядка не более 3.
Распознавание прямоугольников: при отсутствии сложного фона прямоугольник (или квадрат) может быть обнаружен персептроном порядка 3, проверяющим наличие углов и прямых линий.

Проблема распознавания в контексте

Указанные возможности нивелируются в условиях распознавания в контексте (recognition-in-context): если фигура окружена произвольным шумом (другими точками), то локальные признаки теряют способность однозначно идентифицировать свойство, и эффективный порядок неограниченно возрастает.

Технические барьеры реализации

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

Экспоненциальный рост весовых коэффициентов

Минский и Пейперт показывают, что даже для задач, формально решаемых персептронами конечного порядка, практическая реализация может оказаться невозможной из-за физических ограничений. Для некоторых предикатов отношение максимального веса к минимальному ( $\alpha_{\max}/\alpha_{\min}$ ) растёт экспоненциально с размером сетчатки. Это требует точности представления чисел, недостижимой в аналоговых и многих цифровых системах.

Проблема времени сходимости алгоритмов обучения

Число итераций алгоритма обучения может быть сравнимо с полным перебором всех состояний, что лишает применение алгоритма практического смысла. Авторы критикуют "иллюзию однородного программирования" — убеждение в том, что персептрон является универсальной самообучающейся средой. В монографии доказывается, что успех обучения возможен лишь тогда, когда пространство весов, совместимых с решением, достаточно велико, а это накладывает жёсткие ограничения на архитектуру.

Историческое влияние

Монография оказала существенное воздействие на развитие информатики. Она заложила математические основы вычислительной геометрии и строгой теории сложности машинного обучения. Однако пессимистичные выводы относительно перспектив искусственных нейронных сетей привели к резкому сокращению финансирования коннекционистских исследований^[1]. Период стагнации вошел в историю как первая "зима искусственного интеллекта" (AI winter). На протяжении 1970-х годов фокус научного сообщества сместился от нейросетей к символьным вычислениям и экспертным системам.

Критика

Основная критика работы возникла в период возрождения интереса к нейросетям в 1980-х годах. Главный аргумент научного сообщества заключался в необоснованной экстраполяции: авторы строго доказали ограничения исключительно однослойных персептронов, но выразили скепсис в отношении многослойных архитектур, посчитав поиск алгоритма их обучения бесперспективным^[1].

С распространением алгоритма обратного распространения ошибки (backpropagation) в 1986 году^[1] стало очевидно, что многослойные сети преодолевают эти барьеры. Многослойные архитектуры справлялись с задачами, невычислимыми для машин из одного слоя — в первую очередь с функцией XOR, являющейся частным случаем предиката чётности. Историки науки неоднократно отмечали, что категоричность монографии затормозила развитие машинного обучения^[1].

См. также

Литература

Источник — «http://machinelearning.ru/wiki/index.php?title=Perceptrons_%281969%29»