Структурированная регуляризация разреженности
Структурированная регуляризация разреженности — это класс методов и область исследований в теории статистического обучения , которые расширяют и обобщают методы обучения регуляризации разреженности. [1] Методы регуляризации как разреженности, так и структурированной разреженности стремятся использовать предположение о том, что выходная переменная (т. е. ответ или зависимая переменная ), которую необходимо изучить, может быть описана уменьшенным количеством переменных во входном пространстве. (т. е. область , пространство признаков или независимых переменных ). Методы регуляризации разреженности фокусируются на выборе входных переменных, которые лучше всего описывают выходные данные. Методы структурированной регуляризации разреженности обобщают и расширяют методы регуляризации разреженности, позволяя осуществлять оптимальный выбор среди таких структур, как группы или сети входных переменных. . [2] [3]
Распространенной мотивацией для использования методов структурированной разреженности являются интерпретируемость модели, многомерное обучение (где размерность может быть больше, чем количество наблюдений ) и снижение вычислительной сложности . [4] Более того, методы структурированной разреженности позволяют включать предварительные предположения о структуре входных переменных, таких как перекрывающиеся группы, [2] непересекающиеся группы и ациклические графы. [3] Примеры использования методов структурированной разреженности включают распознавание лиц, [5] магнитно-резонансных изображений (МРТ) , обработка [6] социолингвистический анализ обработки естественного языка, [7] и анализ генетической экспрессии при раке молочной железы. [8]
Определение и связанные с ним понятия
[ редактировать ]Регуляризация разреженности
[ редактировать ]с линейным ядром Рассмотрим регуляризованную задачу минимизации эмпирического риска и функцией потерь и «норма» как штраф за регуляризацию:
где , и обозначает «норма», определяемая как количество ненулевых элементов вектора. . называется разреженным, если . Это означает, что вывод может быть описан небольшим подмножеством входных переменных.
В более общем смысле, предположим, что словарь с задана такая, что целевая функция задачи обучения можно записать так:
- ,
The норма как количество ненулевых компонентов определяется как
- , где мощность множества .
называется разреженным, если .
Однако при использовании норма регуляризации отдает предпочтение более редким решениям, ее сложно использовать в вычислительном отношении, и, кроме того, она не является выпуклой. Более осуществимой в вычислительном отношении нормой, которая отдает предпочтение более разреженным решениям, является норма; Было показано, что это по-прежнему благоприятствует более разреженным решениям и, кроме того, является выпуклым. [4]
Структурированная регуляризация разреженности
[ редактировать ]Структурированная регуляризация разреженности расширяет и обобщает проблему выбора переменных, которая характеризует регуляризацию разреженности. [2] [3] Рассмотрим приведенную выше регуляризованную задачу минимизации эмпирического риска с общим ядром и связанной с ним картой признаков. с .
Срок регуляризации наказывает каждого компонент независимо, что означает, что алгоритм будет подавлять входные переменные независимо друг от друга.
В некоторых ситуациях мы можем захотеть ввести больше структуры в процесс регуляризации, чтобы, например, входные переменные подавлялись в соответствии с заранее определенными группами. Методы регуляризации структурированной разреженности позволяют навязать такую структуру, добавляя структуру к нормам, определяющим термин регуляризации.
Структуры и нормы
[ редактировать ]Непересекающиеся группы: группа «Лассо»
[ редактировать ]Случай непересекающейся группы — это самый простой пример структурированной разреженности. В нем априорное разбиение вектора коэффициентов в предполагается непересекающиеся группы. Позволять быть вектором коэффициентов в группе мы можем определить термин регуляризации и его групповую норму как
- ,
где это группа норма , это группа , и — j-й компонент группы .
Вышеуказанную норму еще называют групповым лассо . [2] Этот регуляризатор будет стремиться к нулю целых групп коэффициентов, а не отдельных коэффициентов. Поскольку группы непересекающиеся, набор ненулевых коэффициентов можно получить как объединение групп, которые не были установлены в ноль, и наоборот для набора нулевых коэффициентов.
Перекрывающиеся группы
[ редактировать ]Перекрывающиеся группы — это случай разреженности структуры, когда переменная может принадлежать более чем одной группе. . Этот случай часто представляет интерес, поскольку он может представлять более общий класс отношений между переменными, чем непересекающиеся группы, такие как древовидные структуры или другие типы графов. [3] [8]
Существует два типа подходов к регуляризации перекрывающейся групповой разреженности, которые используются для моделирования различных типов отношений входных переменных:
Пересечение дополнений: группа Лассо
[ редактировать ]Подход пересечения дополнений используется в тех случаях, когда мы хотим выбрать только те входные переменные, которые имеют положительные коэффициенты во всех группах, к которым они принадлежат. Рассмотрим еще раз групповое Лассо для регуляризованной эмпирической задачи минимизации риска :
- ,
где это группа норма, это группа , и — j-й компонент группы .
Как и в случае с непересекающимися группами, регуляризатор группового Лассо потенциально обнуляет целые группы коэффициентов. Выбраны переменные с коэффициентами . Однако, поскольку в этом случае группы могут перекрываться, мы берем пересечение дополнений тех групп, которые не равны нулю.
Это пересечение критериев выбора дополнений подразумевает выбор моделирования, согласно которому мы допускаем некоторые коэффициенты внутри определенной группы. быть установлено на ноль, в то время как другие в той же группе может оставаться положительным. Другими словами, коэффициенты внутри группы могут различаться в зависимости от принадлежности к нескольким группам, которые может иметь каждая переменная внутри группы.
Объединение групп: латентная группа Лассо
[ редактировать ]Другой подход заключается в рассмотрении объединения групп для выбора переменных. Этот подход отражает ситуацию моделирования, когда переменные могут быть выбраны, если они принадлежат хотя бы к одной группе с положительными коэффициентами. Эта перспектива моделирования подразумевает, что мы хотим сохранить структуру группы.
Формулировка подхода объединения групп также называется Лассо скрытой группы и требует изменения группы. норму, рассмотренную выше, и введем следующий регуляризатор [3]
где , – вектор коэффициентов группы g, а вектор с коэффициентами для всех переменных в группе , и во всех остальных, т.е. если в группе и в противном случае.
Этот регуляризатор можно интерпретировать как эффективное копирование переменных, принадлежащих более чем одной группе, что позволяет сохранить структуру группы. По замыслу подхода объединения групп, требующего создает вектор весов w, который эффективно суммирует веса всех переменных во всех группах, к которым они принадлежат.
Проблемы с регуляризацией Group Lasso и альтернативными подходами
[ редактировать ]Целевая функция, использующая групповое лассо, состоит из функции ошибок, которая обычно должна быть выпуклой, но не обязательно сильно выпуклой, и групповой функции. срок регуляризации. Проблема с этой целевой функцией заключается в том, что она выпуклая, но не обязательно сильно выпуклая, и поэтому обычно не приводит к уникальным решениям. [9]
Пример способа исправить это — ввести квадрат норма весового вектора в качестве дополнительного члена регуляризации при сохранении термин регуляризации из подхода группового лассо. [9] Если коэффициент при квадрате Нормативный член больше, чем , то поскольку квадрат Нормальный член сильно выпуклый, то результирующая целевая функция также будет сильно выпуклой. [9] При условии, что коэффициент достаточно мал, но все же положителен, весовой вектор, минимизирующий результирующую целевую функцию, обычно очень близок к весовому вектору, который минимизирует целевую функцию, которая возникнет в результате удаления группы. член регуляризации полностью отличается от исходной целевой функции; последний сценарий соответствует подходу группового лассо. [9] Таким образом, этот подход позволяет упростить оптимизацию при сохранении разреженности. [9]
Нормы, основанные на структуре входных переменных
[ редактировать ]См.: Функция субмодульного набора.
Помимо норм, обсуждавшихся выше, другие нормы, используемые в методах структурированной разреженности, включают иерархические нормы и нормы, определенные на сетках. Эти нормы возникают из субмодулярных функций и позволяют включать предварительные предположения о структуре входных переменных. В контексте иерархических норм эта структура может быть представлена как ориентированный ациклический граф над переменными, тогда как в контексте норм, основанных на сетке, структура может быть представлена с использованием сетки. [10] [11] [12] [13] [14] [15]
Иерархические нормы
[ редактировать ]Методы обучения без учителя часто используются для изучения параметров моделей со скрытыми переменными . Модели со скрытыми переменными — это статистические модели, в которых помимо наблюдаемых переменных существует также набор скрытых переменных, которые не наблюдаются. Часто в таких моделях предполагаются «иерархии» между переменными системы; эту систему иерархий можно представить с помощью ориентированных ациклических графов.
Иерархии скрытых переменных стали естественной структурой в нескольких приложениях, особенно для моделирования текстовых документов. [11] Иерархические модели с использованием байесовских непараметрических методов использовались для изучения тематических моделей . [10] которые представляют собой статистические модели для обнаружения абстрактных «тем», встречающихся в коллекции документов. Иерархии также рассматривались в контексте методов ядра. [13] Иерархические нормы были применены к биоинформатике. [12] компьютерное зрение и тематические модели. [14]
Нормы, определенные на сетках
[ редактировать ]Если предполагаемая структура переменных имеет форму 1D, 2D или 3D сетки, то субмодулярные функции, основанные на перекрывающихся группах, можно рассматривать как нормы, приводящие к стабильным множествам, равным прямоугольным или выпуклым формам. [13] Такие методы имеют применение в компьютерном зрении. [15]
Алгоритмы вычислений
[ редактировать ]Задача выбора лучшего подмножества
[ редактировать ]Проблему выбора наилучшего подмножества входных переменных можно естественным образом сформулировать в рамках системы штрафов следующим образом: [4]
Где обозначает «норма», определяемая как количество ненулевых элементов вектора. .
Хотя эта формулировка имеет смысл с точки зрения моделирования, она неосуществима с вычислительной точки зрения, поскольку эквивалентна исчерпывающему перебору с оценкой всех возможных подмножеств переменных. [4]
Двумя основными подходами к решению задачи оптимизации являются: 1) жадные методы, такие как пошаговая регрессия в статистике или поиск совпадений при обработке сигналов ; и 2) подходы к формулированию выпуклой релаксации и методы оптимизации проксимального градиента .
Выпуклая релаксация
[ редактировать ]Естественным приближением для задачи выбора лучшего подмножества является регуляризация нормы: [4]
Такая схема называется преследованием базиса или Лассо , которое заменяет «норма» для выпуклого, недифференцируемого норма.
Методы проксимального градиента
[ редактировать ]Методы проксимального градиента , также называемые расщеплением вперед-назад, представляют собой методы оптимизации, полезные для минимизации функций с выпуклым и дифференцируемым компонентом, а также выпуклым потенциально недифференцируемым компонентом.
Таким образом, методы проксимального градиента полезны для решения проблем регуляризации разреженности и структурированной разреженности. [9] следующей формы:
Где является выпуклой и дифференцируемой функцией потерь, такой как квадратичная потеря , и является выпуклым потенциально недифференцируемым регуляризатором, таким как норма.
Связи с другими областями машинного обучения
[ редактировать ]Подключение к обучению с несколькими ядрами
[ редактировать ]Регуляризацию структурированной разреженности можно применять в контексте множественного обучения ядра . [16] Множественное обучение ядер относится к набору методов машинного обучения, которые используют заранее определенный набор ядер и изучают оптимальную линейную или нелинейную комбинацию ядер как часть алгоритма.
В упомянутых выше алгоритмах учитывалось сразу все пространство и разбивалось на группы, т.е. подпространства. Дополнительная точка зрения состоит в том, чтобы рассмотреть случай, когда различные пространства объединяются для получения нового. Полезно обсудить эту идею, рассматривая конечные словари. Конечные словари с линейно независимыми элементами (эти элементы также известны как атомы) относятся к конечным наборам линейно независимых базисных функций, линейные комбинации которых определяют пространства гипотез. Как будет показано, для определения конкретных ядер можно использовать конечные словари. [16] Предположим в этом примере, что рассматривается не один словарь, а несколько конечных словарей.
Для простоты рассмотрим случай, когда имеется только два словаря. и где и являются целыми числами, будут считаться. Атомы в а также атомы в предполагаются линейно независимыми. Позволять быть объединением двух словарей. Рассмотрим линейное пространство функций заданные линейными комбинациями вида
для некоторых векторов коэффициентов , где . Предположим, что атомы в оставаться линейно независимым или, что то же самое, что отображение это один в один. Функции в пространстве можно рассматривать как сумму двух компонентов, один из которых находится в пространстве , линейные комбинации атомов в и один в , линейные комбинации атомов в .
Один из вариантов нормы в этом пространстве: . Обратите внимание, что теперь мы можем просмотреть как функциональное пространство, в котором , являются подпространствами. Ввиду предположения линейной независимости можно отождествить с и с соответственно. Упомянутую выше норму можно рассматривать как групповую норму в связанный с подпространствами , , обеспечивая связь со структурированной регуляризацией разреженности.
Здесь, , и можно рассматривать как воспроизводящее ядро гильбертова пространства с соответствующими картами признаков. , заданный , , заданный , и , заданный конкатенацией , соответственно.
В подходе структурированной регуляризации разреженности к этому сценарию соответствующие группы переменных, которые рассматривают групповые нормы, соответствуют подпространствам и . Этот подход способствует установке нулевых групп коэффициентов, соответствующих этим подпространствам, а не только отдельных коэффициентов, способствуя разреженному множественному обучению ядра.
Приведенные выше рассуждения напрямую распространяются на любое конечное число словарей или карт объектов. Его можно расширить, чтобы включить в него карты признаков, вызывающие гипотезу бесконечного измерения.
пространства. [16]
Когда полезно разреженное множественное обучение ядра
[ редактировать ]Рассмотрение разреженного множественного обучения ядра полезно в нескольких ситуациях, включая следующие:
- Слияние данных: когда каждое ядро соответствует различному типу модальности/функции.
- Нелинейный выбор переменных: рассмотрим ядра зависит только от одного измерения входных данных.
Как правило, разреженное обучение с несколькими ядрами особенно полезно, когда ядер много, а выбор модели и ее интерпретируемость важны. [16]
Дополнительные варианты использования и применения
[ редактировать ]Методы структурированной регуляризации разреженности использовались в ряде случаев, когда желательно наложить априорную структуру входных переменных на процесс регуляризации. Вот некоторые из таких приложений:
- Компрессионное зондирование в магнитно-резонансной томографии (МРТ), восстановление МР-изображений на основе небольшого количества измерений, что потенциально приводит к значительному сокращению времени МР-сканирования. [6]
- Надежное распознавание лиц при наличии смещения, окклюзии и изменения освещенности [5]
- Выявление социолингвистических ассоциаций между лексическими частотами, используемыми авторами Твиттера, и социально-демографическими переменными их географических сообществ. [7]
- Анализ выбора генов данных о раке молочной железы с использованием априорных данных перекрывающихся групп, например, биологически значимых наборов генов. [8]
См. также
[ редактировать ]- Статистическая теория обучения
- Регуляризация
- Разреженное приближение
- Методы проксимального градиента
- Выпуклый анализ
- Выбор функции
Ссылки
[ редактировать ]- ^ Росаско, Лоренцо; Поджо, Томассо (декабрь 2014 г.). Экскурсия по машинному обучению по регуляризации, конспекты лекций MIT-9.520 .
- ^ Jump up to: а б с д Юань, М.; Лин, Ю. (2006). «Выбор модели и оценка в регрессии с сгруппированными переменными». JR Стат. Соц. Б. 68 (1): 49–67. CiteSeerX 10.1.1.79.2062 . дои : 10.1111/j.1467-9868.2005.00532.x . S2CID 6162124 .
- ^ Jump up to: а б с д и Обозинский, Г.; Лоран, Дж.; Верт, Ж.-П. (2011). «Групповое лассо с перекрытиями: подход скрытого группового лассо». arXiv : 1110.0413 [ stat.ML ].
- ^ Jump up to: а б с д и Л. Росаско. Лекция 10 из конспектов лекций по курсу 9.520: Статистическая теория обучения и ее приложения. Массачусетский технологический институт, осень 2014 г. Доступно по адресу https://www.mit.edu/~9.520/fall14/slides/class18/class18_sparsity.pdf.
- ^ Jump up to: а б Цзя, Куй; и др. (2012). «Надежное и практичное распознавание лиц с помощью структурированной разреженности». У Эндрю Фитцгиббона; Светлана Лазебник; Пьетро Перона; Йоичи Сато; Корделия Шмид (ред.). Компьютерное зрение – ECCV 2012: 12-я Европейская конференция по компьютерному зрению, Флоренция, Италия, 7–13 октября 2012 г., Материалы, Часть IV .
- ^ Jump up to: а б Чен, Чен; и др. (2012). «МРТ с компрессионным зондированием и разреженностью дерева вейвлетов» . Материалы 26-й ежегодной конференции по нейронным системам обработки информации . Том. 25. Карран Ассошиэйтс. стр. 1115–1123.
- ^ Jump up to: а б Эйзенштейн, Джейкоб; и др. (2011). «Обнаружение социолингвистических ассоциаций со структурированной разреженностью». Материалы 49-го ежегодного собрания Ассоциации компьютерной лингвистики .
- ^ Jump up to: а б с Джейкоб, Лоран; и др. (2009). «Групповое лассо с перекрытием и графическое лассо». Материалы 26-й Международной конференции по машинному обучению .
- ^ Jump up to: а б с д и ж Вилла, С.; Росаско, Л.; Моски, С.; Верри, А. (2012). «Проксимальные методы наказания скрытых групповых лассо». arXiv : 1209.0368 [ math.OC ].
- ^ Jump up to: а б Блей Д., Нг А. и Джордан М. Скрытое распределение дирихле. Дж. Мах. Учиться. Рез., 3:993–1022, 2003.
- ^ Jump up to: а б Бенджио, Ю. «Изучение глубокой архитектуры для искусственного интеллекта». Основы и тенденции в машинном обучении, 2 (1), 2009.
- ^ Jump up to: а б С. Ким и Э. Син. Древовидная группа Lasso для многозадачной регрессии со структурированной разреженностью. В Proc. ИКМЛ, 2010.
- ^ Jump up to: а б с Дженаттон, Родольф; Одибер, Жан-Ив; Бах, Франциск (2011). «Структурированный выбор переменных с нормами, вызывающими разреженность». Журнал исследований машинного обучения . 12 (2011): 2777–2824. arXiv : 0904.3523 . Бибкод : 2009arXiv0904.3523J .
- ^ Jump up to: а б Р. Дженаттон, Дж. Майрал, Г. Обозинский и Ф. Бах. Проксимальные методы обучения разреженным иерархическим словарям. В Proc. ИКМЛ, 2010.
- ^ Jump up to: а б Р. Дженаттон, Г. Обозинский и Ф. Бах. Структурированный анализ разреженных главных компонент. В Proc. АЙСТАТС , 2009.
- ^ Jump up to: а б с д Росаско, Лоренцо; Поджо, Томазо (осень 2015 г.). «Глава 6». Конспект курса MIT 9.520, осень 2015 г.