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