Трансдукция (машинное обучение) - Transduction (machine learning)

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

Трансдукция была введена Владимир Вапник в 1990-х годах, мотивированный своим мнением, что преобразование предпочтительнее индукции, поскольку, по его словам, индукция требует решения более общей проблемы (вывода функции) перед решением более конкретной задачи (вычисление результатов для новых случаев): «При решении интересующей проблемы, не решайте более общую проблему в качестве промежуточного шага. Постарайтесь получить ответ, который вам действительно нужен, но не более общий ». Аналогичное наблюдение было сделано ранее Бертран Рассел: «мы придем к заключению, что Сократ смертен, с большим подходом к определенности, если сделаем наш аргумент чисто индуктивным, чем если мы пойдем путем« все люди смертны »и затем воспользуемся дедукцией» (Russell 1912, глава VII).

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

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

Пример проблемы

Следующий пример задачи противопоставляет некоторые уникальные свойства трансдукции индукции.

Дан набор точек, некоторые из которых помечены (A, B или C), но большинство точек не помечены (?). Цель состоит в том, чтобы предсказать соответствующие метки для всех непомеченных точек.

Индуктивный подход к решению этой проблемы состоит в использовании помеченных точек для обучения контролируемое обучение алгоритм, а затем попросите его предсказать метки для всех непомеченных точек. Однако с этой проблемой у алгоритма контролируемого обучения будет только пять помеченных точек, которые будут использоваться в качестве основы для построения прогнозной модели. Конечно, будет сложно построить модель, отражающую структуру этих данных. Например, если используется алгоритм ближайшего соседа, то точки рядом с серединой будут помечены «A» или «C», даже если очевидно, что они принадлежат к тому же кластеру, что и точка, помеченная «B».

Преимущество трансдукции состоит в возможности учитывать все точки, а не только помеченные точки, при выполнении задачи маркировки. В этом случае трансдуктивные алгоритмы помечают немаркированные точки в соответствии с кластерами, к которым они естественным образом принадлежат. Поэтому точки в середине, скорее всего, будут помечены как «B», потому что они расположены очень близко к этому кластеру.

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

Алгоритмы трансдукции

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

Разделение трансдукции

Разделение трансдукции можно рассматривать как трансдукцию сверху вниз. Это полу-контролируемое расширение кластеризации на основе разделов. Обычно это выполняется следующим образом:

Считайте набор всех точек одним большим разделом. В то время как любой раздел P содержит две точки с конфликтующими метками: Разделите P на меньшие разделы. Для каждого раздела P: назначьте одну и ту же метку всем точкам в P.

Конечно, с этим алгоритмом можно использовать любую разумную технику разделения. Макс.расход мин. Отсек Для этого очень популярны схемы перегородок.

Агломеративная трансдукция

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

Вычислите попарные расстояния D между всеми точками. Отсортируйте D в порядке возрастания. Считайте каждую точку кластером размера 1. Для каждой пары точек {a, b} в D: Если (a не помечено) или (b не помечен) или (a и b имеют одну и ту же метку) Объединить два кластера, содержащие a и b. Обозначьте все точки в объединенном кластере одинаковой меткой.

Трансдукция в коллекторе

Трансдукция, основанная на изучении многообразия, - все еще очень молодая область исследований.

Смотрите также

Эпилогизм

внешняя ссылка

А. Гаммерман, В. Вовк, В. Вапник (1998). "Обучение путем преобразования. »Раннее объяснение трансдуктивного обучения.
"Обсуждение полу-контролируемого обучения и трансдукции, "Глава 25 Полу-контролируемое обучение, Оливье Шапель, Бернхард Шёлкопф и Александр Зиен, ред. (2006). MIT Press. Обсуждение разницы между SSL и трансдукцией.
Вафли - это библиотека алгоритмов машинного обучения C ++ с открытым исходным кодом, включая алгоритмы преобразования, а также Вафли.
SVMlight представляет собой пакет SVM общего назначения, который включает опцию преобразовательного SVM.