Трансдуктивное обучение

Трансдуктивное обучение (англ. transductive learning, трансдукция) — это парадигма машинного обучения, при которой выводы о метках конкретных тестовых примеров делаются непосредственно на основе доступных обучающих данных, минуя этап построения общей предсказательной модели (функции).

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

Определение и основная идея

Традиционное машинное обучение (индуктивное) работает в два этапа: 1. По обучающей выборке строится универсальное правило (модель). 2. Это правило применяется к новым, ранее не виданным данным для получения прогноза.

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

Схематическое сравнение:

Индукция: $X_{train} \rightarrow f(x) \rightarrow \text{Прогнозы для } X_{test}$
Трансдукция: $(X_{train}, X_{test}) \rightarrow \text{Прогнозы для } X_{test}$

Мотивация

Главная мотивация трансдуктивного подхода элегантно сформулирована его создателем, Владимиром Вапником: Шаблон:Цитата

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

Историческая справка

Понятие трансдукции было введено советским и американским математиком Владимиром Вапником в 1990-х годах в рамках развития статистической теории обучения (Vapnik–Chervonenkis theory). Наиболее полно эта концепция была описана в его фундаментальном труде «The Nature of Statistical Learning Theory» (1995) [1].

Вапник аргументировал, что классическая статистика часто заставляет исследователей решать задачу восстановления плотности распределения или регрессионную задачу (сложные, некорректно поставленные задачи) только для того, чтобы в итоге классифицировать несколько объектов. Трансдукция была предложена как прямой путь к ответу. Ранее похожие идеи витали в математической статистике под терминами вроде «квази-индукции», но строгую формализацию в контексте машинного обучения они получили именно благодаря Вапнику.

Математическая постановка

Пусть задана обучающая выборка X_train, состоящая из n пар «объект — ответ»:

$X_{train} = \{(x_1, y_1), (x_2, y_2), \dots, (x_n, y_n)\}$

где $x_i \in \mathbb{R}^d$ , а метки классов $y_i \in \{-1, 1\}$ (для задачи бинарной классификации).

Также задана тестовая выборка X_test, состоящая из m объектов без меток:

$X_{test} = \{x_{n+1}, x_{n+2}, \dots, x_{n+m}\}$

Задача трансдукции: найти такой вектор меток $Y_{test} = (y_{n+1}, \dots, y_{n+m})$ для тестовой выборки, который минимизирует ожидаемую ошибку на этой конкретной выборке.

Вместо минимизации классического эмпирического риска для поиска общей функции $f(x)$ , трансдуктивные алгоритмы часто минимизируют совместный функционал, который штрафует за ошибки на обучающей выборке и одновременно накладывает структурные ограничения (регуляризацию) на метки тестовой выборки, опираясь на её топологию.

Основные подходы и алгоритмы

Трансдуктивная машина опорных векторов (TSVM)

Является классическим примером трансдукции. В стандартном SVM разделяющая гиперплоскость строится только по размеченным данным. TSVM (предложенная Т. Йоахимсом в 1999 г. [2]) ищет такую гиперплоскость и такую разметку для X_test, при которой зазор (margin) между классами будет максимальным с учетом обеих выборок. Это реализует предположение о том, что граница классов должна проходить через области низкой плотности распределения данных. Формально TSVM минимизирует норму весов $\|w\|^2$ при условии правильной классификации X_train и принудительного разнесения объектов X_test как можно дальше от границы принятия решения (независимо от того, какой класс им будет присвоен).

Графовые методы (Graph-based methods)

Данные (как X_train, так и X_test) представляются в виде вершин графа. Ребра между вершинами отражают степень сходства объектов (например, на основе RBF-ядра). Затем метки «растекаются» (Label Propagation [3]) от размеченных узлов к неразмеченным вдоль ребер с наибольшим весом. Это чистая трансдукция, так как функция предсказания вне вершин графа не строится.

Машина Байесовых Комитетов (Bayesian Committee Machine, BCM)

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

Связь с другими парадигмами

Полуавтоматическое обучение (Semi-supervised learning, SSL): Наиболее близкая концепция. Разница тонка, но фундаментальна: SSL использует неразмеченные данные для построения индуктивной (глобальной) модели, которая затем сможет классифицировать любые новые, неизвестные на этапе обучения объекты. Трансдукция же использует неразмеченные данные только для того, чтобы разметить именно их. Многие алгоритмы (например, TSVM) можно использовать в обоих режимах, но их математическая цель различна.
Активное обучение: В активном обучении алгоритм сам выбирает, какие объекты из неразмеченной выборки нужно передать эксперту (оракулу) для получения метки. Трансдукция не запрашивает новые метки у человека, а делает выводы самостоятельно.
Обучение без учителя (Кластеризация): Трансдукцию можно рассматривать как кластеризацию (или обучение многообразиям), которая «заякорена» (constrained) небольшим количеством известных меток классов из обучающей выборки.

Преимущества и ограничения

Преимущества:

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

Ограничения и критика:

Противоречивость прогнозов: Если мы добавим к тестовой выборке $X_{test}$ еще один набор данных $X'_{test}$ и запустим трансдукцию заново, метки для изначального $X_{test}$ могут измениться. Граница принятия решения смещается адаптивно под любую подаваемую геометрию множества. Модель нельзя «сохранить на диск» и применять поштучно к новым объектам в реальном времени.
Вычислительная сложность: TSVM требует решения задачи смешанного целочисленного программирования. С ростом размера тестовой выборки задача становится NP-трудной, требуя тяжелых эвристических приближений, что снижает практическую изящность изначальной идеи.

Практические применения

Классификация текстов и веб-страниц: Зачастую у нас есть полная база документов (например, весь корпус статей или весь текущий индекс сайта), но размечена вручную лишь малая часть. Нам не нужно классифицировать тексты, которые появятся через 10 лет, нам нужно качественно разметить текущую базу.
Биоинформатика: Анализ экспрессии генов, где эксперименты (микрочипы) дороги, размеченных профилей мало, а новые данные пациентов поступают крупными партиями (батчами).
Компьютерное зрение (Image Retrieval): Поиск похожих изображений в конечной и фиксированной базе данных.

Критика и альтернативы

В современной индустрии машинного обучения индуктивный подход доминирует. Это связано с тем, что большинство коммерческих систем требуют потоковой обработки данных (онлайн-инференс), когда предсказание нужно выдавать мгновенно для одного пришедшего пользователя. Пересчитывать трансдуктивный баланс ради каждого нового объекта вычислительно нецелесообразно. Тем не менее, идеи Вапника о недопустимости решения избыточно общих задач легли в основу современных методов адаптации доменов (Domain Adaptation) и малоресурсного обучения (Few-shot Learning).

Заключение

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

Литература

[1] Vapnik, V. N. (1995). The Nature of Statistical Learning Theory. Springer-Verlag.

[2] Joachims, T. (1999). Transductive Inference for Text Classification using Support Vector Machines. ICML.

[3] Zhu, X. (2005). Semi-Supervised Learning Literature Survey. Computer Sciences, University of Wisconsin-Madison.

[4] Chapelle, O., Schölkopf, B., & Zien, A. (2006). Semi-Supervised Learning. MIT Press.

Ссылки

Трансдуктивное обучение на MachineLearning.ru

Полный промпт, использованный при создании этой статьи, доступен на странице обсуждения.

Источник — «http://recognition.su/wiki/index.php?title=%D0%A2%D1%80%D0%B0%D0%BD%D1%81%D0%B4%D1%83%D0%BA%D1%82%D0%B8%D0%B2%D0%BD%D0%BE%D0%B5_%D0%BE%D0%B1%D1%83%D1%87%D0%B5%D0%BD%D0%B8%D0%B5»

Категории: Прикладная статистика | Машинное обучение

@@ Строка 1: / Строка 1: @@
-В отличии от индукции, являющейся рассуждением от частного (наблюдаемых объектов обучения) к общему (закономерностям общего характера), '''трансдукцией''' называют выводы о частных случаях (тестовых данных) на основании частных случаев (данных обучения).
+{{well|Статья написана с использованием LLM '''Gemini''' и проверена участником ~~Ilia Vdovin~~}}
-Различия между этими методами построения выводов особенно интересны, когда прогноз, полученный с помощью трансдуктивной модели, невозможно получить, используя модель индуктивную.
-Заметим, что подобные ситуации возникают, когда в результате трансдутивного вывода на различных тестовых наборах получаются взаимно противоречивые прогнозы.
-Понятие трансдукции было введено [[Вапник, Владимир Наумович|Владимиром Вапником]] в девяностых годах двадцатого века.
+== Трансдуктивное обучение ==
-По мнению Вапника трансдукция может быть отнесена к индукции, поскольку индукция требует решения общей задачи (восстановления функции) перед решением задачи более конкретной (вычисление результатов для новых объектов):
-«Решая интересующую Вас задачу, не стоит решать более общую задачу на промежуточном шаге.
-Постарайтесь получить ответ, который Вам действительно нужен, а не более общий.»
-Примером обучения, не являющегося индуктивным, может быть случай двоичной классификации, в котором входные данные склонны разделяться на две группы.
+'''Трансдуктивное обучение''' (англ. ''transductive learning'', ''трансдукция'') — это парадигма [[Машинное обучение|машинного обучения]], при которой выводы о метках конкретных тестовых примеров делаются непосредственно на основе доступных обучающих данных, минуя этап построения общей предсказательной модели (функции).
-Большой объём контрольных данных может помочь в поиске кластеров, давая полезную информацию о метках классов.
-Те же выводы не могут быть достигнуты с помощью модели, восстанавливающей функцию лишь на основании обучающей выборки.
-Может показаться, что это пример тесно связанного с трансдукцией [[Частичное обучение|частичного обучения]], но у Вапника была несколько иная мотивация.
-Примером алгоритма этой категории может послужить трансдуктивная [[машина опорных векторов]] (Transductive Support Vector Machine, TSVM).
-Третья возможная причина, ведущая к трансдукции, возникает при необходимости в приближении.
+В отличие от [[Индукция (логика)|индукции]], которая представляет собой рассуждение от частного (наблюдаемых объектов обучения) к общему (глобальным закономерностям и функциям), трансдукция — это рассуждение от частного к частному. Различия между этими методами особенно интересны в ситуациях, когда прогноз, полученный с помощью трансдуктивной модели, невозможно или вычислительно крайне сложно получить, используя традиционную индуктивную модель. Подобные ситуации возникают, когда в результате трансдуктивного вывода на различных тестовых наборах получаются взаимно противоречивые прогнозы из-за изменения состава и геометрии самого тестового множества.
-Если построение точного ответа вычислительно невозможно, то можно по крайней мере попытаться убедиться в том, что приближения хороши на тестовых данных.
-В этом случае тестовые данные могут иметь произвольное распределение (необязательно связанное с распределением обучающих данных), что недопустимо в случае частичного обучения.
+== Определение и основная идея ==
-Примером алгоритма, подпадающего под эту категорию, может является Машина Байесовых Комитетов (Bayesian Committee Machine, BCM).
+Традиционное машинное обучение (индуктивное) работает в два этапа:
+. По обучающей выборке строится универсальное правило (модель).
+. Это правило применяется к новым, ранее не виданным данным для получения прогноза.
+Трансдуктивное обучение объединяет эти два этапа в один. На вход алгоритму одновременно подаются как размеченные обучающие данные, так и ''неразмеченные тестовые данные'', для которых необходимо получить ответ. Алгоритм анализирует структуру всей совокупности данных и выдает метки только для предоставленного тестового множества, не гарантируя корректную работу с любыми другими потенциальными данными в будущем.
+Схематическое сравнение:
+* '''Индукция:''' <tex>X_{train} \rightarrow f(x) \rightarrow \text{Прогнозы для } X_{test}</tex>
+* '''Трансдукция:''' <tex>(X_{train}, X_{test}) \rightarrow \text{Прогнозы для } X_{test}</tex>
+== Мотивация ==
+Главная мотивация трансдуктивного подхода элегантно сформулирована его создателем, [[Вапник, Владимир Наумович|Владимиром Вапником]]:
+{{Цитата|Решая интересующую Вас задачу, не стоит решать более общую задачу на промежуточном шаге. Постарайтесь получить ответ, который Вам действительно нужен, а не более общий.}}
+Построение глобальной функции (индукция) — математически более сложная задача, чем классификация конечного набора точек. Кроме того, сами тестовые данные, даже без меток, несут колоссальный объем информации о геометрической структуре пространства признаков. Наблюдая, как тестовые данные распределены в пространстве (например, образуют ли они плотные кластеры), трансдуктивный алгоритм может провести разделяющую гиперплоскость в местах наименьшей плотности данных, что невозможно сделать, опираясь только на малочисленную обучающую выборку.
+== Историческая справка ==
+Понятие трансдукции было введено советским и американским математиком Владимиром Вапником в 1990-х годах в рамках развития статистической теории обучения (Vapnik–Chervonenkis theory). Наиболее полно эта концепция была описана в его фундаментальном труде ''«The Nature of Statistical Learning Theory»'' (1995) [1].
+Вапник аргументировал, что классическая статистика часто заставляет исследователей решать задачу восстановления плотности распределения или регрессионную задачу (сложные, некорректно поставленные задачи) только для того, чтобы в итоге классифицировать несколько объектов. Трансдукция была предложена как прямой путь к ответу. Ранее похожие идеи витали в математической статистике под терминами вроде «квази-индукции», но строгую формализацию в контексте машинного обучения они получили именно благодаря Вапнику.
+== Математическая постановка ==
+Пусть задана обучающая выборка '''X<sub>train</sub>''', состоящая из '''n''' пар «объект — ответ»:
+<tex>X_{train} = \{(x_1, y_1), (x_2, y_2), \dots, (x_n, y_n)\}</tex>
+где <tex>x_i \in \mathbb{R}^d</tex>, а метки классов <tex>y_i \in \{-1, 1\}</tex> (для задачи бинарной классификации).
+Также задана тестовая выборка '''X<sub>test</sub>''', состоящая из '''m''' объектов без меток:
+<tex>X_{test} = \{x_{n+1}, x_{n+2}, \dots, x_{n+m}\}</tex>
+'''Задача трансдукции:''' найти такой вектор меток <tex>Y_{test} = (y_{n+1}, \dots, y_{n+m})</tex> для тестовой выборки, который минимизирует ожидаемую ошибку на этой конкретной выборке.
+Вместо минимизации классического [[Эмпирический риск|эмпирического риска]] для поиска общей функции <tex>f(x)</tex>, трансдуктивные алгоритмы часто минимизируют совместный функционал, который штрафует за ошибки на обучающей выборке и одновременно накладывает структурные ограничения (регуляризацию) на метки тестовой выборки, опираясь на её топологию.
+== Основные подходы и алгоритмы ==
+* '''Трансдуктивная машина опорных векторов (TSVM)'''
+Является классическим примером трансдукции. В стандартном [[Метод опорных векторов|SVM]] разделяющая гиперплоскость строится только по размеченным данным. TSVM (предложенная Т. Йоахимсом в 1999 г. [2]) ищет такую гиперплоскость и такую разметку для '''X<sub>test</sub>''', при которой зазор (margin) между классами будет максимальным с учетом ''обеих'' выборок. Это реализует предположение о том, что граница классов должна проходить через области низкой плотности распределения данных.
+Формально TSVM минимизирует норму весов <tex>\|w\|^2</tex> при условии правильной классификации '''X<sub>train</sub>''' и принудительного разнесения объектов '''X<sub>test</sub>''' как можно дальше от границы принятия решения (независимо от того, какой класс им будет присвоен).
+* '''Графовые методы (Graph-based methods)'''
+Данные (как '''X<sub>train</sub>''', так и '''X<sub>test</sub>''') представляются в виде вершин графа. Ребра между вершинами отражают степень сходства объектов (например, на основе RBF-ядра). Затем метки «растекаются» (Label Propagation [3]) от размеченных узлов к неразмеченным вдоль ребер с наибольшим весом. Это чистая трансдукция, так как функция предсказания вне вершин графа не строится.
+* '''Машина Байесовых Комитетов (Bayesian Committee Machine, BCM)'''
+Возникает при необходимости в робастной аппроксимации. Если построение точного байесовского вывода вычислительно невозможно на огромных массивах данных, данные разбиваются на части. На каждой части строится свой алгоритм, а их прогнозы объединяются (комитет). Веса для объединения прогнозов в BCM вычисляются с использованием распределения ''тестовых'' данных. В этом случае тестовые данные могут иметь произвольное распределение, необязательно совпадающее с обучающим.
+== Связь с другими парадигмами ==
+* '''[[Полуавтоматическое обучение]] (Semi-supervised learning, SSL):''' Наиболее близкая концепция. Разница тонка, но фундаментальна: SSL использует неразмеченные данные для построения ''индуктивной'' (глобальной) модели, которая затем сможет классифицировать любые новые, неизвестные на этапе обучения объекты. Трансдукция же использует неразмеченные данные только для того, чтобы разметить ''именно их''. Многие алгоритмы (например, TSVM) можно использовать в обоих режимах, но их математическая цель различна.
+* '''[[Активное обучение]]:''' В активном обучении алгоритм сам выбирает, какие объекты из неразмеченной выборки нужно передать эксперту (оракулу) для получения метки. Трансдукция не запрашивает новые метки у человека, а делает выводы самостоятельно.
+* '''[[Обучение без учителя]] (Кластеризация):''' Трансдукцию можно рассматривать как кластеризацию (или обучение многообразиям), которая «заякорена» (constrained) небольшим количеством известных меток классов из обучающей выборки.
+== Преимущества и ограничения ==
+'''Преимущества:'''
+# '''Выигрыш при малых выборках:''' Если размеченных данных мало, а тестовых много, трансдукция дает значительный прирост точности за счет использования неявной информации из распределения тестовой выборки.
+# '''Прямое решение:''' Избегание проклятия размерности, присущего индуктивному восстановлению сложной многомерной функции.
+'''Ограничения и критика:'''
+# '''Противоречивость прогнозов:''' Если мы добавим к тестовой выборке <tex>X_{test}</tex> еще один набор данных <tex>X'_{test}</tex> и запустим трансдукцию заново, метки для изначального <tex>X_{test}</tex> могут измениться. Граница принятия решения смещается адаптивно под любую подаваемую геометрию множества. Модель нельзя «сохранить на диск» и применять поштучно к новым объектам в реальном времени.
+# '''Вычислительная сложность:''' TSVM требует решения задачи смешанного целочисленного программирования. С ростом размера тестовой выборки задача становится '''NP'''-трудной, требуя тяжелых эвристических приближений, что снижает практическую изящность изначальной идеи.
+== Практические применения ==
+* '''Классификация текстов и веб-страниц:''' Зачастую у нас есть полная база документов (например, весь корпус статей или весь текущий индекс сайта), но размечена вручную лишь малая часть. Нам не нужно классифицировать тексты, которые появятся через 10 лет, нам нужно качественно разметить текущую базу.
+* '''Биоинформатика:''' Анализ экспрессии генов, где эксперименты (микрочипы) дороги, размеченных профилей мало, а новые данные пациентов поступают крупными партиями (батчами).
+* '''Компьютерное зрение (Image Retrieval):''' Поиск похожих изображений в конечной и фиксированной базе данных.
+== Критика и альтернативы ==
+В современной индустрии машинного обучения индуктивный подход доминирует. Это связано с тем, что большинство коммерческих систем требуют потоковой обработки данных (онлайн-инференс), когда предсказание нужно выдавать мгновенно для одного пришедшего пользователя. Пересчитывать трансдуктивный баланс ради каждого нового объекта вычислительно нецелесообразно. Тем не менее, идеи Вапника о недопустимости решения избыточно общих задач легли в основу современных методов адаптации доменов (Domain Adaptation) и малоресурсного обучения (Few-shot Learning).
+== Заключение ==
+Трансдуктивное обучение — это мощный теоретический концепт, напоминающий нам о том, что в машинном обучении не всегда нужно строить всеобъемлющие модели мироздания. Несмотря на то, что чистая трансдукция применяется в продакшене реже индуктивных нейросетей, её математические принципы прочно закрепились в современных графовых алгоритмах и методах глубокого обучения с частичным привлечением учителя.
+== Литература ==
+[1] Vapnik, V. N. (1995). ''The Nature of Statistical Learning Theory''. Springer-Verlag.
+[2] Joachims, T. (1999). Transductive Inference for Text Classification using Support Vector Machines. ''ICML''.
+[3] Zhu, X. (2005). Semi-Supervised Learning Literature Survey. ''Computer Sciences, University of Wisconsin-Madison''.
+[4] Chapelle, O., Schölkopf, B., & Zien, A. (2006). ''Semi-Supervised Learning''. MIT Press.
 == Ссылки ==
-[http://en.wikipedia.org/wiki/Transductive_learning Wikipedia: Transduction]
+* [https://www.machinelearning.ru/wiki/index.php?title=Трансдуктивное_обучение Трансдуктивное обучение на MachineLearning.ru]
-== Категории ==
+[[Категория:Прикладная статистика]]
 [[Категория:Машинное обучение]]
+Полный промпт, использованный при создании этой статьи, доступен на [[Обсуждение:Трансдуктивное обучение|странице обсуждения]].

Трансдуктивное обучение

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

Версия 01:08, 2 июля 2026

Содержание