Редкое изучение словаря - Sparse dictionary learning

Часть серии о
Машинное обучение и интеллектуальный анализ данных
Проблемы Классификация Кластеризация Регресс Обнаружение аномалий Очистка данных AutoML Правила ассоциации Обучение с подкреплением Структурированный прогноз Функциональная инженерия Особенности обучения Онлайн обучение Полу-контролируемое обучение Неконтролируемое обучение Учимся ранжировать Введение в грамматику
Обучение с учителем ( классификация  • регрессия ) Деревья решений Ансамбли Упаковка Повышение Случайный лес k -NN Линейная регрессия Наивный байесовский Искусственные нейронные сети Логистическая регрессия Перцептрон Вектор релевантности (RVM) Машина опорных векторов (SVM)
Кластеризация БЕРЕЗА ИЗЛЕЧИВАТЬ Иерархический k -средство Ожидание – максимизация (EM) DBSCAN ОПТИКА Средний сдвиг
Снижение размерности Факторный анализ CCA ICA LDA NMF PCA PGD t-SNE
Структурированный прогноз Графические модели Сеть Байеса Условное случайное поле Скрытый Марков
Обнаружение аномалий k -NN Фактор местного выброса
Искусственная нейронная сеть Автоэнкодер Когнитивные вычисления Глубокое обучение DeepDream Многослойный перцептрон RNN LSTM ГРУ ESN Ограниченная машина Больцмана GAN SOM Сверточная нейронная сеть U-Net Трансформатор Пиковая нейронная сеть Мемтранзистор Электрохимическая RAM (ECRAM)
Обучение с подкреплением Q-обучение SARSA Временная разница (TD)
Теория Компромисс смещения и дисперсии Теория вычислительного обучения Минимизация эмпирического риска Обучение Оккама PAC обучение Статистическое обучение Теория ВК
Площадки для машинного обучения NeurIPS ICML ML JMLR ArXiv: cs.LG
Статьи по Теме Глоссарий искусственного интеллекта Список наборов данных для исследований в области машинного обучения Краткое описание машинного обучения
v т е

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

Одно из наиболее важных приложений обучения разреженному словарю - это сжатое восприятие или восстановление сигнала . При сжатии измерений сигнал большой размерности может быть восстановлен только с помощью нескольких линейных измерений при условии, что сигнал является разреженным или почти разреженным. Поскольку не все сигналы удовлетворяют этому условию разреженности, очень важно найти разреженное представление этого сигнала, такое как вейвлет-преобразование или направленный градиент растеризованной матрицы. После того, как матрица или вектор большой размерности переносится в разреженное пространство, для восстановления сигнала могут использоваться различные алгоритмы восстановления, такие как поиск по базису, CoSaMP или быстрые неитерационные алгоритмы.

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

Постановка задачи

Учитывая входной набор данных, мы хотим найти словарь и такое представление , чтобы они были минимизированы, а представления были достаточно разреженными. Это можно сформулировать как следующую задачу оптимизации : ${\ displaystyle X = [x_ {1}, ..., x_ {K}], x_ {i} \ in \ mathbb {R} ^ {d}}$${\ displaystyle \ mathbf {D} \ in \ mathbb {R} ^ {d \ times n}: D = [d_ {1}, ..., d_ {n}]}$${\ displaystyle R = [r_ {1}, ..., r_ {K}], r_ {i} \ in \ mathbb {R} ^ {n}}$${\ Displaystyle \ | X- \ mathbf {D} R \ | _ {F} ^ {2}}$${\ displaystyle r_ {i}}$

${\ displaystyle {\ underset {\ mathbf {D} \ in {\ mathcal {C}}, r_ {i} \ in \ mathbb {R} ^ {n}} {\ text {argmin}}} \ sum _ { i = 1} ^ {K} \ | x_ {i} - \ mathbf {D} r_ {i} \ | _ {2} ^ {2} + \ lambda \ | r_ {i} \ | _ {0}}$, где ,${\ Displaystyle {\ mathcal {C}} \ Equiv \ {\ mathbf {D} \ in \ mathbb {R} ^ {d \ times n}: \ | d_ {i} \ | _ {2} \ leq 1 \ , \, \ forall i = 1, ..., n \}}$${\ displaystyle \ lambda> 0}$

${\ displaystyle {\ mathcal {C}}}$требуется для ограничения, чтобы его атомы не достигли произвольно высоких значений, допускающих произвольно низкие (но ненулевые) значения . контролирует компромисс между разреженностью и ошибкой минимизации. ${\ displaystyle \ mathbf {D}}$${\ displaystyle r_ {i}}$${\ displaystyle \ lambda}$

Вышеупомянутая задача минимизации не является выпуклой из-за ℓ ₀ - «нормы», и ее решение NP-сложно. В некоторых случаях известно, что L ¹ -норма обеспечивает разреженность, и поэтому вышеупомянутая задача становится выпуклой оптимизационной задачей по каждой из переменных, и когда другая фиксирована, но она не является совместно выпуклой по . ${\ displaystyle \ mathbf {D}}$${\ displaystyle \ mathbf {R}}$${\ Displaystyle (\ mathbf {D}, \ mathbf {R})}$

Свойства словаря

Словарь, определенный выше, может быть «неполным», если или «переполненным» в случае, когда последнее является типичным допущением для проблемы изучения разреженного словаря. Случай полного словаря не дает никаких улучшений с репрезентативной точки зрения и поэтому не рассматривается. ${\ displaystyle \ mathbf {D}}$${\ displaystyle n <d}$${\ displaystyle n> d}$

Неполные словари представляют собой установку, в которой фактические входные данные находятся в пространстве меньшей размерности. Этот случай сильно связан с уменьшением размерности и такими методами, как анализ главных компонентов, которые требуют, чтобы атомы были ортогональными. Выбор этих подпространств имеет решающее значение для эффективного уменьшения размерности, но не является тривиальным. А уменьшение размерности на основе словарного представления может быть расширено для решения конкретных задач, таких как анализ или классификация данных. Однако их главный недостаток - ограничение выбора атомов. ${\ displaystyle d_ {1}, ..., d_ {n}}$

Однако переполненные словари не требуют, чтобы атомы были ортогональными (в любом случае они никогда не будут основой ), что позволяет создавать более гибкие словари и более богатые представления данных.

Переполненный словарь, который допускает разреженное представление сигнала, может быть известной матрицей преобразования (вейвлет-преобразование, преобразование Фурье) или может быть сформулирован так, что его элементы изменяются таким образом, что он разреженно представляет данный сигнал наилучшим образом. Выученные словари могут давать более разреженные решения по сравнению с предопределенными матрицами преобразования.

Алгоритмы

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

Проблема поиска оптимального разреженного кодирования с заданным словарем известна как разреженное приближение (или иногда просто проблема разреженного кодирования). Для ее решения был разработан ряд алгоритмов (например, поиск совпадения и LASSO ), которые включены в алгоритмы, описанные ниже. ${\ displaystyle R}$${\ displaystyle \ mathbf {D}}$

Метод оптимальных направлений (MOD)

Метод оптимальных направлений (или MOD) был одним из первых методов, предложенных для решения проблемы изучения разреженного словаря. Основная идея состоит в том, чтобы решить задачу минимизации с учетом ограниченного числа ненулевых компонентов вектора представления:

${\ displaystyle \ min _ {\ mathbf {D}, R} \ {\ | X- \ mathbf {D} R \ | _ {F} ^ {2} \} \, \, {\ text {st}} \, \, \ forall i \, \, \ | r_ {i} \ | _ {0} \ leq T}$

Здесь обозначает норму Фробениуса . MOD чередуется между получением разреженного кодирования с использованием такого метода, как поиск соответствия, и обновлением словаря путем вычисления аналитического решения проблемы, заданной как где - псевдообратная функция Мура-Пенроуза . После этого обновления перенормируется в соответствии с ограничениями, и снова получается новое разреженное кодирование. Процесс повторяется до схождения (или до достаточно небольшого остатка). ${\ displaystyle F}$${\ Displaystyle \ mathbf {D} = XR ^ {+}}$${\ Displaystyle R ^ {+}}$${\ displaystyle \ mathbf {D}}$

MOD оказался очень эффективным методом для низкоразмерных входных данных, требующих всего нескольких итераций для схождения. Однако из-за высокой сложности операции обращения матрицы вычисление псевдообратной матрицы в случаях большой размерности во многих случаях является неразрешимым. Этот недостаток вдохновил на разработку других методов изучения словарей. ${\ displaystyle X}$

К-СВД

K-SVD - это алгоритм, который выполняет SVD в своей основе для обновления атомов словаря один за другим и в основном является обобщением K-средних . Он требует, чтобы каждый элемент входных данных кодировался линейной комбинацией не более чем элементов способом, идентичным подходу MOD: ${\ displaystyle x_ {i}}$${\ displaystyle T_ {0}}$

${\ displaystyle \ min _ {\ mathbf {D}, R} \ {\ | X- \ mathbf {D} R \ | _ {F} ^ {2} \} \, \, {\ text {st}} \, \, \ forall i \, \, \ | r_ {i} \ | _ {0} \ leq T_ {0}}$

Суть этого алгоритма состоит в том, чтобы сначала исправить словарь, найти наилучшее из возможных при указанном выше ограничении (с использованием метода ортогонального сопоставления ), а затем итеративно обновить атомы словаря следующим образом: ${\ displaystyle R}$${\ displaystyle \ mathbf {D}}$

${\ Displaystyle \ | X- \ mathbf {D} R \ | _ {F} ^ {2} = \ left | X- \ sum _ {i = 1} ^ {K} d_ {i} x_ {T} ^ {i} \ right | _ {F} ^ {2} = \ | E_ {k} -d_ {k} x_ {T} ^ {k} \ | _ {F} ^ {2}}$

Следующие шаги алгоритма включают приближение ранга 1 остаточной матрицы , обновление и обеспечение разреженности после обновления. Этот алгоритм считается стандартным для изучения словарей и используется во множестве приложений. Однако у него есть общие недостатки: MOD эффективен только для сигналов с относительно низкой размерностью и имеет возможность застревать на локальных минимумах. ${\ displaystyle E_ {k}}$${\ displaystyle d_ {k}}$${\ displaystyle x_ {k}}$

Стохастический градиентный спуск

Для решения этой проблемы можно также применить широко распространенный метод стохастического градиентного спуска с итеративным проецированием. Идея этого метода состоит в том, чтобы обновить словарь, используя стохастический градиент первого порядка, и спроецировать его на набор ограничений . Шаг, который происходит на i-й итерации, описывается этим выражением: ${\ displaystyle {\ mathcal {C}}}$

${\ displaystyle \ mathbf {D} _ {i} = {\ text {proj}} _ {\ mathcal {C}} \ left \ {\ mathbf {D} _ {i-1} - \ delta _ {i} \ nabla _ {\ mathbf {D}} \ sum _ {i \ in S} \ | x_ {i} - \ mathbf {D} r_ {i} \ | _ {2} ^ {2} + \ lambda \ | r_ {i} \ | _ {1} \ right \}}$, где - случайное подмножество и - шаг градиента. ${\ displaystyle S}$${\ Displaystyle \ {1 ... К \}}$${\ displaystyle \ delta _ {я}}$

Двойственный метод Лагранжа

Алгоритм, основанный на решении двойной задачи Лагранжа, обеспечивает эффективный способ решения словаря без осложнений, вызванных функцией разреженности. Рассмотрим следующий лагранжиан:

${\ Displaystyle {\ mathcal {L}} (\ mathbf {D}, \ Lambda) = {\ text {tr}} \ left ((X- \ mathbf {D} R) ^ {T} (X- \ mathbf {D} R) \ right) + \ sum _ {j = 1} ^ {n} \ lambda _ {j} \ left ({\ sum _ {i = 1} ^ {d} \ mathbf {D} _ { ij} ^ {2} -c} \ right)}$, где - ограничение на норму атомов, - так называемые двойственные переменные, образующие диагональную матрицу . ${\ displaystyle c}$${\ displaystyle \ lambda _ {i}}$${\ displaystyle \ Lambda}$

Затем мы можем предоставить аналитическое выражение для двойника Лагранжа после минимизации : ${\ displaystyle \ mathbf {D}}$

${\ displaystyle {\ mathcal {D}} (\ Lambda) = \ min _ {\ mathbf {D}} {\ mathcal {L}} (\ mathbf {D}, \ Lambda) = {\ text {tr}} (X ^ {T} X-XR ^ {T} (RR ^ {T} + \ Lambda) ^ {- 1} (XR ^ {T}) ^ {T} -c \ Lambda)}$.

После применения одного из методов оптимизации к значению двойственного (например , метода Ньютона или сопряженного градиента ) мы получаем значение : ${\ displaystyle \ mathbf {D}}$

${\ Displaystyle \ mathbf {D} ^ {T} = (RR ^ {T} + \ Lambda) ^ {- 1} (XR ^ {T}) ^ {T}}$

Решение этой проблемы требует меньших вычислительных затрат, поскольку количество двойных переменных во много раз меньше, чем количество переменных в основной задаче. ${\ displaystyle n}$

ЛАССО

При таком подходе задача оптимизации формулируется как:

${\ displaystyle \ min _ {r \ in \ mathbb {R} ^ {n}} \ {\, \, \ | r \ | _ {1} \} \, \, {\ text {при условии}} \ , \, \ | X- \ mathbf {D} R \ | _ {F} ^ {2} <\ epsilon}$, где - допустимая погрешность реконструкции LASSO. ${\ displaystyle \ epsilon}$

Он находит оценку путем минимизации ошибки наименьших квадратов с учетом ограничения L ¹ -нормы в векторе решения, сформулированного как: ${\ displaystyle r_ {i}}$

${\ displaystyle \ min _ {r \ in \ mathbb {R} ^ {n}} \, \, {\ dfrac {1} {2}} \, \, \ | X- \ mathbf {D} r \ | _ {F} ^ {2} + \ lambda \, \, \ | r \ | _ {1}}$, где контролирует компромисс между разреженностью и ошибкой восстановления. Это дает глобальное оптимальное решение. См. Также изучение онлайн-словарей для разреженного кодирования.${\ displaystyle \ lambda> 0}$

Параметрические методы обучения

Методы параметрического обучения нацелены на то, чтобы объединить лучшее из обоих миров - области аналитически построенных словарей и изученных. Это позволяет создавать более мощные обобщенные словари, которые потенциально могут быть применены к случаям сигналов произвольного размера. Известные подходы включают:

• Переводно-инвариантные словари. Эти словари состоят из переводов атомов, происходящих из словаря, созданного для фрагмента сигнала конечного размера. Это позволяет результирующему словарю предоставить представление для сигнала произвольного размера.
• Мультимасштабные словари. Этот метод направлен на создание словаря, который состоит из словарей с различным масштабом, чтобы улучшить разреженность.
• Скудные словари. Этот метод ориентирован не только на обеспечение разреженного представления, но и на построение разреженного словаря, который обеспечивается выражением, где - некоторый предопределенный аналитический словарь с желательными свойствами, такими как быстрое вычисление, и разреженная матрица. Такая формулировка позволяет напрямую сочетать быструю реализацию аналитических словарей с гибкостью разреженных подходов.${\ Displaystyle \ mathbf {D} = \ mathbf {B} \ mathbf {A}}$${\ displaystyle \ mathbf {B}}$${\ displaystyle \ mathbf {A}}$

Обучение онлайн-словарю ( подход LASSO )

Многие распространенные подходы к изучению разреженного словаря основаны на том факте, что для алгоритма доступны все входные данные (или, по крайней мере, достаточно большой набор обучающих данных). Однако в реальном сценарии это может быть не так, поскольку размер входных данных может быть слишком большим, чтобы уместить их в памяти. Другой случай, когда это предположение невозможно сделать, - это когда входные данные поступают в виде потока . Такие случаи лежат в области изучения онлайн-обучения, которое, по сути, предполагает итеративное обновление модели при появлении новых точек данных. ${\ displaystyle X}$${\ displaystyle x}$

Словарь можно выучить в режиме онлайн следующим образом:

1. Для ${\ displaystyle t = 1 ... T:}$
2. Нарисуйте новый образец ${\ displaystyle x_ {t}}$
3. Найдите разреженное кодирование с помощью LARS :${\ displaystyle r_ {t} = {\ underset {r \ in \ mathbb {R} ^ {n}} {\ text {argmin}}} \ left ({\ frac {1} {2}} \ | x_ { t} - \ mathbf {D} _ {t-1} r \ | + \ lambda \ | r \ | _ {1} \ right)}$
4. Обновить словарь с использованием блочно-координатного подхода:${\ displaystyle \ mathbf {D} _ {t} = {\ underset {\ mathbf {D} \ in {\ mathcal {C}}} {\ text {argmin}}} {\ frac {1} {t}} \ sum _ {i = 1} ^ {t} \ left ({\ frac {1} {2}} \ | x_ {i} - \ mathbf {D} r_ {i} \ | _ {2} ^ {2 } + \ lambda \ | r_ {i} \ | _ {1} \ right)}$

Этот метод позволяет нам постепенно обновлять словарь по мере того, как новые данные становятся доступными для обучения разреженному представлению, и помогает резко сократить объем памяти, необходимый для хранения набора данных (который часто имеет огромный размер).

Приложения

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

Он также имеет свойства, которые полезны для шумоподавления сигнала, поскольку обычно можно выучить словарь, чтобы представлять значимую часть входного сигнала разреженным образом, но шум на входе будет иметь гораздо менее разреженное представление.

Разрезанное изучение словаря успешно применялось к различным задачам обработки изображений, видео и аудио, а также к синтезу текстур и неконтролируемой кластеризации. При оценке модели « Сумка слов» эмпирически было обнаружено, что разреженное кодирование превосходит другие подходы к кодированию в задачах распознавания категорий объектов.

Обучение по словарю используется для детального анализа медицинских сигналов. К таким медицинским сигналам относятся сигналы электроэнцефалографии (ЭЭГ), электрокардиографии (ЭКГ), магнитно-резонансной томографии (МРТ), функциональной МРТ (фМРТ), непрерывных мониторов глюкозы и ультразвуковой компьютерной томографии (УЗИ), где для анализа каждого сигнала используются различные допущения.

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

• Разреженное приближение
• Редкий PCA
• К-СВД
• Факторизация матрицы
• Нейронное разреженное кодирование

использованная литература