Теория вычислительного обучения

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

Версия 20:20, 21 июня 2026 (править) Polina Khadralinova (Обсуждение | вклад) ← К предыдущему изменению		Текущая версия (20:23, 21 июня 2026) (править) (отменить) Polina Khadralinova (Обсуждение | вклад) (Отмена правки № 107612 участника Polina Khadralinova (обсуждение))
Строка 1:		Строка 1:
-	{{well|Статья написана с использованием LLM '''Gemini 3.1 Pro Preview''' и проверена участником Polina Khadralinova}}	+	'''Теория вычислительного обучения''' (Computational Learning Theory, COLT) изучает методы построения и анализа алгоритмов, обучаемых по прецедентам. Она сосредоточена на получении строгих математических результатов. Основные направления исследований — [[переобучение|проблема переобучения]] и [[вычислительная сложность]] алгоритмов.
-	'''Принцип эмпирической индукции Фрэнсиса Бэкона''' в контексте [[Машинное обучение|машинного обучения]] — это философско-методологическая основа извлечения закономерностей из данных. Сформулированный в XVII веке принцип перехода от частных наблюдений (прецедентов) к общим правилам сегодня является фундаментальной парадигмой [[Обучение по прецедентам|обучения по прецедентам]], математически выраженной через [[Минимизация эмпирического риска|минимизацию эмпирического риска]] (ERM).	+	Основная международная конференция — [[Computational Learning Theory (конференция)|COLT]].
		+	Проводятся также европейские конференции [[European Conference on Computational Learning Theory (конференция)|EuroCOLT]] и [[Algorithmic Learning Theory (конференция)|ALT]].
-	С гносеологической точки зрения машинное обучение рассматривается не просто как набор алгоритмов, а как современная математическая технология автоматизации научного метода познания, у истоков которого стоял Фрэнсис Бэкон.	+	== Задачи и направления ==
-	== Исторический контекст ==	+	Теория COLT претендует на роль теоретического базиса всего [[машинное обучение|машинного обучения]].
		+	Основная задача ''теории вычислительного обучения'' — дать строгие обоснования алгоритмов обучения по прецедентам.
-	Английский философ и политик Фрэнсис Бэкон (1561–1626) в своём фундаментальном труде «Новый Органон» (1620) подверг жёсткой критике формальную дедуктивную логику Аристотеля. Бэкон утверждал, что законы природы невозможно вывести из умозрительных, абстрактных аксиом; их необходимо «расшифровывать» исключительно из фактов опыта<ref>Бэкон Ф. Новый Органон, или Истинные указания для истолкования природы. — 1620.</ref>.	+	''Алгоритм обучения'' принимает на входе конечную [[обучающая выборка|обучающую выборку]] прецедентов и настраивает модель.
		+	Настроенная (обученная) модель затем используется для предсказания будущих прецедентов.
		+	Алгоритм должен обладать свойством ''обучаемости'' в следующих двух смыслах.
-	Для систематизации наблюдений Бэкон предложил использовать так называемые «Таблицы открытия» (таблицы присутствия, отсутствия и степеней). Исследователь должен был фиксировать условия, при которых исследуемое свойство проявляется, отсутствует или меняет свою интенсивность. Исторически эти таблицы можно считать первым прообразом современных [[Выборка|обучающих выборок]] (датасетов) с признаковым описанием.	+	Во-первых, ''алгоритм обучения'' должен обладать [[обобщающая способность|способностью к обобщению]] данных.
		+	Построенная им модель должна выдавать в среднем достаточно точные предсказания будущих прецедентов.
		+	Оценки обобщающей способности, как правило, основываются на гипотезе, что прошлые и будущее прецеденты поступают случайно и независимо из одного и того же неизвестного вероятностного распределения.
		+	Эта гипотеза позволяет применить статистические методы для получения верхних оценок ожидаемой в будущем ошибки.
		+	Первые оценки были получены [[Теория Вапника-Червоненкиса|Вапником и Червоненкисом]] в конце 60-х годов.
-	== Формализация идей Бэкона в машинном обучении ==	+	Во-вторых, процесс обучения должен завершиться за приемлемое время.
		+	Обычно исследуется вопрос, является ли время обучения модели полиномиальным или экспоненциальным по длине выборки.
		+	Таким образом, проблематика вычислительного обучения тесно связана также и с вопросами вычислительной сложности алгоритмов.
-	Современная математическая постановка задачи машинного обучения является прямой алгоритмической реализацией бэконовской эмпирической индукции. «Таблица открытия» Бэкона задаётся в машинном обучении как множество прецедентов:	+	Впервые оба аспекта обучаемости были связаны воедино в теории [[Теория Валианта|вероятно почти корректного обучения]] (probably approximately correct, PAC-learning), предложенной Лесли Валиантом {{S|в работе}} 1984 года.
-	:<tex>X^\ell = \{ x_i \mid i = 1, \dots, \ell \}</tex>,	+	{{S|В дальнейших}} исследованиях они, как правило, разделялись.
-	где <tex>\ell</tex> — количество доступных наблюдений (опытов).	+
-	Свойства объектов, которые Бэкон призывал тщательно измерять и систематизировать, формализуются через измеряемые признаки (векторное представление):	+	=== Направления теории вычислительного обучения ===
-	:<tex>f_j(x)</tex> — <tex>j</tex>-й признак объекта, где <tex>j = 1, \dots, n</tex>.	+	* [[Теория Вапника-Червоненкиса]] (VC theory)
		+	* [[Теория Валианта]] (probably approximately correct learning, PAC theory)
		+	* Теория [[PAC-Bayes]] (PAC-Bayesian theory)
		+	* Оценки [[Обобщающая способность|обобщающей способности]] для различных алгоритмов обучения (generalization bounds)
		+	* Теория [[Эмпирический процесс|эмпирических процессов]] (empirical processes)
		+	* Теория [[Концентрация вероятностной меры|концентрации вероятностной меры]] (concentration inequalities)
		+	* [[Сложность данных]] (sample complexity)
		+	* [[Байесовский вывод]] (bayesian inference)
-	Цель бэконовского исследования (поиск «формы» или истинного закона) сводится к предсказанию целевого свойства <tex>y_i</tex>. Алгоритм машинного обучения автоматизирует процесс индукции, подбирая параметрическую модель <tex>a(x, w)</tex>, которая наилучшим образом обобщает частные факты из <tex>X^\ell</tex> на всё пространство объектов <tex>X</tex>.	+	=== Смежные области ===
		+	''Теория вычислительного обучения'' черпает идеи во многих разделах современной математики.
		+	* [[Теория игр]] (game theory)
		+	* [[Теория аппроксимации]] (approximation theory)
		+	* [[Вычислительная сложность]] (computational complexity)
		+	* [[Теория информации]] (information theory)
		+	* [[Криптография]] (cryptography)
-	== Машинное обучение как автоматизация научного метода ==	+	== Ссылки ==
-	Индуктивный метод Бэкона тесно связан с современными концепциями [[Эпистемология|эпистемологии]] и философии науки. В парадигме искусственного интеллекта классические шаги научного познания формализуются через строгие математические операции<ref>Воронцов К. В. Философия. Введение в ИИ (курс лекций). — 2026.</ref>:	+	* [http://hunch.net hunch.net] — хорошо структурированный блог Джона Лангфорда (John Langford).
		+	* [http://www.learningtheory.org COLT] — сайт конференций COLT.
		+	* [http://www.gaussianprocess.org Гауссовские процессы].
		+	* [http://research.microsoft.com/adapt/MSBNx/msbnx/Basics_of_Bayesian_Inference.htm Основы байесовского вывода].
-	# '''Наблюдения и измерения:''' Сбор сырых данных и формирование обучающей выборки <tex>X^\ell</tex>. Этот этап соответствует заполнению «Таблиц открытия».	+	== Литература ==
-	# '''Гипотеза (модель):''' Выбор параметрического семейства функций <tex>A = \{a(x, w) \mid w \in W\}</tex>. Модель выступает в роли научной теории, объясняющей данные.	+	#{{книга
-	# '''Принцип верифицируемости (Фрэнсис Бэкон):''' Обучение модели (train) путём оптимизации её параметров. Система ищет подтверждение гипотезы на известных данных через [[Минимизация эмпирического риска|минимизацию функции потерь]] <tex>\mathcal{L}(w, x_i)</tex>.	+	|автор = Вапник В.Н., Червоненкис А.Я.
-	# '''Принцип фальсифицируемости (Карл Поппер):''' Проверка (test) обученной модели на новых, отложенных данных. Согласно Попперу, научная теория должна допускать возможность опровержения. В машинном обучении это реализуется через процедуру [[Скользящий контроль|кросс-валидации]]: если модель показывает плохую обобщающую способность на независимом тесте (происходит [[Переобучение|переобучение]]), гипотеза (текущие веса модели) отвергается.	+	|заглавие = Теория распознавания образов
		+	|год = 1974
		+	|место = М.
		+	|издательство = Наука
		+	}}
		+	#{{книга
		+	|автор = Valiant L.G.
		+	|часть = A theory of the learnable
		+	|заглавие = Communications of the ACM
		+	|год = 1984
		+	|том = 27
		+	|страницы = 1134-1142
		+	|ссылка = http://web.mit.edu/6.435/www/Valiant84.pdf
		+	}}
		+	#{{книга
		+	|автор = Rasmussen C.E., Williams C.K.I.
		+	|заглавие = Gaussian Processes for Machine Learning
		+	|год = 2006
		+	|издательство = MIT Press
		+	|ссылка = http://www.gaussianprocess.org/gpml/chapters/
		+	|isbn = 0-262-18253-X
		+	}}
		+	#{{книга
		+	|автор = Goldman S.A.
		+	|часть = Computational Learning Theory
		+	|заглавие = Algorithms and Theory of Computation Handbook
		+	|год = 1999
		+	|издательство = CRC Press
		+	|ссылка = http://citeseer.ist.psu.edu/275016.html
		+	}}
		+	#{{книга
		+	|автор = MacKay D.
		+	|заглавие = On-line book: Information Theory, Inference, and Learning Algorithms
		+	|год = 2005
		+	|ссылка = http://www.inference.phy.cam.ac.uk/mackay/itila
		+	}}
-	Таким образом, современные алгоритмы машинного обучения выступают вычислительными инструментами, которые масштабируют философский принцип эмпирической индукции на массивы данных, объём которых недоступен для ручного анализа человеком.
-	== См. также ==
-	* [[Обучение с учителем]]
-	* [[Минимизация эмпирического риска]]
-	* [[Переобучение]]
-	* [[Скользящий контроль]]
-	== Примечания ==
-	<references/>
-
-	== Литература ==
-	* ''Бэкон Ф.'' Сочинения в двух томах. Т. 2. — М.: Мысль, 1978. (Включает «Новый Органон»).
-	* ''Воронцов К. В.'' Математические методы обучения по прецедентам (теория обучения машин). — МФТИ, 2012.
		+	{{stub}}
		+	[[Категория:Энциклопедия анализа данных]]
	[[Категория:Машинное обучение]]		[[Категория:Машинное обучение]]
-	[[Категория:Философия искусственного интеллекта]]	+	[[Категория:Теория вычислительного обучения]]

---

Текущая версия

Теория вычислительного обучения (Computational Learning Theory, COLT) изучает методы построения и анализа алгоритмов, обучаемых по прецедентам. Она сосредоточена на получении строгих математических результатов. Основные направления исследований — проблема переобучения и вычислительная сложность алгоритмов.

Основная международная конференция — COLT. Проводятся также европейские конференции EuroCOLT и ALT.

Содержание 1 Задачи и направления 1.1 Направления теории вычислительного обучения 1.2 Смежные области 2 Ссылки 3 Литература

Задачи и направления

Теория COLT претендует на роль теоретического базиса всего машинного обучения. Основная задача теории вычислительного обучения — дать строгие обоснования алгоритмов обучения по прецедентам.

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

Во-первых, алгоритм обучения должен обладать способностью к обобщению данных. Построенная им модель должна выдавать в среднем достаточно точные предсказания будущих прецедентов. Оценки обобщающей способности, как правило, основываются на гипотезе, что прошлые и будущее прецеденты поступают случайно и независимо из одного и того же неизвестного вероятностного распределения. Эта гипотеза позволяет применить статистические методы для получения верхних оценок ожидаемой в будущем ошибки. Первые оценки были получены Вапником и Червоненкисом в конце 60-х годов.

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

Впервые оба аспекта обучаемости были связаны воедино в теории вероятно почти корректного обучения (probably approximately correct, PAC-learning), предложенной Лесли Валиантом в работе 1984 года. В дальнейших исследованиях они, как правило, разделялись.

Направления теории вычислительного обучения

• Теория Вапника-Червоненкиса (VC theory)
• Теория Валианта (probably approximately correct learning, PAC theory)
• Теория PAC-Bayes (PAC-Bayesian theory)
• Оценки обобщающей способности для различных алгоритмов обучения (generalization bounds)
• Теория эмпирических процессов (empirical processes)
• Теория концентрации вероятностной меры (concentration inequalities)
• Сложность данных (sample complexity)
• Байесовский вывод (bayesian inference)

Смежные области

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

• Теория игр (game theory)
• Теория аппроксимации (approximation theory)
• Вычислительная сложность (computational complexity)
• Теория информации (information theory)
• Криптография (cryptography)

Ссылки

• hunch.net — хорошо структурированный блог Джона Лангфорда (John Langford).
• COLT — сайт конференций COLT.
• Гауссовские процессы.
• Основы байесовского вывода.

Литература

1. Вапник В.Н., Червоненкис А.Я. Теория распознавания образов. — М.: Наука, 1974.
2. Valiant L.G. A theory of the learnable // Communications of the ACM. — 1984 T. 27. — С. 1134-1142.
3. Rasmussen C.E., Williams C.K.I. Gaussian Processes for Machine Learning. — MIT Press, 2006. — ISBN 0-262-18253-X
4. Goldman S.A. Computational Learning Theory // Algorithms and Theory of Computation Handbook. — CRC Press, 1999.
5. MacKay D. On-line book: Information Theory, Inference, and Learning Algorithms. — 2005.