Изучение пространства версий
Обучение в пространстве версий — это логический подход к машинному обучению , в частности к двоичной классификации . Алгоритмы обучения пространству версий ищут заранее определенное пространство гипотез , рассматриваемое как набор логических предложений . Формально пространство гипотез представляет собой дизъюнкцию [1]
(т. е. либо гипотеза 1 верна, либо гипотеза 2, либо любое подмножество гипотез с 1 по n ). Алгоритм обучения пространству версий представлен с примерами, которые он будет использовать для ограничения пространства гипотез; для каждого примера x гипотезы, несовместимые с x , удаляются из пространства. [2] Это итеративное уточнение пространства гипотез называется алгоритмом исключения кандидатов , пространством гипотез, поддерживаемым внутри алгоритма, пространством его версий . [1]
Алгоритм пространства версий
[ редактировать ]В условиях, когда существует упорядочение гипотез по общности, можно представить пространство версий двумя наборами гипотез: (1) наиболее конкретными непротиворечивыми гипотезами и (2) наиболее общими непротиворечивыми гипотезами, где «согласованный» означает согласие с наблюдаемыми данными.
Наиболее конкретные гипотезы (т. е. конкретная граница SB ) охватывают наблюдаемые положительные примеры обучения и как меньше оставшегося пространства признаков можно . Эти гипотезы, если их сузить еще больше, исключают положительный . обучающий пример и, следовательно, становятся противоречивыми Эти минимальные гипотезы, по сути, представляют собой (пессимистическое) утверждение о том, что истинная концепция определяется только уже наблюдаемыми положительными данными: Таким образом, если наблюдается новая (никогда ранее не встречавшаяся) точка данных, ее следует считать отрицательной. (То есть, если данные ранее не были исключены, они исключаются.)
Наиболее общие гипотезы (т. е. общая граница GB ) охватывают наблюдаемые положительные примеры обучения, но также охватывают большую часть оставшегося пространства признаков, не включая никаких отрицательных примеров обучения. Если их расширить дальше, включают в себя отрицательный они тренировочный пример и, следовательно, становятся противоречивыми. Эти максимальные гипотезы, по сути, представляют собой (оптимистическое) утверждение о том, что истинная концепция определяется только уже наблюдаемыми отрицательными данными: Таким образом, если наблюдается новая (никогда ранее не встречавшаяся) точка данных, ее следует считать положительной. (То есть, если данные ранее не были исключены, то они включены.)
Таким образом, во время обучения пространство версий (которое само по себе представляет собой множество – возможно, бесконечное – содержащее все непротиворечивые гипотезы) может быть представлено только его нижней и верхней границей (максимально общим и максимально конкретным набором гипотез), а операции обучения могут выполняться просто на этих репрезентативных множествах.
После обучения классификацию можно выполнить на невидимых примерах путем проверки гипотезы, полученной алгоритмом. Если пример согласуется с несколькими гипотезами, можно применить правило большинства голосов. [1]
Историческая справка
[ редактировать ]Понятие пространств версий было введено Митчеллом в начале 1980-х годов. [2] как основу для понимания основной проблемы обучения с учителем в контексте поиска решения . Хотя базовый метод поиска « исключением кандидатов », который сопровождает структуру пространства версий, не является популярным алгоритмом обучения, существуют некоторые практические реализации, которые были разработаны (например, Свердлик и Рейнольдс 1992, Хонг и Цанг 1997, Дюбуа и Куафафу 2002).
Основным недостатком обучения пространства версий является его неспособность справляться с шумом: любая пара противоречивых примеров может привести к коллапсу пространства версий , то есть к его опустошению, в результате чего классификация становится невозможной. [1] Одно из решений этой проблемы было предложено Дюбуа и Кафафу, предложившими Пространство грубых версий: [3] где аппроксимации на основе грубых наборов используются для изучения определенных и возможных гипотез при наличии противоречивых данных.
См. также
[ редактировать ]- Формальный концептуальный анализ
- Индуктивное логическое программирование
- Грубый набор . [Принцип грубого набора фокусируется на случае, когда двусмысленность вносится обедненным набором функций . То есть целевую концепцию невозможно точно описать, поскольку доступный набор функций не позволяет устранить неоднозначность объектов, принадлежащих к разным категориям. Структура пространства версий фокусируется на случае (классической индукции), когда неоднозначность вносится обедненным набором данных . То есть целевую концепцию невозможно точно описать, поскольку имеющиеся данные не позволяют однозначно выделить гипотезу. Естественно, оба типа неоднозначности могут возникнуть в одной и той же задаче обучения.]
- Индуктивное рассуждение . [Об общей проблеме индукции.]
Ссылки
[ редактировать ]- ^ Jump up to: а б с д Рассел, Стюарт ; Норвиг, Питер (2003) [1995]. Искусственный интеллект: современный подход (2-е изд.). Прентис Холл. стр. 683–686. ISBN 978-0137903955 .
- ^ Jump up to: а б Митчелл, Том М. (1982). «Обобщение как поиск». Искусственный интеллект . 18 (2): 203–226. дои : 10.1016/0004-3702(82)90040-6 .
- ^ Дюбуа, Винсент; Куафафу, Мохамед (2002). «Концептуальное обучение с приближением: пространства грубых версий». Грубые множества и современные тенденции в области вычислений: материалы Третьей международной конференции, RSCTC 2002 . Малверн, Пенсильвания. стр. 239–246. дои : 10.1007/3-540-45813-1_31 .
- Хонг, Цунг-Пай; Шиан-Шён Цанг (1997). «Обобщенный алгоритм пространственного обучения версий для зашумленных и неопределенных данных». Транзакции IEEE по знаниям и инженерии данных . 9 (2): 336–340. дои : 10.1109/69.591457 . S2CID 29926783 .
- Митчелл, Том М. (1997). Машинное обучение . Бостон: МакГроу-Хилл.
- Свердлик, В.; Рейнольдс, Р.Г. (1992). «Динамические пространства версий в машинном обучении». Материалы Четвертой международной конференции по инструментам искусственного интеллекта (TAI '92) . Арлингтон, Вирджиния. стр. 308–315.