Изучение пространства версий - Version space learning - Wikipedia

Пространство версий для "прямоугольного" языка гипотез в двух измерениях. Зеленые плюсы - положительные примеры, а красные кружки - отрицательные. ГБ - это максимально Общее граница положительной гипотезы, а SB - максимально специфический граница положительной гипотезы. Промежуточные (тонкие) прямоугольники представляют гипотезы в пространстве версий.

Изучение пространства версий это логичный подход к машинное обучение, конкретно двоичная классификация. Алгоритмы обучения пространства версий ищут заранее заданное пространство гипотезы, рассматриваемый как набор логические предложения. Формально пространство гипотез - это дизъюнкция^[1]

${\displaystyle H_{1}\lor H_{2}\lor ...\lor H_{n}}$

(т.е. либо гипотеза 1 верна, либо гипотеза 2, либо любое подмножество гипотез с 1 по п). Алгоритм обучения пространству версий представлен с примерами, которые он будет использовать для ограничения пространства своих гипотез; для каждого примера Икс, гипотезы, которые непоследовательный с Икс удалены из пространства.^[2] Это итеративное уточнение пространства гипотез называется исключение кандидата алгоритма, пространство гипотез поддерживается внутри алгоритма его пространство версий.^[1]

Алгоритм пространства версий

В условиях, когда гипотезы упорядочиваются по общности, пространство версий можно представить двумя наборами гипотез: (1) наиболее конкретный непротиворечивые гипотезы, и (2) самый общий согласованные гипотезы, где «согласованный» означает согласие с наблюдаемыми данными.

Наиболее конкретные гипотезы (т.е. конкретная граница SB) охватывают наблюдаемые положительные примеры тренировок и как минимум пространство функций насколько возможно. Эти гипотезы, если их продолжить, исключать а положительный пример обучения, и, следовательно, становятся непоследовательными. Эти минимальные гипотезы по сути представляют собой (пессимистическое) утверждение, что истинное понятие определяется просто положительный данные, которые уже наблюдались: Таким образом, если наблюдаются новые (ранее неизвестные) данные, их следует считать отрицательными. (То есть, если данные ранее не были исключены, это исключено.)

Наиболее общие гипотезы (т. Е. Общая граница ГБ) охватывают наблюдаемые положительные обучающие примеры, но также покрывают оставшееся пространство функций без включения каких-либо отрицательных обучающих примеров. Эти, если их еще увеличить, включают а отрицательный пример обучения, и, следовательно, становятся непоследовательными. Эти максимальные гипотезы, по сути, составляют (оптимистическое) утверждение, что истинное понятие определяется только отрицательный данные, которые уже наблюдались: Таким образом, если наблюдается новая (никогда ранее не наблюдаемая) точка данных, ее следует считать положительной. (То есть, если данные ранее не были исключены, они исключены.)

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

После обучения классификация может быть выполнена на невидимых примерах путем проверки гипотезы, полученной алгоритмом. Если пример согласуется с несколькими гипотезами, можно применить правило большинства голосов.^[1]

Историческое прошлое

Понятие пространств версий было введено Митчеллом в начале 1980-х годов.^[2] как основу для понимания основной проблемы обучения с учителем в контексте поиск решения. Хотя основной "исключение кандидата"Метод поиска, который сопровождает структуру пространства версий, не является популярным алгоритмом обучения, есть некоторые практические реализации, которые были разработаны (например, Sverdlik & Reynolds 1992, Hong & Tsang 1997, Dubois & Quafafou 2002).

Основным недостатком обучения пространству версий является его неспособность справиться с шумом: любая пара несовместимых примеров может привести к тому, что пространство версий крах, т.е. стать пустым, так что классификация становится невозможной.^[1] Одно решение этой проблемы предложено Дюбуа и Квафафу, которые предложили пространство грубых версий^[3], где приближения на основе грубых множеств используются для изучения определенных и возможных гипотез при наличии противоречивых данных.

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

• Формальный анализ концепции
• Индуктивное логическое программирование
• Грубый набор. [Основа приблизительного набора ориентирована на случай, когда двусмысленность вводится неимущими набор функций. То есть целевая концепция не может быть описана однозначно, потому что доступный набор функций не позволяет однозначно определить объекты, принадлежащие к разным категориям. Структура пространства версий фокусируется на (классической индукции) случае, когда неоднозначность вводится обеднением набор данных. То есть целевая концепция не может быть определена, потому что доступные данные не могут однозначно выбрать гипотезу. Естественно, оба типа двусмысленности могут возникать в одной и той же задаче обучения.]
• Индуктивное мышление. [Об общей проблеме индукции.]

Рекомендации

1. Рассел, Стюарт; Норвиг, Питер (2003) [1995]. Искусственный интеллект: современный подход (2-е изд.). Прентис Холл. С. 683–686. ISBN  978-0137903955.
2. Митчелл, Том М. (1982). «Обобщение как поиск». Искусственный интеллект. 18 (2): 203–226. Дои:10.1016/0004-3702(82)90040-6.
3. Дюбуа, Винсент; Куафафу, Мохамед (2002). «Концептуальное обучение с приближением: приблизительные пространства версий». Приблизительные наборы и текущие тенденции в вычислительной технике: материалы третьей международной конференции, RSCTC 2002. Малверн, Пенсильвания. С. 239–246. Дои:10.1007/3-540-45813-1_31.

• Хонг, Цзунг-Пай; Шиан-Шионг Цанг (1997). «Обобщенный алгоритм обучения пространству версий для зашумленных и неопределенных данных». IEEE Transactions по разработке знаний и данных. 9 (2): 336–340. Дои:10.1109/69.591457.
• Митчелл, Том М. (1997). Машинное обучение. Бостон: Макгроу-Хилл.
• Свердлик, З .; Рейнольдс, Р. (1992). «Динамические пространства версий в машинном обучении». Труды Четвертой Международной конференции по инструментам с искусственным интеллектом (TAI '92). Арлингтон, Вирджиния. С. 308–315.