Векторное квантование


Векторное квантование

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

По способам настройки входных весов сумматоров и по решаемым задачам различают много разновидностей сетей Кохонена.[1] Наиболее известные из них:

  • Сети векторного квантования сигналов[2], тесно связанные с простейшим базовым алгоритмом кластерного анализа (метод динамических ядер или K-средних, то есть Самоорганизующиеся карты Кохонена (Self-Organising Maps, SOM)[3]
  • Сети векторного квантования, обучаемые с учителем (Learning Vector Quantization)[4]

Содержание

Слой Кохонена

Базовая версия

Слой Кохонена состоит из некоторого количества n параллельно действующих линейных элементов. Все они имеют одинаковое число входов m и получают на свои входы один и тот же вектор входных сигналов x = (x1,...xm). На выходе jго линейного элемента получаем сигнал

y_j=w_{j0} + \sum_{i=1}^m w_{ji}x_i,

где wji — весовой коэффициент iго входа jго нейрона, wj0 — пороговой коэффициент.

После прохождения слоя линейных элементов сигналы посылаются на обработку по правилу «победитель забирает всё»: среди выходных сигналов yj ищется максимальный; его номер jmax = argmaxj{yj}. Окончательно, на выходе сигнал с номером jmax равен единице, остальные — нулю. Если максимум одновременно достигается для нескольких jmax, то либо принимают все соответствующие сигналы равными единице, либо только первый в списке (по соглашению). «Нейроны Кохонена можно воспринимать как набор электрических лампочек, так что для любого входного вектора загорается одна из них.»[5]

Геометрическая интерпретация

Разбиение плоскости на многоугольники Вороного-Дирихле для случайно выбранных точек (каждая точка указана в своём многоугольнике).

Большое распространение получили слои Кохонена, построенные следующим образом: каждому (jму) нейрону сопоставляется точка Wj = (wj1,...wjm) в m-мерном пространстве (пространстве сигналов). Для входного вектора x = (x1,...xm) вычисляется его расстояния ρj(x) до точек Wj и «ближайший получает всё» — тот нейрон, для которого это расстояние минимально, выдаёт единицу, остальные — нули. Следует заметить, что для сравнения расстояний достаточно вычислять линейную функцию сигнала:

\rho_j(x)^2=\|x-W_j\|^2=\|W_j\|^2-2\sum_{i=1}^m w_{ji}x_i + \|x\|^2.

Последнее слагаемое \|x\|^2 одинаково для всех нейронов, поэтому для нахождения ближайшей точки оно не нужно. Задача сводится к поиску номера наибольшего из значений линейных функций:

j_{\max}={\rm arg} \max_{j}\{\sum_{i=1}^m w_{ji}x_i-\frac{1}{2}\|W_j\|^2\}.

Таким образом, координаты точки Wj = (wj1,...wjm) совпадают с весами линейного нейрона слоя Кохонена (при этом значение порогового коэффициента w_{j0} =-\|W_j\|^2/2 ).

Если заданы точки Wj = (wj1,...wjm), то m-мерное пространство разбивается на соответствующие многогранники Вороного-Дирихле Vj: многогранник Vj состоит из точек, которые ближе к Wj, чем к другим Wk (k \neq j).[6]

Сети векторного квантования

Задача векторного квантования с k кодовыми векторами Wj для заданной совокупности входных векторов S ставится как задача минимизации искажения при кодировании, то есть при замещении каждого вектора из S соответствующим кодовым вектором. В базовом варианте сетей Кохонена используется метод наименьших квадратов и искажение D вычисляется по формуле

D=\sum_{j=1}^k \sum_{x \in K_j}\|x-W_j\|^2,

где Kj состоит из тех точек x \in S, которые ближе к Wj, чем к другим Wl (l \neq j). Другими словами, Kj состоит из тех точек x \in S, которые кодируются кодовым вектором Wj.

Если совокупность S задана и хранится в памяти, то стандартным выбором в обучении соответствующей сети Кохонена является метод K-средних. Это метод расщепления:

  • при данном выборе кодовых векторов (они же весовые векторы сети) Wj минимизацией D находим множества Kj — они состоит из тех точек x \in S, которые ближе к Wj, чем к другим Wl;
  • при данном разбиении S на множества Kj минимизацией D находим оптимальные позиции кодовых векторов Wj — для оценки по методу наименьших квадратов это просто средние арифметические:
W_j=\frac{1}{|K_j|}\sum_{x \in K_j} x,

где | Kj |  — число элементов в Kj.

Далее итерируем. Этот метод расщепления сходится за конечное число шагов и даёт локальный минимум искажения.

Если же, например, совокупность S заранее не задана, или по каким-либо причинам не хранится в памяти, то широко используется онлайн метод. Векторы входных сигналов x обрабатываются по одному, для каждого из них находится ближайший кодовый вектор («победитель», который «забирает всё») Wj(x). После этого данный кодовый вектор пересчитывается по формуле

W^{\rm new}_{j(x)}=W^{\rm old}_{j(x)}(1-\theta)+x\theta,

где \theta \in (0,1) — шаг обучения. Остальные кодовые векторы на этом шаге не изменяются.

Для обеспечения стабильности используется онлайн метод с затухающей скоростью обучения: если T — количество шагов обучения, то полагают θ = θ(T). Функцию θ(T) > 0 выбирают таким образом, чтобы \theta(T) \to 0 монотонно при T \to \infty и чтобы ряд \sum_{T=1}^{\infty}\theta(T) расходился, например, θ(T) = θ0 / T.

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

Самоорганизующиеся карты Кохонена

Идея и алгоритм обучения

Задача векторного квантования состоит, по своему существу, в наилучшей аппроксимации всей совокупности векторов данных k кодовыми векторами Wj. Самоорганизующиеся карты Кохонена также аппроксимируют данные, однако при наличии дополнительной структуры в совокупности кодовых векторов (англ. codebook). Предполагается, что априори задана некоторая симметричная таблица «мер соседства» (или «мер близости») узлов: для каждой пары j,l (j,l = 1,...k) определено число ηjl (0 \leq \eta_{jl} \leq 1) при этом диагональные элементы таблицы близости равны единице (ηjj = 1).

Векторы входных сигналов x обрабатываются по одному, для каждого из них находится ближайший кодовый вектор («победитель», который «забирает всё») Wj(x). После этого все кодовые векторы Wl, для которых \eta_{j(x)l}\neq 0, пересчитываются по формуле

W^{\rm new}_l=W^{\rm old}_l(1- \eta_{j(x)l} \theta)+x\eta_{j(x)l} \theta,

где \theta \in (0,1) — шаг обучения. Соседи кодового вектора — победителя (по априорно заданной таблице близости) сдвигаются в ту же сторону, что и этот вектор, пропорционально мере близости.

Чаще всего, таблица кодовых векторов представляется в виде фрагмента квадратной решётки на плоскости, а мера близости определяется, исходя из евклидового расстояния на плоскости.

Самоорганизующиеся карты Кохонена служат, в первую очередь, для визуализации и первоначального («разведывательного») анализа данных.[7] Каждая точка данных отображается соответствующим кодовым вектором из решётки. Так получают представление данных на плоскости («карту данных»). На этой карте возможно отображение многих слоёв: количество данных, попадающих в узлы (то есть «плотность данных»), различные функции данных и так далее. При отображении этих слоёв полезен аппарат географических информационных систем (ГИС). В ГИС подложкой для изображения информационных слоев служит географическая карта. Карта данных является подложкой для произвольного по своей природе набора данных. Она служит заменой географической карте там, где ее просто не существует. Принципиальное отличие в следующем: на географической карте соседние объекты обладают близкими географическими координатами, на карте данных близкие объекты обладают близкими свойствами. С помощью карты данных можно визуализировать данные, одновременно нанося на подложку сопровождающую информацию (подписи, аннотации, атрибуты, информационные раскраски).[7] Карта служит также информационной моделью данных. С её помощью можно заполнять пробелы в данных. Эта способность используется, например, для решения задач прогнозирования.

Самоорганизующиеся карты и главные многообразия

Идея самоорганизующихся карт очень привлекательна и породила массу обобщений, однако, строго говоря, мы не знаем, что мы строим: карта — это результат работы алгоритма и не имеет отдельного («объектного») определения. Есть, однако, близкая теоретическая идея — главные многообразия (principal manifolds).[8] Эти многообразия обобщают линейные главные компоненты. Они были введены как линии или поверхности, проходящие через «середину» распределения данных, с помощью условия самосогласованности: каждая точка x на главном многообразии M является условным математическим ожиданием тех векторов z, которые проектируются на x (при условии x = P(z), где P — оператор проектирования окрестности M на M),

x=\mathbf{E}(z|P(z)=x).

Самоорганизующиеся карты могут рассматриваться как аппроксимации главных многообразий и популярны в этом качестве[9].

Упругие карты

Визуализация набора данных по экспрессии генов в раке молочной железы с использованием упругих карт (b) и метода главных компонент (c). Классы точек показаны с использованием размера (ER - статуc эстроген-рецептора), формы (GROUP - риск развития метастаз) и цвета (TYPE - молекулярный тип опухоли). На панели (a) показана конфигурация узлов двумерной упругой карты в проекции на первые три главные компоненты. Сравнивая (b) и (c), можно заметить, что базальный тип опухоли как кластер лучше отделен на нелинейной проекции (b).

Метод аппроксимации многомерных данных, основанный на минимизации «энергии упругой деформации» карты, погружённой в пространство данных, был предложен А. Н. Горбанём в 1996 году, и впоследствии развит им совместно с А. Ю. Зиновьевым, А. А. Россиевым и А. А. Питенко.[7] Метод основан на аналогии между главным многообразием и эластичной мембраной и упругой пластиной. В этом смысле он является развитием классической идеи сплайна (хотя упругие карты и не являются многомерными сплайнами).

Пусть задана совокупность входных векторов S. Так же, как и сети векторного квантования и самоорганизующиеся карты, упругая карта представлена как совокупность кодовых векторов (узлов) Wj в пространстве сигналов. Множество данных S разделено на классы Kj, состоящие из тех точек x \in S, которые ближе к Wj, чем к другим Wl (l \neq j). Искажение кодирования D

D=\sum_{j=1}^k \sum_{x \in K_j}\|x-W_j\|^2,

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

На множестве узлов задана дополнительная структура: некоторые пары связаны «упругими связями», а некоторые тройки объединены в «рёбра жёсткости». Обозначим множество пар, связанных упругими связями, через E, а множество троек, составляющих рёбра жёсткости, через G. Например, в квадратной решётке ближайшие узлы (как по вертикали, так и погоризонтали) связываются упругими связями, а ребра жёсткости образуются вертикальными и горизонтальными тройками ближайших узлов. Энергия деформации карты состоит из двух слагаемых:

энергия растяжения U_{E}=\lambda \sum_{(W_i,W_j) \in E} \|W_i -W_j\|^2 ;
энергия изгиба U_{G}=\mu \sum_{(W_i,W_j,W_l) \in G} \|W_i -2W_j+W_l\|^2 ;

где λ,μ — соответствующие модули упругости.

Задача построения упругой карты состоит в минимизации функционала

U = D + UE + UG;

Если разбиение совокупности входных векторов S на классы Kj фиксировано, то минимизация U — линейная задача с разреженной матрицей коэффициентов. Поэтому, как и для сетей векторного квантования, применяется метод расщепления: фиксируем {Wj} — ищем {Kj} — для данных {Kj} ищем {Wj} — для данных {Wj} ищем {Kj} — … Алгоритм сходится к (локальному) минимуму U.

Метод упругих карт позволяет решать все задачи, которые решают самоорганизующиеся карты Кохонена, однако обладает большей регулярностью и предсказуемостью. При увеличении модуля изгиба μ упругие карты приближаются к линейным главным компонентам. При уменьшении обоих модулей упругости они превращаются в Кохоненовские сети векторного квантования. В настоящее время упругие карты интенсивно используются для анализа многомерных данных в биоинформатике.[10] Соответствующее программное обеспечение опубликовано и свободно доступно на сайте Института Кюри (Париж).[11][12]

На рисунке представлены результаты визуализации данных по раку молочной железы. Эти данные содержат 286 примеров с указанием уровня экспрессии 17816 генов[13]. Они доступны онлайн как ставший классическим тестовый пример для визуализации и картографии данных[14].

Сети векторного квантования, обучаемые с учителем

Пример возможного разделения классов, составленного с помощью разбиения Вороного-Дирихле.

Решается задача классификации. Число классов может быть любым. Изложим алгоритм для двух классов, {\bold A} и {\bold B}. Исходно для обучения системы поступают данные, класс которых известен. Задача: найти для класса {\bold A} некоторое количество k_{\bold A} кодовых векторов W_j^{\bold A}, а для класса {\bold B} некоторое (возможно другое) количество k_{\bold B} кодовых векторов W_l^{\bold B} таким образом, чтобы итоговая сеть Кохонена с k_{\bold A}+k_{\bold B} кодовыми векторами W_j^{\bold A}, W_l^{\bold B} (объединяем оба семейства) осуществляла классификацию по следующему решающему правилу:

если для вектора входных сигналов x ближайший кодовый вектор («победитель», который в слое Кохонена «забирает всё») принадлежит семейству \{W_j^{\bold A}\}, то x принадлежит классу {\bold A}; если же ближайший к x кодовый вектор принадлежит семейству \{W_l^{\bold B}\}, то x принадлежит классу {\bold B}.

С каждым кодовым вектором объединённого семейства \{W_j^{\bold A}\} \cup \{W_l^{\bold B}\} связан многогранник Вороного-Дирихле. Обозначим эти многогранники V_j^{\bold A}, V_l^{\bold B} соответственно. Класс {\bold A} в пространстве сигналов, согласно решающему правилу, соответствует объединению \cup_j V_j^{\bold A}, а класс {\bold B} соответствует объединению \cup_l V_l^{\bold B}. Геометрия таких объединений многогранников может быть весьма сложной (см. Рис с примером возможного разбиения на классы).

Правила обучения сети онлайн строится на основе базового правила обучения сети векторного квантования. Пусть на вход системы подаётся вектор сигналов x, класс которого известен. Если он классифицируется системой правильно, то соответствующий x кодовый вектор Wслегка сдвигается в сторону вектора сигнала («поощрение»)

Wnew = Wold(1 − θ) + xθ,

Если же x классифицируется неправильно, то соответствующий x кодовый вектор Wслегка сдвигается в противоположную сторону от сигнала («наказание»)

Wnew = Wold(1 + θ) − xθ,

где \theta \in (0,1) — шаг обучения. Для обеспечения стабильности используется онлайн метод с затухающей скоростью обучения. Возможно также использование разных шагов для «поощрения» правильного решения и для «наказания» неправильного

Это — простейшая (базовая) версия метода[15]. Существует множество других модификаций.

Другие сети Кохонена

Ссылки

  1. How many kinds of Kohonen networks exist? Internet FAQ Archives. Online Education
  2. Hecht-Nielsen, R. (1990), Neurocomputing, Reading, MA: Addison-Wesley, ISBN 0-201-09355-3.
  3. Kohonen, T. (1989/1997/2001), Self-Organizing Maps, Berlin — New York: Springer-Verlag. First edition 1989, second edition 1997, third extended edition 2001, ISBN 0-387-51387-6, ISBN 3-540-67921-9
  4. Kohonen, T. (1988), Learning Vector Quantization, Neural Networks, 1 (suppl 1), 303.
  5. Уоссермен, Ф. Нейрокомпьютерная техника: Теория и практика = Neural Computing. Theory and Practice. — М.: Мир, 1992. — 240 с. — ISBN 5-03-002115-9
  6. Real time interactive Voronoi and Delaunay diagrams with source code
  7. 1 2 3 Зиновьев А. Ю. Визуализация многомерных данных. — Красноярск: Изд. Красноярского государственного технического университета, 2000. — 180 с.
  8. С этой работы началось изучение главных многообразий. Диссертация T. Хасти: Hastie T., Principal Curves and Surfaces, Ph.D Dissertation, Stanford Linear Accelerator Center, Stanford University, Stanford, California, US, November 1984. А также на сайте PCA
  9. Yin H. Learning Nonlinear Principal Manifolds by Self-Organising Maps, In: Gorban A. N. et al (Eds.), LNCSE 58, Springer, 2007 ISBN 978-3-540-73749-0
  10. Gorban A. N., Kegl B., Wunsch D., Zinovyev A. Y. (Eds.), Principal Manifolds for Data Visualisation and Dimension Reduction, Series: Lecture Notes in Computational Science and Engineering 58, Springer, Berlin — Heidelberg — New York, 2007, XXIV, 340 p. 82 illus. ISBN 978-3-540-73749-0 (а также онлайн).
  11. VIMIDA: a Java-applet for VIsualization of MIcroarray DAta
  12. ViDaExpert: a software for multidimensional vectorial data visualization
  13. Wang Y., Klijn J.G., Zhang Y., Sieuwerts A.M., Look M.P., Yang F., Talantov D., Timmermans M., Meijer-van Gelder M.E., Yu J. et al. Gene-expression profiles to predict distant metastasis of lymph-node-negative primary breast cancer. Lancet 365 (2005), 671-679.
  14. Principal manifolds for data cartography and dimension reduction, Leicester, UK, August 2006. A web-page with test microarrays datasets provided for participants of the workshop.
  15. DLVQ Fundamentals

Wikimedia Foundation. 2010.

Смотреть что такое "Векторное квантование" в других словарях:

  • векторное квантование — Метод квантования, при котором многопараметрический сигнал квантуется по каждому из параметров, а затем хранится и обрабатывается как единый блок данных. Упорядоченная совокупность векторов образует кодовую книгу. В процессе вычислений… …   Справочник технического переводчика

  • иерархическое векторное квантование — алгоритм сжатия видеоданных при телеконференциях — [Л.Г.Суменко. Англо русский словарь по информационным технологиям. М.: ГП ЦНИИС, 2003.] Тематики информационные технологии в целом Синонимы алгоритм сжатия видеоданных при телеконференциях… …   Справочник технического переводчика

  • Квантование (обработка сигналов) — У этого термина существуют и другие значения, см. Квантование. Квантованный сигнал …   Википедия

  • Квантование сигнала — Квантованный сигнал Неквантованный сигнал с дискретным временем Цифровой сигнал В ин …   Википедия

  • Битность — Квантованный сигнал Неквантованный сигнал с дискретным временем Цифровой сигнал В ин …   Википедия

  • Уровень квантования — Квантованный сигнал Неквантованный сигнал с дискретным временем Цифровой сигнал В ин …   Википедия

  • Нейронная сеть Кохонена — Нейронные сети Кохонена  класс нейронных сетей, основным элементом которых является слой Кохонена. Слой Кохонена состоит из адаптивных линейных сумматоров («линейных формальных нейронов»). Как правило, выходные сигналы слоя Кохонена… …   Википедия

  • Карта данных — Нейронные сети Кохонена  класс нейронных сетей, основным элементом которых является слой Кохонена. Слой Кохонена состоит из адаптивных линейных сумматоров («линейных формальных нейронов»). Как правило, выходные сигналы слоя Кохонена… …   Википедия

  • Список алгоритмов — Эта страница информационный список. Основная статья: Алгоритм Ниже приводится список алгоритмов, группированный по категориям. Более детальные сведения приводятся в списке структур данных и …   Википедия

  • Стеганография — Не следует путать с стенографией. Запрос «Тайнопись» перенаправляется сюда; о тайнописи в Древней Руси см. Древнерусские тайнописи. Стеганография (от греч. στεγανός  скрытый + γράφω  пишу; буквально «тайнопись»)  это наука о… …   Википедия


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.