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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Consider the set of all points to be one large partition.
While any partition P contains two points with conflicting labels:
  Partition P into smaller partitions.
For each partition P:
  Assign the same label to all of the points in P.

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

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

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

Compute the pair-wise distances, D, between all the points.
Sort D in ascending order.
Consider each point to be a cluster of size 1.
For each pair of points {a,b} in D:
  If (a is unlabeled) or (b is unlabeled) or (a and b have the same label)
    Merge the two clusters that contain a and b.
    Label all points in the merged cluster with the same label.

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

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

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

Эпилогизм

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

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

Languages

In other projects