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

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

Трансдукция была введена в контекст информатики Владимиром Вапником в 1990-х годах по мотивам его точка зрения, что трансдукция предпочтительнее индукции, поскольку, по его мнению, индукция требует решение более общей задачи (вывод функции) перед решением более конкретной задачи (вычисление результатов для новых случаев): «При решении задачи В интересах не решать более общую проблему в качестве промежуточного шага. Попробуй получите ответ, который вам действительно нужен, но не более общий». ^[1].

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

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

Исторический контекст

Способ вывода от частностей к частностям, который Вапник стал называть трансдукцией, уже отличался от способа вывода от частностей к обобщениям в части III учебника кембриджского философа и логика У. Е. Джонсона 1924 года «Логика» . В работе Джонсона первый метод назывался «обучением», а второй — «индукцией». Бруно де Финетти разработал чисто субъективную форму байесианства, в которой утверждения об объективных шансах могут быть переведены в эмпирически респектабельные утверждения о субъективной достоверности в отношении наблюдаемых величин через свойства взаимозаменяемости. Раннее изложение этой точки зрения можно найти в его книге «La Prevision» 1937 года: ses Lois Logiques, ses Sources Subjectives , а более зрелое утверждение — в его «Теории вероятностей» 1970 года . В рамках субъективной байесовской структуры де Финетти любой индуктивный вывод в конечном итоге представляет собой вывод от частностей к частностям.

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

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

Дан набор точек, в котором некоторые точки помечены (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.

Многообразная трансдукция

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

См. также

Эпилогизм

Ссылки

^ Вапник, Владимир (2006). «Оценка зависимостей на основе эмпирических данных» . Информатика и статистика : 477. doi : 10.1007/0-387-34239-7 . ISBN 978-0-387-30865-4 . ISSN 1613-9011 .

Де Финетти, Бруно. «Прогнозирование: его логические законы, его субъективные источники». Анналы Института Анри Пуанкаре. Полет. 7. № 1. 1937.
де Финетти, Бруно (1970). Теория вероятностей: критическое введение. Нью-Йорк: Джон Уайли.
WE Johnson Logic, часть III , Архив CUP, 1924 г. [1]
Б. Рассел. «Проблемы философии» , Домашняя университетская библиотека, 1912. [2] .
В. Н. Вапник. Статистическая теория обучения . Нью-Йорк: Wiley, 1998. (см. стр. 339–371).
В. Тресп. Машина байесовского комитета , Neural Computation, 12, 2000, pdf .

Внешние ссылки

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

[1] Вапник, Владимир (2006). «Оценка зависимостей на основе эмпирических данных» . Информатика и статистика : 477. doi : 10.1007/0-387-34239-7 . ISBN 978-0-387-30865-4 . ISSN 1613-9011 .

[1]