Разреженное кодирование - это метод обучения представлению, который направлен на поиск разреженного представления входных данных (также известного как разреженное кодирование ) в форме линейной комбинации базовых элементов, а также самих этих базовых элементов. Эти элементы называются атомами, и они составляют словарь . Атомы в словаре не обязательно должны быть ортогональными, и они могут быть чрезмерно полным остовным набором. Эта постановка задачи также позволяет размерности представляемых сигналов быть выше, чем размерность наблюдаемых сигналов. Два вышеупомянутых свойства приводят к появлению кажущихся избыточными атомов, которые позволяют несколько представлений одного и того же сигнала, но также обеспечивают улучшение разреженности и гибкости представления.
Одно из наиболее важных приложений обучения разреженному словарю - это сжатое восприятие или восстановление сигнала . При сжатии измерений сигнал большой размерности может быть восстановлен только с помощью нескольких линейных измерений при условии, что сигнал является разреженным или почти разреженным. Поскольку не все сигналы удовлетворяют этому условию разреженности, очень важно найти разреженное представление этого сигнала, такое как вейвлет-преобразование или направленный градиент растеризованной матрицы. После того, как матрица или вектор большой размерности переносится в разреженное пространство, для восстановления сигнала могут использоваться различные алгоритмы восстановления, такие как поиск базиса , CoSaMP [1] или быстрые неитерационные алгоритмы [2] .
Один из ключевых принципов изучения словаря состоит в том, что словарь должен быть выведен из входных данных. Появление методов обучения с использованием разреженных словарей было стимулировано тем фактом, что при обработке сигналов обычно требуется представлять входные данные с использованием как можно меньшего количества компонентов. До этого подхода общей практикой было использование предопределенных словарей (таких как преобразования Фурье или вейвлет- преобразования). Однако в некоторых случаях словарь, который обучен для соответствия входным данным, может значительно улучшить разреженность, которая имеет приложения для декомпозиции, сжатия и анализа данных и используется в областях шумоподавления и классификации изображений, обработки видео и аудио . Редкие и переполненные словари находят огромное применение в сжатии изображений, слиянии изображений и в рисовании.
Постановка задачи
Учитывая входной набор данных мы хотим найти словарь и представление так что оба минимизируется, а представления достаточно редки. Это можно сформулировать как следующую задачу оптимизации :
, где ,
требуется для ограничения так, чтобы его атомы не достигли произвольно высоких значений, допускающих произвольно низкие (но ненулевые) значения . контролирует компромисс между разреженностью и ошибкой минимизации.
Вышеупомянутая задача минимизации не является выпуклой из-за ℓ 0 - «нормы», и ее решение NP-сложно. [3] В некоторых случаях известно, что L 1 -норма обеспечивает разреженность [4], и поэтому вышеупомянутая задача становится выпуклой оптимизационной задачей по каждой из переменных. а также когда другой зафиксирован, но вместе он не выпуклый в .
Свойства словаря
Словарь определенное выше может быть "неполным", если или "переполнено" в случае, если причем последнее является типичным допущением для проблемы изучения разреженного словаря. Случай полного словаря не дает никаких улучшений с репрезентативной точки зрения и поэтому не рассматривается.
Неполные словари представляют собой установку, в которой фактические входные данные находятся в пространстве меньшей размерности. Этот случай сильно связан с уменьшением размерности и такими методами, как анализ главных компонент, которые требуют наличия атомовбыть ортогональным. Выбор этих подпространств имеет решающее значение для эффективного уменьшения размерности, но не является тривиальным. А уменьшение размерности на основе словарного представления может быть расширено для решения конкретных задач, таких как анализ или классификация данных. Однако их главный недостаток - ограничение выбора атомов.
Однако переполненные словари не требуют, чтобы атомы были ортогональными (в любом случае они никогда не будут основой ), что позволяет создавать более гибкие словари и более богатые представления данных.
Переполненный словарь, который допускает разреженное представление сигнала, может быть известной матрицей преобразования (вейвлет-преобразование, преобразование Фурье) или может быть сформулирован так, что его элементы изменяются таким образом, что он разреженно представляет данный сигнал наилучшим образом. Выученные словари могут давать более разреженные решения по сравнению с предопределенными матрицами преобразования.
Алгоритмы
Поскольку описанная выше проблема оптимизации может быть решена как выпуклая проблема по отношению к словарю или разреженному кодированию, в то время как другой один из двух является фиксированным, большинство алгоритмов основаны на идее итеративного обновления одного, а затем другого.
Проблема поиска оптимального разреженного кодирования с данным словарем известен как разреженное приближение (или иногда просто проблема разреженного кодирования). Для ее решения был разработан ряд алгоритмов (например, поиск совпадения и LASSO ), которые включены в алгоритмы, описанные ниже.
Метод оптимальных направлений (MOD)
Метод оптимальных направлений (или MOD) был одним из первых методов, предложенных для решения проблемы изучения разреженного словаря. [5] Основная идея состоит в том, чтобы решить задачу минимизации с учетом ограниченного числа ненулевых компонентов вектора представления:
Здесь, обозначает норму Фробениуса . MOD чередует получение разреженного кодирования с использованием такого метода, как поиск соответствия, и обновление словаря путем вычисления аналитического решения проблемы, заданной следующим образом: где является псевдообратной системой Мура-Пенроуза . После этого обновленияперенормируется, чтобы соответствовать ограничениям, и снова получается новое разреженное кодирование. Процесс повторяется до схождения (или до достаточно небольшого остатка).
MOD оказался очень эффективным методом для низкоразмерных входных данных. требуется всего несколько итераций для схождения. Однако из-за высокой сложности операции обращения матрицы вычисление псевдообратной матрицы в случаях большой размерности во многих случаях является неразрешимым. Этот недостаток вдохновил на разработку других методов изучения словарей.
К-СВД
K-SVD - это алгоритм, который выполняет SVD в своей основе для обновления атомов словаря один за другим и в основном является обобщением K-средних . Он обеспечивает, чтобы каждый элемент входных данных кодируется линейной комбинацией не более чем элементы способом, идентичным подходу MOD:
Суть этого алгоритма состоит в том, чтобы сначала исправить словарь, найти наилучшее из возможных. при указанном выше ограничении (с использованием метода ортогонального сопоставления ), а затем итеративно обновлять атомы словаря следующим образом:
Следующие шаги алгоритма включают приближение ранга 1 остаточной матрицы, обновление и обеспечение разреженности после обновления. Этот алгоритм считается стандартным для изучения словарей и используется во множестве приложений. Однако у него есть общие недостатки: MOD эффективен только для сигналов с относительно низкой размерностью и имеет возможность застревать на локальных минимумах.
Стохастический градиентный спуск
Для решения этой проблемы можно также применить широко распространенный метод стохастического градиентного спуска с итеративным проецированием. [6] [7] Идея этого метода состоит в том, чтобы обновить словарь, используя стохастический градиент первого порядка, и спроецировать его на набор ограничений.. Шаг, который происходит на i-й итерации, описывается этим выражением:
, где случайное подмножество а также шаг градиента.
Двойственный метод Лагранжа
Алгоритм, основанный на решении двойной задачи Лагранжа, обеспечивает эффективный способ решения словаря без осложнений, вызванных функцией разреженности. [8] Рассмотрим следующий лагранжиан:
, где ограничение на норму атомов и - так называемые двойственные переменные, образующие диагональную матрицу .
Затем мы можем дать аналитическое выражение для двойника Лагранжа после минимизации по :
.
После применения одного из методов оптимизации к значению двойственного (например , метода Ньютона или сопряженного градиента ) мы получаем значение:
Решение этой проблемы требует меньше вычислительных затрат, поскольку количество двойных переменных во много раз меньше, чем количество переменных в основной задаче.
ЛАССО
При таком подходе задача оптимизации формулируется как:
, где - допустимая ошибка при реконструкции LASSO.
Он находит оценку путем минимизации ошибки наименьших квадратов с учетом ограничения L 1 -нормы в векторе решения, сформулированного как:
, где контролирует компромисс между разреженностью и ошибкой реконструкции. Это дает глобальное оптимальное решение. [9] См. Также изучение онлайн-словарей для разреженного кодирования.
Параметрические методы обучения
Методы параметрического обучения нацелены на то, чтобы объединить лучшее из обоих миров - области аналитически построенных словарей и изученных. [10] Это позволяет создавать более мощные обобщенные словари, которые потенциально могут быть применены к случаям сигналов произвольного размера. Известные подходы включают:
- Переводно-инвариантные словари. [11] Эти словари состоят из переводов атомов, происходящих из словаря, созданного для фрагмента сигнала конечного размера. Это позволяет результирующему словарю предоставить представление для сигнала произвольного размера.
- Мультимасштабные словари. [12] Этот метод фокусируется на создании словаря, который состоит из словарей с различным масштабом для улучшения разреженности.
- Скудные словари. [13] Этот метод направлен не только на обеспечение разреженного представления, но и на создание разреженного словаря, который обеспечивается выражением где предопределенный аналитический словарь с желательными свойствами, такими как быстрое вычисление и является разреженной матрицей. Такая формулировка позволяет напрямую сочетать быструю реализацию аналитических словарей с гибкостью разреженных подходов.
Обучение онлайн-словарю ( подход LASSO )
Многие распространенные подходы к изучению разреженных словарей основаны на том факте, что все входные данные (или, по крайней мере, достаточно большой набор обучающих данных) для алгоритма. Однако в реальном сценарии это может быть не так, поскольку размер входных данных может быть слишком большим, чтобы уместить их в памяти. Другой случай, когда это предположение невозможно сделать, - это когда входные данные поступают в виде потока . Такие случаи лежат в области изучения онлайн-обучения, которое, по сути, предполагает итеративное обновление модели по новым точкам данных. становится доступным.
Словарь можно выучить в режиме онлайн следующим образом: [14]
- Для
- Нарисуйте новый образец
- Найдите разреженное кодирование с помощью LARS :
- Обновить словарь с использованием блочно-координатного подхода:
Этот метод позволяет нам постепенно обновлять словарь по мере того, как новые данные становятся доступными для обучения разреженному представлению, и помогает значительно сократить объем памяти, необходимый для хранения набора данных (который часто имеет огромный размер).
Приложения
Среда обучения словарю, а именно линейная декомпозиция входного сигнала с использованием нескольких базовых элементов, извлеченных из самих данных, привела к современным результатам в различных задачах обработки изображений и видео. Этот метод может быть применен к задачам классификации таким образом, что, если мы создали определенные словари для каждого класса, входной сигнал можно было классифицировать, найдя словарь, соответствующий самому разреженному представлению.
Он также имеет свойства, которые полезны для шумоподавления сигнала, поскольку обычно можно выучить словарь, чтобы представлять значимую часть входного сигнала разреженным образом, но шум на входе будет иметь гораздо менее разреженное представление. [15]
Разреженное изучение словаря успешно применялось к различным задачам обработки изображений, видео и аудио, а также к синтезу текстур [16] и неконтролируемой кластеризации. [17] В оценках с Bag-оф-слов модели, [18] [19] разреженное кодирование Эмпирический опережать другие подходы кодирования на категорию объекта распознавания задач.
Обучение по словарю используется для детального анализа медицинских сигналов. К таким медицинским сигналам относятся сигналы электроэнцефалографии (ЭЭГ), электрокардиографии (ЭКГ), магнитно-резонансной томографии (МРТ), функциональной МРТ (фМРТ) и ультразвуковой компьютерной томографии (УЗКТ), где для анализа каждого сигнала используются разные предположения.
Смотрите также
- Разреженное приближение
- Редкий PCA
- Факторизация матрицы
- К-СВД
- Нейронное разреженное кодирование
- SimCO
Рекомендации
- ^ Needell, D .; Тропп, Дж. А. (2009). «CoSaMP: Итеративное восстановление сигнала из неполных и неточных выборок». Прикладной и вычислительный гармонический анализ . 26 (3): 301–321. arXiv : 0803.2392 . DOI : 10.1016 / j.acha.2008.07.002 .
- ^ Lotfi, M .; Видьясагар, М. « Быстрый неитерационный алгоритм для измерения сжатия с использованием двоичных измерительных матриц »
- ^ AM Тиллманн, « О вычислительной неразрешимости точного и приближенного изучения словаря », IEEE Signal Processing Letters 22 (1), 2015: 45–49.
- ^ Донохо, Дэвид Л. (01.06.2006). «Для большинства больших недоопределенных систем линейных уравнений решение с минимальной 1-нормой также является самым разреженным решением». Сообщения по чистой и прикладной математике . 59 (6): 797–829. DOI : 10.1002 / cpa.20132 . ISSN 1097-0312 .
- ^ Энган, К .; Aase, SO; Хакон Хусой, Дж. (1 января 1999 г.). Метод оптимальных направлений для каркасного дизайна . 1999 Международная конференция IEEE по акустике, речи и обработке сигналов, 1999. Труды . 5 . С. 2443–2446 т.5. DOI : 10.1109 / ICASSP.1999.760624 . ISBN 978-0-7803-5041-0. S2CID 33097614 .
- ^ Аарон, Михал; Элад, Майкл (2008). «Разреженное и избыточное моделирование содержания изображения с использованием словаря подписи изображений». SIAM Journal on Imaging Sciences . 1 (3): 228–247. CiteSeerX 10.1.1.298.6982 . DOI : 10.1137 / 07070156x .
- ^ Пинтер, Янош Д. (1 января 2000 г.). Яир Цензор и Ставрос А. Зениос, Параллельная оптимизация - теория, алгоритмы и приложения. Oxford University Press, Нью-Йорк / Оксфорд, 1997, xxviii + 539 страниц. (85 долларов США) . Журнал глобальной оптимизации . 16 . С. 107–108. DOI : 10,1023 / A: 1008311628080 . ISBN 978-0-19-510062-4. ISSN 0925-5001 . S2CID 22475558 .
- ^ Ли, Хонглак и др. «Эффективные алгоритмы разреженного кодирования». Достижения в области нейронных систем обработки информации . 2006 г.
- ^ Кумар, Абхай; Катария, Саураб. «Приложения на основе словарного обучения в обработке изображений с использованием выпуклой оптимизации» (PDF) .
- ^ Рубинштейн, Р .; Bruckstein, AM; Элад, М. (01.06.2010). "Словари для моделирования разреженных представлений". Труды IEEE . 98 (6): 1045–1057. CiteSeerX 10.1.1.160.527 . DOI : 10.1109 / JPROC.2010.2040551 . ISSN 0018-9219 . S2CID 2176046 .
- ^ Энган, Кьерсти ; Скреттинг, Карл; Хусой, Джон Хейкон (01.01.2007). "Семейство итеративных алгоритмов обучения словаря на основе LS, ILS-DLA, для разреженного представления сигналов". Цифра. Сигнальный процесс . 17 (1): 32–49. DOI : 10.1016 / j.dsp.2006.02.002 . ISSN 1051-2004 .
- ^ Mairal, J .; Sapiro, G .; Элад, М. (01.01.2008). «Изучение многомасштабных разреженных представлений для восстановления изображений и видео». Многомасштабное моделирование и симуляция . 7 (1): 214–241. CiteSeerX 10.1.1.95.6239 . DOI : 10.1137 / 070697653 . ISSN 1540-3459 .
- ^ Рубинштейн, Р .; Зибулевский, М .; Элад, М. (01.03.2010). "Двойная разреженность: изучение разреженных словарей для аппроксимации разреженных сигналов". Транзакции IEEE по обработке сигналов . 58 (3): 1553–1564. Bibcode : 2010ITSP ... 58.1553R . CiteSeerX 10.1.1.183.992 . DOI : 10.1109 / TSP.2009.2036477 . ISSN 1053-587X . S2CID 7193037 .
- ^ Майраль, Жюльен; Бах, Фрэнсис; Понсе, Жан; Сапиро, Гильермо (01.03.2010). «Онлайн-обучение матричной факторизации и разреженному кодированию» . J. Mach. Учить. Res . 11 : 19–60. arXiv : 0908.0050 . Bibcode : 2009arXiv0908.0050M . ISSN 1532-4435 .
- ^ Арон, М, М Elad и А Bruckstein. 2006. «K-SVD: алгоритм для разработки переполненных словарей для разреженного представления». Обработка сигналов, транзакции IEEE на 54 (11): 4311-4322
- ^ Пейре, Габриэль (6 ноября 2008 г.). «Разреженное моделирование текстур» (PDF) . Журнал математической визуализации и зрения . 34 (1): 17–31. DOI : 10.1007 / s10851-008-0120-3 . ISSN 0924-9907 . S2CID 15994546 .
- ^ Рамирес, Игнасио; Шпрехманн, Пабло; Сапиро, Гильермо (01.01.2010). Классификация и кластеризация посредством изучения словаря со структурированной несогласованностью и общими функциями . Конференция IEEE 2014 года по компьютерному зрению и распознаванию образов . 0 . Лос-Аламитос, Калифорния, США: Компьютерное общество IEEE. С. 3501–3508. DOI : 10.1109 / CVPR.2010.5539964 . ISBN 978-1-4244-6984-0. S2CID 206591234 .
- ^ Конюш, Петр; Ян, Фэй; Миколайчик, Кристиан (01.05.2013). «Сравнение подходов к кодированию функций среднего уровня и стратегий объединения при обнаружении визуальных концепций». Компьютерное зрение и понимание изображений . 117 (5): 479–492. CiteSeerX 10.1.1.377.3979 . DOI : 10.1016 / j.cviu.2012.10.010 . ISSN 1077-3142 .
- ^ Конюш, Петр; Ян, Фэй; Госслен, Филипп Анри; Миколайчик, Кристиан (24.02.2017). «Объединение вхождений более высокого порядка для мешков со словами: визуальное определение концепции» (PDF) . IEEE Transactions по анализу шаблонов и машинному анализу . 39 (2): 313–326. DOI : 10.1109 / TPAMI.2016.2545667 . hdl : 10044/1/39814 . ISSN 0162-8828 . PMID 27019477 .