WikiSort.ru - Не сортированное

Машинное обучение и data mining

Задачи Задача классификации Обучение без учителя Обучение с частичным привлечением учителя Регрессионный анализ AutoML Ассоциативные правила Выделение признаков Обучение признакам Обучение ранжированию Грамматический вывод Онлайновое обучение

Обучение с учителем Метод k-ближайших соседей Наивный байесовский классификатор Дерево решений Метод опорных векторов Линейная регрессия Логистическая регрессия Перцептрон Ансамбли моделей (Бэггинг, Бустинг, Random forest) Метод релевантных векторов

Кластерный анализ Метод k-средних Метод нечёткой кластеризации Иерархическая кластеризация EM-алгоритм BIRCH CURE DBSCAN OPTICS Mean-shift

Снижение размерности Факторный анализ Метод главных компонент CCA ICA LDA Неотрицательное матричное разложение t-SNE

Структурное прогнозирование Графовая вероятностная модель (Байесовская сеть, Скрытая марковская модель, CRF)

Выявление аномалий Метод k-ближайших соседей Локальный уровень выброса

Графовые вероятностные модели Байесовская сеть Марковская сеть Скрытая марковская модель

Искусственные нейронные сети Ограниченная машина Больцмана Самоорганизующаяся карта Функция активации (Сигмоида, Softmax, Радиально-базисная функция) Метод обратного распространения ошибки Глубокое обучение Многослойный перцептрон Рекуррентная нейронная сеть (Долгая краткосрочная память, Управляемый рекуррентный блок) Свёрточная нейронная сеть (U-Net) Автокодировщик

Обучение с подкреплением Марковский процесс Уравнение Беллмана Жадный алгоритм Q-learning SARSA Temporal difference (TD)

Теория Теория Вапника — Червоненкиса Дилемма смещения–дисперсии Теория вычислительного обучения Минимизация эмпирического риска Оккамово обучение PAC learning Статистическая теория обучения

Журналы и конференции NIPS ICML ML JMLR ArXiv:cs.LG

Глоссарий Глоссарий по машинному обучению

Статьи по теме List of datasets for machine-learning research Outline of machine learning

Вероятностно приблизительно корректное обучение (ВПК обучение, англ. Probably Approximately Correct learning, (PAC learning) в теории вычислительного обучения — это схема математического анализа машинного обучения. Схему предложил в 1984 Лесли Вэлиант^[1].

В этой схеме учитель получает выборки и должен выбрать обобщающую функцию (называемую гипотезой) из определённого класса возможных функций. Целью является функция, которая с большой вероятностью (откуда «вероятностно» в названии) будет иметь низкую ошибку обобщения^[en] (откуда «приблизительно корректное» в названии). Учитель должен быть способен обучить концепт^[2], дающее произвольный коэффициент аппроксимации, вероятность успеха или распределения выборок.

Модель была позднее расширена для обработки шума (некорректно классифицируемых выборок).

Важным нововведением схемы ВПК является введение концептов вычислительной сложности машинного обучения. В частности, ожидается, что учитель находит эффективные функции (которые ограничены по времени выполнения и требуемому пространству многочленом от размера выборки), и учитель должен реализовать эффективную процедуру (запрашивая размер примера, ограниченный многочленом от размера концепта, модифицированного границами приближения и правдоподобия).

Определения и терминология

Чтобы дать определение для объекта, который является ВПК-обучаемым, нам сначала следует ввести некоторые термины^[3][4].

Для последующих определений используется два примера. Первым примером является задача распознавания символов по заданному массиву закодированного ${\displaystyle n}$ битами бинарного изображения. Вторым примером является задача нахождения интервала, который корректно классифицирует точки внутри интервала как положительные и вне интервала как отрицательные.

Пусть ${\displaystyle X}$ будет множеством, которое называется признаковым пространством или кодировкой всех выборок. В задаче распознавания символов признаковым пространством является ${\displaystyle X=\{0,1\}^{n}}$ . В задаче нахождения интервала признаковым пространством является множество всех ограниченных интервалов в ${\displaystyle \mathbb {R} }$ (здесь ${\displaystyle \mathbb {R} }$ означает множество всех вещественных чисел).

Концепт — подмножество ${\displaystyle c\subset X}$ . Один из концептов — множество всех последовательностей бит в ${\displaystyle X=\{0,1\}^{n}}$ , которые кодируют рисунок буквы «P». Примером концепта для второго примера служит множество открытых интервалов, ${\displaystyle \{(a,b)\mid 0\leq a\leq \pi /2,\pi \leq b\leq {\sqrt {13}}\}}$ , каждый из которых содержит только положительные точки. Класс концептов^[en] ${\displaystyle C}$ — это множество концептов над ${\displaystyle X}$ . Это может быть множество всех подмножеств каркасного^[en] 4-связного^[en] массива бит (ширина фонта равна 1).

Пусть ${\displaystyle EX(c,D)}$ будет процедурой, которая рисует пример ${\displaystyle x}$ с помощью вероятностного распределения ${\displaystyle D}$ и даёт правильную метку ${\displaystyle c(x)}$ , которая равна 1, если ${\displaystyle x\in c}$ и 0 в противном случае.

Теперь, если дано ${\displaystyle 0<\epsilon ,\delta <1}$ , предположим, что есть алгоритм ${\displaystyle A}$ и многочлен ${\displaystyle p}$ от ${\displaystyle 1/\epsilon ,1/\delta }$ (и другие относящиеся к делу параметры класса ${\displaystyle C}$ ) такие, что, если дана выборка размера p, нарисованный согласно ${\displaystyle EX(c,D)}$ , то с вероятностью по меньшей мере ${\displaystyle 1-\delta }$ выход алгоритма ${\displaystyle A}$ является гипотеза ${\displaystyle h\in C}$ , которая имеет среднюю ошибку, меньшую или равную ${\displaystyle \epsilon }$ на ${\displaystyle X}$ для одного и того же распределения ${\displaystyle D}$ . Далее, если утверждение выше для алгоритма ${\displaystyle A}$ верно для любого концепта ${\displaystyle c\in C}$ и для любого распределения ${\displaystyle D}$ над ${\displaystyle X}$ и для всех ${\displaystyle 0<\epsilon ,\delta <1}$ , тогда ${\displaystyle C}$ является (эффективно) ВПК обучаемым (или свободным от распределения ВПК обучаемым). Мы также можем сказать, что ${\displaystyle A}$ является алгоритмом ВПК обучения для ${\displaystyle C}$ .

Эквивалентность

При определённых условиях регулярности эти три условия эквивалентны:

1. Класс понятий C является ВПК обучаемым.
2. Размерность Вапника — Червоненкиса класса C конечна.
3. C является однородным классом Гливенко — Кантелли.

См. также

• Машинное обучение
• Data mining
• Отказоустойчивость (ВПК обучение)^[en]
• Сложность выборки^[en]

Примечания

Литература

Литература для дальнейшего чтения

• D. Haussler. Overview of the Probably Approximately Correct (PAC) Learning Framework. An introduction to the topic.
• L. Valiant. Probably Approximately Correct. Basic Books, 2013. В книге Валиант обсуждает, как ВПК обучение описывает, каким образом организмы развиваются и учатся.

Для улучшения этой статьи желательно: Проверить качество перевода с иностранного языка. Исправить статью согласно стилистическим правилам Википедии.