Полуконтролируемая машина опорных векторов (S3VM)
- Автор метода
- Joachims, T.
- Год
- 1999
- Тип
- Semi-supervised classifier
- Семейство
- Machine learning
Этот текст переведён машинным способом и ещё не проверен. Читать оригинал на английском
Что он делает?
Полуконтролируемая машина опорных векторов (S3VM) расширяет классическую SVM, включая большое количество неразмеченных данных наряду с небольшим размеченным обучающим набором.
Она ищет гиперплоскость с максимальным зазором, которая не только разделяет размеченные примеры, но и проходит через области низкой плотности полного распределения данных, обеспечивая лучшую обобщающую способность при дефиците размеченных образцов.
Интуиция метода
Стандартная SVM обучается на границе исключительно на основе размеченных точек. S3VM учитывает, что неразмеченные данные все еще несут геометрическую информацию о том, где кластеры данных плотные, а где разреженные. Требуя, чтобы граница принятия решений избегала областей высокой плотности — независимо от того, имеют ли эти точки метки или нет — модель может использовать неразмеченное большинство для повышения четкости границы, которую она иначе нарисовала бы только по нескольким размеченным примерам. Результатом является зазор, который соответствует базовой структуре данных, а не только известным меткам.
История
Основы S3VM были заложены Вапником в его ранних работах по трансдуктивному выводу, но метод получил широкое распространение после того, как Йоакимс (1999) продемонстрировал его эффективность для классификации текстов под названием Transductive SVM. Комплексное изложение в Chapelle, Scholkopf и Zien (2006) объединило S3VM с другими полуконтролируемыми подходами и остается стандартным справочным материалом. Последующие работы представили выпуклые релаксации и масштабируемые решатели для решения проблем вычислений и локальных оптимумов исходного метода.
Когда применять
S3VM — правильный выбор, когда размеченные данные дороги или редки (например, менее нескольких сотен примеров), но доступны обильные неразмеченные данные — распространенный сценарий в классификации текстов, биоинформатике или любой области, где аннотация дорога. Она работает лучше всего, когда выполняется предположение о кластеризации: классы образуют отдельные кластеры, а граница принятия решений лежит в области низкой плотности. Избегайте S3VM, когда размеченных данных уже достаточно (стандартная SVM достигнет или превзойдет ее при меньших затратах), когда предположение о кластеризации нарушено (классы сильно перекрываются в признаковом пространстве) или когда распределение неразмеченных данных отличается от распределения размеченных, что может сместить границу в неправильном направлении.
Ограничения и замечания
- Оптимизация не является выпуклой из-за псевдо-меток, что делает ее чувствительной к инициализации и склонной к локальным оптимумам.
- Вычислительная стоимость плохо масштабируется с количеством неразмеченных примеров — большие неразмеченные пулы становятся дорогими.
- Основывается на предположении о кластеризации; если классы не образуют хорошо разделенных кластеров, неразмеченные данные могут ухудшить качество.
- Требует тщательной настройки веса размеченных потерь C и веса неразмеченных потерь C*, что усложняет выбор модели.
Условия из источника не заменяют независимую научную проверку или валидацию аналитическим движком.
Сильные стороны
- Эффективно использует большие неразмеченные наборы данных для улучшения обобщающей способности при дефиците размеченных примеров.
- Наследует гарантии максимального зазора и гибкость ядер стандартных SVM.
- Хорошо подходит для разреженных данных высокой размерности, таких как текст, где обильны неразмеченные корпуса.
- Существуют принципиальные вероятностные расширения (Gaussian Process S3VM) и варианты с ядрами для нелинейных границ.
- Конкурентоспособная точность в режимах с малым количеством размеченных данных по сравнению с чисто контролируемыми альтернативами.
Применение
- Классификация текстов и документов с небольшим количеством размеченных обучающих примеров.
- Задачи биоинформатики, такие как предсказание функций белков, где экспериментальная аннотация дорога.
- Категоризация веб-страниц с использованием больших проиндексированных, но неаннотированных корпусов.
- Анализ медицинских изображений, где экспертная разметка требует много времени и затрат.
- Любая задача классификации высокой размерности с обильными неразмеченными данными и редкими метками.
Как это работает
Как это работает
Предварительная SVM подгоняется на доступных размеченных примерах, изучая предварительную границу принятия решений и зазор. Это обеспечивает стартовую модель и начальные предсказания для неразмеченного пула, основывая последующую полуконтролируемую оптимизацию на контролируемом решении.
Предварительная SVM назначает временные метки классов (псевдо-метки) всем неразмеченным примерам на основе того, по какую сторону текущей границы они находятся. Эти псевдо-метки позволяют неразмеченным точкам участвовать в максимизации зазора, даже если их истинный класс неизвестен.
Основная цель S3VM совместно минимизирует потерю шарнира на размеченных примерах и псевдо-потерю шарнира на неразмеченных примерах, одновременно максимизируя зазор. Параметр баланса C* контролирует, насколько сильно неразмеченные точки влияют на границу, балансируя между использованием структуры в неразмеченных данных и подгонкой к размеченным истинным значениям.
Формула
\min_{w,b,y^*} \frac{1}{2}\|w\|^2 + C\sum_{i}\xi_i + C^*\sum_{j}\xi_j^*Поскольку псевдо-метки могут быть ошибочными, алгоритм итерирует: он переназначает псевдо-метки, используя обновленную границу, и повторно решает совместную оптимизацию. Замена неправильно назначенных неразмеченных примеров на противоположный класс и повторная оптимизация постепенно перемещают границу в промежутки с меньшей плотностью данных.
После достижения сходимости новые примеры классифицируются по знаку изученной линейной функции принятия решений. Полученная гиперплоскость располагается в области низкой плотности полного распределения данных, обеспечивая лучшую обобщающую способность на отложенных примерах, чем чисто контролируемая SVM, обученная на том же небольшом размеченном наборе.
Формула
f(x) = \text{sign}(w^\top x + b)Частые ошибки
- Предположение, что неразмеченные данные всегда помогают — если предположение о кластеризации нарушено, S3VM может работать хуже, чем контролируемая SVM.
- Использование очень большого C* по сравнению с C, чрезмерное взвешивание неразмеченных точек и позволение границе отклоняться от размеченного сигнала.
- Пренебрежение проверкой на отложенном размеченном наборе, что делает невозможным обнаружение случаев, когда неразмеченные данные ухудшили качество.
- Применение S3VM, когда размеченные и неразмеченные данные поступают из разных распределений (сдвиг ковариат), что нарушает предположения метода.
Часто задаваемые вопросы
Чем S3VM отличается от стандартной SVM?
Стандартная SVM использует только размеченные данные для размещения своей границы принятия решений. S3VM дополнительно включает неразмеченные примеры, требуя, чтобы граница проходила через области низкой плотности полного распределения данных, улучшая обобщающую способность при дефиците размеченных данных.
Что такое предположение о кластеризации и почему оно важно?
Предположение о кластеризации гласит, что граница принятия решений лежит в области низкой плотности данных, что означает, что классы образуют разделяемые кластеры. S3VM использует это, отводя границу от плотных областей. Если классы сильно перекрываются, это предположение нарушается, и неразмеченные данные могут ввести модель в заблуждение.
Как выбрать вес неразмеченных данных C*?
C* контролирует, насколько сильно неразмеченные примеры влияют на зазор. Распространенная стратегия — начать с C* намного меньше, чем C, и постепенно увеличивать его, отслеживая точность на валидационном наборе с небольшой размеченной выборкой, останавливаясь до того, как качество ухудшится.
Может ли S3VM обрабатывать нелинейные границы?
Да. Как и стандартные SVM, S3VM поддерживает ядерные функции (RBF, полиномиальные и т. д.), которые неявно отображают данные в пространства более высокой размерности, где линейная граница становится нелинейной в исходном признаковом пространстве.
Когда следует предпочесть self-training или label propagation вместо S3VM?
Self-training проще в реализации и лучше масштабируется для больших пулов неразмеченных данных; предпочтите его, когда вычислительные ресурсы ограничены. Label propagation хорошо работает на данных с графовой структурой. S3VM предпочтительнее, когда требуются гарантии максимального зазора и предположение о кластеризации, вероятно, выполняется.
Похожие методы
Источники
Joachims, T. (1999). Transductive Inference for Text Classification using Support Vector Machines. Proceedings of the 16th International Conference on Machine Learning (ICML), 200–209.
Открыть ссылку на публикациюСкопировано.Chapelle, O., Scholkopf, B., & Zien, A. (Eds.). (2006). Semi-Supervised Learning. MIT Press.
ISBN: 978-0-262-03358-9Скопировано.