Нейронная сеть Кохонена

Материал из Википедии — свободной энциклопедии
(перенаправлено с «Векторное квантование»)
Перейти к: навигация, поиск

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

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

Слой Кохонена[править | править вики-текст]

Базовая версия[править | править вики-текст]

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

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

где w_{ji} — весовой коэффициент iго входа jго нейрона, w_{j0} — пороговый коэффициент.

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

Геометрическая интерпретация[править | править вики-текст]

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

Большое распространение получили слои Кохонена, построенные следующим образом: каждому (jму) нейрону сопоставляется точка W_j = (w_{j1},...w_{jm}) в m-мерном пространстве (пространстве сигналов). Для входного вектора x=(x_1,... x_m) вычисляются его евклидовы расстояния \rho_j(x) до точек W_j и «ближайший получает всё» — тот нейрон, для которого это расстояние минимально, выдаёт единицу, остальные — нули. Следует заметить, что для сравнения расстояний достаточно вычислять линейную функцию сигнала:

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

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

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

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

Если заданы точки W_j = (w_{j1},...w_{jm}), то m-мерное пространство разбивается на соответствующие многогранники Вороного-Дирихле V_j: многогранник V_j состоит из точек, которые ближе к W_j, чем к другим W_k (k \neq j).[6]

Сети векторного квантования[править | править вики-текст]

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

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

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

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

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

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

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

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

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

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

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

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

Самоорганизующиеся карты Кохонена[править | править вики-текст]

Идея и алгоритм обучения[править | править вики-текст]

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

Векторы входных сигналов x обрабатываются по одному, для каждого из них находится ближайший кодовый вектор («победитель», который «забирает всё») W_{j(x)}. После этого все кодовые векторы W_l, для которых \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 - статус эстроген-рецептора), формы (GROUP - риск развития метастаз) и цвета (TYPE - молекулярный тип опухоли). На панели (a) показана конфигурация узлов двумерной упругой карты в проекции на первые три главные компоненты. Сравнивая (b) и (c), можно заметить, что базальный тип опухоли как кластер лучше отделен на нелинейной проекции (b).

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

Пусть задана совокупность входных векторов S. Так же, как и сети векторного квантования и самоорганизующиеся карты, упругая карта представлена как совокупность кодовых векторов (узлов) W_j в пространстве сигналов. Множество данных S разделено на классы K_j, состоящие из тех точек x \in S, которые ближе к W_j, чем к другим W_l (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 ;

где \lambda, \mu  — соответствующие модули упругости.

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

U=D+U_{E}+U_{G};

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

Метод упругих карт позволяет решать все задачи, которые решают самоорганизующиеся карты Кохонена, однако обладает большей регулярностью и предсказуемостью. При увеличении модуля изгиба \mu упругие карты приближаются к линейным главным компонентам. При уменьшении обоих модулей упругости они превращаются в Кохоненовские сети векторного квантования. В настоящее время упругие карты интенсивно используются для анализа многомерных данных в биоинформатике.[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слегка сдвигается в сторону вектора сигнала («поощрение»)

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

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

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

где \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

См. также[править | править вики-текст]