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

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

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

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

Удаление шума изображения с помощью обучения по словарю

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

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

${\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}$, где ${\mathcal {C}}\equiv \{\mathbf {D} \in \mathbb {R} ^{d\times n}:\|d_{i}\|_{2}\leq 1\,\,\forall i=1,...,n\}$, $\lambda >0$

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

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

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

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

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

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

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

Алгоритмы

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

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

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

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

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

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

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

К-СВД

Основная статья: К-СВД

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

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

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

$\|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. аппроксимацию остаточной матрицы $E_{k}$, обновление $d_{k}$ и обеспечение редкости $x_{k}$ после обновления. Этот алгоритм считается стандартным для изучения словарей и используется во множестве приложений. Однако у него есть общие недостатки: MOD эффективен только для сигналов с относительно низкой размерностью и имеет возможность застревания в локальных минимумах.

спуск

Основная статья: Стохастический градиентный спуск

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

$\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\}$, где $S$ представляет собой случайное подмножество $\{1...K\}$ и $\delta _{i}$ является градиентным шагом.

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

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

${\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)$, где $c$ является ограничением на норму атомов и $\lambda _{i}$ – это так называемые двойственные переменные, образующие диагональную матрицу $\Lambda$.

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

${\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 )$.

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

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

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

ЛАССО

Основная статья: Лассо (статистика)

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

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

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

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

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

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

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

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

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

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

1. Для $t=1...T:$
2. Нарисуйте новый образец $x_{t}$
3. Найдите разреженное кодирование с помощью LARS : $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. Обновить словарь, используя блочно-координатный подход: $\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
• К-СВД
• Матричная факторизация
• Нейронное разреженное кодирование