Словарное обучение / разреженное кодирование (Dictionary Learning, K-SVD)

Материал из MachineLearning.

Статья написана с использованием LLM Claude Sonnet 5 и проверена участником Участник:Georgii Kvaratsкheliia 18 июля 2026

Промпт приводится полностью в Обсуждение: Словарное обучение / разреженное кодирование (Dictionary Learning, K-SVD)

Содержание

1 Определение
- 1.1 Разреженное кодирование при фиксированном словаре
- 1.2 Совместная задача словарного обучения
2 Мотивация
3 История
4 Алгоритмы
5 Теоретические аспекты: единственность и точное восстановление
6 Применения в машинном обучении и искусственном интеллекте
7 Ограничения и практические аспекты
8 См. также
9 Примечания
10 Литература

Словарное обучение / разреженное кодирование (англ. dictionary learning, K-SVD) и тесно связанное с ним разреженное кодирование (англ. sparse coding) — семейство методов обучения без учителя, в которых сигналы (изображения, звук, признаки) представляются как линейные комбинации небольшого числа элементов («атомов») из избыточного, настраиваемого по данным набора базисных векторов — словаря. В отличие от классических ортогональных базисов (Фурье, вейвлеты, главные компоненты), словарь при словарном обучении, как правило, избыточен (число атомов больше размерности сигнала) и обучается непосредственно по обучающей выборке, а каждое отдельное наблюдение раскладывается лишь по небольшому числу атомов — отсюда «разреженность» кодов.

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

Определение

Разреженное кодирование при фиксированном словаре

Пусть $D\in\mathbb{R}^{n\times K}$ — словарь из $K$ атомов-столбцов (как правило, $K>n$ , то есть словарь избыточен), а $y\in\mathbb{R}^n$ — наблюдаемый сигнал. Задача разреженного кодирования — найти коэффициенты $x\in\mathbb{R}^K$ , приближающие $y\approx Dx$ при малом числе ненулевых компонент:

$\min_{x}\ \|y-Dx\|_2^2$ при $\|x\|_0\le T,$

где $\|x\|_0$ — число ненулевых координат («псевдонорма» $\ell_0$ ), а $T\ll K$ — заданный уровень разреженности. Эквивалентная штрафная (лагранжева) форма:

$\min_{x}\ \frac12\|y-Dx\|_2^2 + \lambda\|x\|_0.$

Совместная задача словарного обучения

Для обучающей выборки из $N$ сигналов $Y=[y_1,\dots,y_N]\in\mathbb{R}^{n\times N}$ словарное обучение ставит задачу совместного поиска словаря $D$ и матрицы кодов $X=[x_1,\dots,x_N]\in\mathbb{R}^{K\times N}$ :

$\min_{D,\,X}\ \|Y-DX\|_F^2$ при $\|x_i\|_0\le T\ \ \forall i,\qquad \|d_j\|_2=1\ \ \forall j,$

где ограничение на норму столбцов словаря $d_j$ устраняет тривиальную неоднозначность масштаба между $D$ и $X$ . Эта задача формально представляет собой билинейную факторизацию матрицы $Y$ , родственную матричным и тензорным разложениям, но с явным ограничением разреженности на один из факторов вместо ограничений ортогональности (как в PCA) или неотрицательности (как в NMF).

Мотивация

Избыточные словари гибче фиксированных базисов. Классические ортогональные преобразования (дискретное косинусное, вейвлеты) фиксированы заранее и не адаптируются к статистике конкретных данных; обучаемый избыточный словарь может представлять сигнал существенно более компактно (меньшим числом ненулевых коэффициентов при той же точности), поскольку подбирается именно под структуру рассматриваемого класса сигналов.
Разреженность как естественный статистический приор. Многие природные сигналы — фрагменты естественных изображений, речь, музыка — хорошо приближаются малым числом «типичных» локальных структур (краёв, текстур, гармоник); это наблюдение восходит к исследованию рецептивных полей простых клеток зрительной коры и объясняет, почему разреженное представление одновременно эффективно вычислительно и биологически правдоподобно.
Устойчивость к шуму и выбросам. Поскольку истинный сигнал предполагается разреженно представимым, а типичный аддитивный шум — нет, проекция на разреженное представление по обученному словарю естественным образом действует как фильтр шума.
Связь со сжатым зондированием. Если сигнал действительно разрежен в некотором базисе, теория сжатого зондирования (compressed sensing) гарантирует возможность его точного восстановления по существенно меньшему числу линейных измерений, чем размерность самого сигнала — разреженное представление данных является предпосылкой для применения этой теории.

История

Основополагающей для всей области стала работа Олсхаузена и Филда 1996 года, показавшая, что алгоритм обучения, максимизирующий разреженность кода при представлении фрагментов естественных изображений, самостоятельно порождает базисные функции, локализованные, ориентированные и избирательные по масштабу — то есть в точности воспроизводящие свойства рецептивных полей простых клеток первичной зрительной коры[1]; развитие этой идеи для избыточных базисов было дано авторами годом позже[2]. Параллельно в теории обработки сигналов развивались жадные алгоритмы разреженной аппроксимации по фиксированному избыточному словарю: Маллат и Чжан предложили метод согласованного преследования (Matching Pursuit) в 1993 году[3], а чуть позже Чен, Донохо и Сондерс сформулировали выпуклую $\ell_1$ -релаксацию задачи под названием Basis Pursuit[4].

Первые алгоритмы, обучающие сам словарь (а не только код по фиксированному словарю), появились на рубеже 1990-х и 2000-х: Энган, Осе и Хёсой предложили метод оптимальных направлений (Method of Optimal Directions, MOD) в 1999 году — точное обновление словаря в замкнутой форме при фиксированных кодах[5]. В 2003 году Донохо и Элад дали строгие условия единственности разреженного представления в терминах взаимной когерентности словаря, заложив теоретический фундамент области[6]. Флагманский алгоритм словарного обучения — K-SVD — предложили Ахарон, Элад и Брукштейн в 2006 году, обобщив MOD последовательным атомарным обновлением словаря через SVD[7]; в том же году Элад и Ахарон показали, что обученный K-SVD словарь даёт передовые на тот момент результаты в задаче шумоподавления изображений[8]. Обзорная статья Брукштейна, Донохо и Элада 2009 года стала стандартной точкой входа в теорию и практику разреженных представлений для более широкой аудитории[9].

В компьютерном зрении разреженное представление получило известность благодаря работе Райта, Янга, Ганеша, Састри и Ма 2009 года о распознавании лиц через разреженное представление (Sparse Representation-based Classification), устойчивое к затенению и искажениям[10]. Проблему масштабируемости словарного обучения на очень большие наборы данных решили Майраль, Бах, Понс и Сапиро, предложившие в 2009—2010 годах онлайн-алгоритм на основе стохастической аппроксимации, обрабатывающий обучающие сигналы последовательно, а не пакетно[11][12]. Наконец, в 2010 году Грегор и Лекун показали, что итеративный алгоритм разреженного кодирования можно «развернуть» в неглубокую нейронную сеть с обучаемыми весами (LISTA), на порядки ускоряющую вычисление приближённого разреженного кода по сравнению с классическими итеративными методами — один из первых примеров техники алгоритмического разворачивания (algorithm unrolling), впоследствии широко применяемой в глубоком обучении для физически интерпретируемых архитектур[13].

Алгоритмы

Жадные и выпуклые методы разреженного кодирования

Задача с ограничением $\|x\|_0\le T$ в общем случае NP-трудна, поэтому на практике применяют либо жадные приближённые алгоритмы, либо выпуклую релаксацию. Ортогональное согласованное преследование (Orthogonal Matching Pursuit, OMP) на каждом шаге добавляет к текущему носителю атом, наиболее коррелированный с остатком, и пересчитывает коэффициенты методом наименьших квадратов по всему текущему носителю, повторяя это до достижения заданной разреженности[3]. Альтернативный подход — заменить $\ell_0$ на выпуклую $\ell_1$ -норму:

$\min_{x}\ \frac12\|y-Dx\|_2^2 + \lambda\|x\|_1,$

известную как Basis Pursuit (в статистике — регрессия LASSO)[4][14]; при определённых условиях на словарь решения задач с $\ell_0$ и $\ell_1$ совпадают, что оправдывает использование выпуклой, эффективно решаемой релаксации вместо исходной комбинаторной задачи[6].

Обновление словаря при фиксированных кодах

При фиксированной матрице кодов $X$ задача $\min_D\|Y-DX\|_F^2$ становится обычной задачей наименьших квадратов, решаемой в замкнутой форме (метод MOD):

$D \leftarrow YX^\top(XX^\top)^{-1},$

с последующей перенормировкой столбцов $D$ к единичной норме[5]. K-SVD уточняет эту идею, обновляя атомы словаря не все сразу, а последовательно, по одному: для атома $d_k$ вычисляется матрица ошибки, накопленной всеми остальными атомами, — $E_k=Y-\sum_{j\ne k}d_jx_j^\top$ , — эта ошибка ограничивается только теми столбцами (сигналами), где атом $k$ реально используется ( $x_k\ne0$ ), после чего атом $d_k$ и соответствующая строка коэффициентов одновременно обновляются как наилучшее ранг-1 приближение этой ограниченной матрицы ошибки — то есть через SVD:

$E_k^R = U\Sigma V^\top,\qquad d_k \leftarrow u_1,\qquad x_k^R \leftarrow \sigma_1 v_1^\top,$

где $u_1,v_1$ — первые сингулярные векторы, а $\sigma_1$ — наибольшее сингулярное число[7]. Такое поатомное обновление на основе SVD и дало алгоритму название K-SVD.

Связь с альтернированной минимизацией

И MOD, и K-SVD в целом следуют одной и той же двухблоковой схеме: зафиксировать словарь и найти разреженные коды (жадным или выпуклым методом разреженного кодирования), затем зафиксировать коды и точно обновить словарь, и повторять эти два шага до сходимости — это в точности схема альтернированной минимизации, применённая к билинейной, но при этом ограниченной по разреженности задаче факторизации матрицы. Отличие от классической точной AM в том, что шаг кодирования сам по себе решается лишь приближённо (жадно или через выпуклую релаксацию NP-трудной задачи), поэтому строгие гарантии монотонной сходимости, справедливые для точной альтернированной минимизации, здесь распространяются на неё лишь частично.

Онлайн и стохастические алгоритмы

Для очень больших обучающих выборок хранение всей матрицы $Y$ и её кодов в памяти непрактично. Майраль с соавторами предложили онлайн-схему, обрабатывающую сигналы по одному (или малыми пакетами): для каждого нового сигнала вычисляется его разреженный код по текущему словарю, после чего словарь обновляется методом стохастической аппроксимации с накоплением статистик второго порядка — с доказанной сходимостью к стационарной точке исходной невыпуклой задачи и значительно лучшей масштабируемостью, чем у пакетных методов вроде K-SVD[11][12].

Теоретические аспекты: единственность и точное восстановление

Ключевой теоретический вопрос — при каких условиях на словарь разреженное представление сигнала единственно (а значит, содержательно интерпретируемо, а не артефакт конкретного алгоритма). Донохо и Элад ввели понятие спарка словаря $\operatorname{spark}(D)$ — минимального числа линейно зависимых столбцов $D$ — и показали, что если сигнал имеет представление с $\|x\|_0<\operatorname{spark}(D)/2$ , то это представление единственно среди всех решений с тем же числом ненулевых компонент[6]. Более практичная (хотя и более консервативная) оценка использует взаимную когерентность словаря $\mu(D)=\max_{i\ne j}|d_i^\top d_j|$ : разреженное решение с $\|x\|_0<\frac12\bigl(1+1/\mu(D)\bigr)$ гарантированно единственно и совпадает с решением, которое находит и выпуклая $\ell_1$ -релаксация[6]. Эти результаты — прямой мост к теории сжатого зондирования, где аналогичные условия (в частности, свойство ограниченной изометрии) гарантируют точное восстановление разреженных сигналов по случайным линейным измерениям.

Применения в машинном обучении и искусственном интеллекте

Шумоподавление и восстановление изображений

Обучив словарь на фрагментах чистых (или самих же зашумлённых) изображений, можно очистить каждый зашумлённый фрагмент, найдя его наилучшее разреженное представление по словарю и заменив исходный фрагмент реконструкцией — подход K-SVD-шумоподавления Элада и Ахарона на момент публикации превзошёл современные ему методы, основанные на фиксированных вейвлет-базисах[8].

Классификация через разреженное представление

В задаче распознавания лиц по Райту и соавторам тестовое изображение представляется как разреженная линейная комбинация обучающих изображений всех классов сразу; класс определяется тем подмножеством обучающих примеров, которое даёт наименьшую ошибку реконструкции — при этом метод демонстрирует устойчивость к значительным затенениям и искажениям именно благодаря разреженности решения[10].

Обучение признаков без учителя

Разреженное кодирование — один из ранних и влиятельных примеров обучения признаков без учителя: вместо ручного проектирования признаков локальные разреженные коды по обученному словарю сами по себе служат входом для последующих классификаторов, что предвосхитило современный принцип обучения представлений (representation learning) в глубоких сетях.

Развёрнутые (unrolled) нейросетевые архитектуры

LISTA Грегора и Лекуна показывает, что итеративный алгоритм разреженного кодирования (пороговая итеративная схема ISTA) можно интерпретировать как рекуррентную сеть с фиксированными весами, а затем обучить веса этой сети так, чтобы за фиксированное малое число слоёв (шагов) получать точность, для которой классическому итеративному алгоритму потребовались бы на порядки больше итераций[13]. Эта идея — «развёртывание» классического оптимизационного алгоритма в обучаемую нейронную сеть — стала самостоятельным направлением проектирования архитектур в задачах обратных и некорректно поставленных задач.

Сжатое зондирование

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

Ограничения и практические аспекты

Вычислительная стоимость шага кодирования. В отличие от точных блочных подзадач классической альтернированной минимизации, шаг разреженного кодирования сам по себе не имеет замкнутого решения и требует итеративного (жадного или выпуклого) решателя на каждой внешней итерации словарного обучения — это основная вычислительная нагрузка метода.
Невыпуклость и чувствительность к инициализации. Совместная задача словарного обучения невыпукла даже при выпуклом шаге кодирования; K-SVD и MOD сходятся, как правило, лишь к локальному минимуму, а качество результата зависит от начального словаря.
Выбор параметров. Число атомов словаря $K$ , уровень разреженности $T$ (или вес регуляризации $\lambda$ ) — гиперпараметры, которые на практике подбираются кросс-валидацией или экспертным знанием о предметной области; избыточный словарь при малом $T$ и большом $K$ может переобучаться на шум обучающей выборки.
Сравнение с родственными разложениями. PCA даёт плотные ортогональные компоненты, оптимальные для одного фиксированного числа компонент сразу; NMF добавляет ограничение неотрицательности; словарное обучение — единственное среди них, что явно поощряет структурную разреженность индивидуальных кодов при сохранении избыточности (переполноты) самого базиса, что даёт более гибкие, адаптированные к данным представления ценой более дорогого вычисления кодов.

См. также

Примечания

Olshausen B. A., Field D. J. Emergence of simple-cell receptive field properties by learning a sparse code for natural images // Nature. — 1996. — Т. 381, № 6583. — С. 607–609.
Olshausen B. A., Field D. J. Sparse coding with an overcomplete basis set: A strategy employed by V1? // Vision Research. — 1997. — Т. 37, № 23. — С. 3311–3325.
Mallat S. G., Zhang Z. Matching pursuits with time-frequency dictionaries // IEEE Transactions on Signal Processing. — 1993. — Т. 41, № 12. — С. 3397–3415.
Chen S. S., Donoho D. L., Saunders M. A. Atomic decomposition by basis pursuit // SIAM Journal on Scientific Computing. — 1998. — Т. 20, № 1. — С. 33–61.
Engan K., Aase S. O., Husøy J. H. Method of optimal directions for frame design // Proceedings of IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP). — 1999. — Т. 5. — С. 2443–2446.
Donoho D. L., Elad M. Optimally sparse representation in general (nonorthogonal) dictionaries via $\ell^1$ minimization // Proceedings of the National Academy of Sciences. — 2003. — Т. 100, № 5. — С. 2197–2202.
Aharon M., Elad M., Bruckstein A. K-SVD: An Algorithm for Designing Overcomplete Dictionaries for Sparse Representation // IEEE Transactions on Signal Processing. — 2006. — Т. 54, № 11. — С. 4311–4322.
Elad M., Aharon M. Image Denoising Via Sparse and Redundant Representations Over Learned Dictionaries // IEEE Transactions on Image Processing. — 2006. — Т. 15, № 12. — С. 3736–3745.
Bruckstein A. M., Donoho D. L., Elad M. From Sparse Solutions of Systems of Equations to Sparse Modeling of Signals and Images // SIAM Review. — 2009. — Т. 51, № 1. — С. 34–81.
Wright J., Yang A. Y., Ganesh A., Sastry S. S., Ma Y. Robust Face Recognition via Sparse Representation // IEEE Transactions on Pattern Analysis and Machine Intelligence. — 2009. — Т. 31, № 2. — С. 210–227.
Mairal J., Bach F., Ponce J., Sapiro G. Online Dictionary Learning for Sparse Coding // Proceedings of the 26th International Conference on Machine Learning (ICML). — 2009. — С. 689–696.
Mairal J., Bach F., Ponce J., Sapiro G. Online Learning for Matrix Factorization and Sparse Coding // Journal of Machine Learning Research. — 2010. — Т. 11. — С. 19–60.
Gregor K., LeCun Y. Learning Fast Approximations of Sparse Coding // Proceedings of the 27th International Conference on Machine Learning (ICML). — 2010. — С. 399–406.
Tibshirani R. Regression Shrinkage and Selection via the Lasso // Journal of the Royal Statistical Society: Series B. — 1996. — Т. 58, № 1. — С. 267–288.

Литература

Bruckstein A. M., Donoho D. L., Elad M. From Sparse Solutions of Systems of Equations to Sparse Modeling of Signals and Images // SIAM Review. — 2009. — Т. 51, № 1. — С. 34–81.
Aharon M., Elad M., Bruckstein A. K-SVD: An Algorithm for Designing Overcomplete Dictionaries for Sparse Representation // IEEE Transactions on Signal Processing. — 2006. — Т. 54, № 11. — С. 4311–4322.
Mairal J., Bach F., Ponce J., Sapiro G. Online Learning for Matrix Factorization and Sparse Coding // Journal of Machine Learning Research. — 2010. — Т. 11. — С. 19–60.
Olshausen B. A., Field D. J. Emergence of simple-cell receptive field properties by learning a sparse code for natural images // Nature. — 1996. — Т. 381. — С. 607–609.
Donoho D. L., Elad M. Optimally sparse representation in general (nonorthogonal) dictionaries via $\ell^1$ minimization // Proceedings of the National Academy of Sciences. — 2003. — Т. 100, № 5. — С. 2197–2202.
Wright J., Yang A. Y., Ganesh A., Sastry S. S., Ma Y. Robust Face Recognition via Sparse Representation // IEEE Transactions on Pattern Analysis and Machine Intelligence. — 2009. — Т. 31, № 2. — С. 210–227.

Источник — «http://poligon.machinelearning.ru/wiki/index.php?title=%D0%A1%D0%BB%D0%BE%D0%B2%D0%B0%D1%80%D0%BD%D0%BE%D0%B5_%D0%BE%D0%B1%D1%83%D1%87%D0%B5%D0%BD%D0%B8%D0%B5_/_%D1%80%D0%B0%D0%B7%D1%80%D0%B5%D0%B6%D0%B5%D0%BD%D0%BD%D0%BE%D0%B5_%D0%BA%D0%BE%D0%B4%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5_%28Dictionary_Learning%2C_K-SVD%29»