Анализ независимых компонент

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску

Анализ независимых компонент (АНК, англ. Independent Component Analysis, ICA), называемый также Метод независимых компонент (МНК) — это вычислительный метод в обработке сигналов для разделения многомерного[en] сигнала на аддитивные подкомпоненты. Этот метод применяется при предположении, что подкомпоненты являются негауссовыми сигналами и что они статистически независимы друг от друга. АНК является специальным случаем слепого разделения сигнала. Типичным примером приложения является «Задача о шумной вечеринке»[en] — когда люди на шумной вечеринке выделяют голос собеседника, несмотря на громкую музыку и шум людей в помещении. Если мозг способен фильтровать звуки и сосредоточиться на одном звуке (голос визави), есть возможность применить этот метод в машинном обучении.

Введение[править | править код]

АНК на четырёх случайно смешанных видео[1]

Анализ независимых компонент пытается разложить множественный сигнал на независимые негауссовые сигналы. Например звук обычно является сигналом, который состоит из сложения в каждый момент одиночных t-сигналов, идущих из нескольких источников. Вопрос заключается в том, возможно ли разделить эти источники, выделяя их из общего сигнала. Если допущение статистической независимости верно, слепое разделение независимых компонент смешанного сигнала даст очень хорошие результаты. Метод также применяется для анализа сигналов, которые могут быть и не смешанными.

Простым приложением АНК является «задача о шумной вечеринке»[en], когда собеседники слышат друг друга, выделяя голос собеседника из общего сигнала, состоящего из шума одновременно говорящих людей в помещении и шумной улицы за окном. Обычно задача упрощается предположением, что задержка по времени или эхо отсутствуют. Заметим, что отфильтрованный и задержанный сигнал является копией зависимой компоненты, и тогда допущение статистической независимости не нарушено.

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

Метод АНК — разделение смешанных сигналов, базируется на двух допущениях и трёх эффектах источников смешанного сигнала, что даёт очень хорошие результаты. Двумя допущениями являются:

  1. Источники сигналов независимы друг от друга.
  2. Значения каждого источника сигнала имеют негауссово распределение.

Тремя эффектами источника смешанного сигнала являются:

  1. Независимость: как в и допущении 1, источники сигналов независимы, однако их смесь не является независимой от источников, потому что смесь сигналов имеет одни и те же источники.
  2. Нормальность: согласно центральной предельной теореме, распределение суммы независимых случайных переменных с конечной дисперсией стремится к гауссовому распределению. Попросту говоря, сумма двух независимых случайных переменных обычно имеет распределение более близкое к гауссовому, чем любое из двух исходных случайных переменных. Здесь мы рассматриваем каждый сигнал как случайную переменную.
  3. Сложность: временна́я сложность любой смеси сигналов больше, чем сложность одного сигнала, более простого по его составляющим.

Эти принципы составляют базовые основы АНК. Если сигналы, которые нам удалось извлечь из смеси, независимы, подобно исходным сигналам, и имеют негауссовые гистограммы или имеют малую сложность, подобную сигналу источников, они должны быть сигналами источников[2][3].

Определение независимости компонент[править | править код]

АНК находит независимые компоненты (которые называются факторами, скрытыми переменными или источниками) путём максимизации статистической независимости оцениваемых компонент. Можно выбрать один из многих путей для определения заменителя независимости, и этот выбор определит форму алгоритма АНК. Два наиболее широких определения независимости АНК:

  1. Минимизация взаимной информации
  2. Максимизация негауссовости

Семейство алгоритмов АНК с минимизацией взаимной информации (англ. Minimization-of-Mutual information, MMI) использует такие меры, как расхождение Кульбака — Лейблера и максимальная энтропия. Семейство алгоритмов АНК с максимизацией негауссовости использует коэффициент эксцесса и негэнтропию.

Типичным алгоритмам АНК свойственно использование следующих методов:

Декорреляция и снижение размерности могут быть получены методом главных компонент или сингулярным разложением. Декорреляция обеспечивает методу такие условия, когда все размерности трактуются одинаково и установлены априори до прогона алгоритма. Хорошо известные алгоритмы для АНК: infomax[en], FastICA[en], JADE[en], ядерный независимый компонентный анализ[en] и многие другие. В общем случае АНК не сможет определить действительное число источников сигналов, единственно правильный порядок или масштаб (включая знак) сигналов.

АНК важен для слепого разделения сигнала и имеет много практических приложений. Метод тесно связан с поиском (или даже является частным случаем поиска) факториального кодирования[en] данных, то есть нового векторного представления каждого вектора данных таким образом, чтобы он был однозначно закодирован результирующим кодовым вектором (кодирование без потерь), при этом компоненты кода статистически независимы.

Математическое определение[править | править код]

Линейный анализ независимых компонент может быть разделён на случай без шумов и случай с шумами, где АНК без шумов является частым случаем АНК с шумом. Нелинейный АНК следует считать отдельным случаем.

Общее определение[править | править код]

Данные представлены наблюдаемым случайным вектором , а скрытые компоненты случайным вектором . Задачей построения алгоритма является преобразование наблюдаемых данных с помощью статического преобразования в наблюдаемый вектор максимально независимых компонент , измеренных некоторой функцией независимости .

Генерирующая модель[править | править код]

Линейная АНК без шума[править | править код]

Компоненты наблюдаемого случайного вектора генерируются как сумма независимых компонент , :

взвешенных весами .

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

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

Исходные источники могут быть извлечены путём умножения наблюдаемых сигналов на обратную к матрице смешивания , которая известна также как не смешивающая матрица. Здесь предполагается, что матрица смешивания квадратная (). Если число базисных векторов больше размерности наблюдаемых векторов , задача является переопределённой, но остаётся разрешимой с помощью псевдообратной матрицы.

Линейный АНК с шумом[править | править код]

С добавочным предположением о нулевом среднем и не коррелирующим гауссовым шумом , модель АНК принимает форму .

Нелинейный АНК[править | править код]

Смесь источников не обязательно должна быть линейной. Используя нелинейную функцию смешивания с параметрами нелинейной моделью АНК будет .

Различимость[править | править код]

Независимые компоненты различимы с точностью до перестановки и масштабирования источников. Эта различимость требует, чтобы:

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

Бинарный анализ независимых компонент[править | править код]

Специальным вариантом АНК является Бинарный АНК, в котором как источники сигнала, так и мониторы имеют двоичную форму, а наблюдения от мониторов являются дизъюнктивной смесью бинарных независимых источников. Задача, как было показано, имеет приложения во многих областях, включая медицинскую диагностику, многокластерное назначение, сетевую томографию[en] и управление ресурсами интернета.

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

где является булевым И (англ. AND), а является булевым ИЛИ (англ. OR). Заметим, что шум не моделируется явно, а трактуется как независимые источники.

Описанная выше проблема может быть эвристически решена[4] (при предположении, что переменные непрерывны) путём применения метода FastICA[en] на бинарных наблюдаемых данных для получения смешанной матрицы (получены вещественные значения), затем применяем технику округления на для получения бинарных значений. Этот подход, как было показано, даёт крайне неточный результат.

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

Аппарат обобщённой бинарной АНК[6] вводит более широкое описание проблемы, которое не требует какого-либо знания о порождающей модели. Другими словами, этот метод пытается разложить источник на независимые компоненты (на столько, насколько возможно создать алгоритм без потери какой-либо информации) без предварительных допущений применения способа, при помощи которого он был получен. Хотя эта задача достаточно сложна, она может быть точно решена с помощью метода ветвей и границ или точно ограничена сверху умножением матрицы на вектор.

Методы слепого разделения сигнала[править | править код]

Поиск наилучшей проекции[править | править код]

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

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

Мы можем использовать коэффициент эксцесса для извлечения сигнала с несколькими источниками путём нахождения правильных векторов весов с использованием поиска наилучшей проекции.

Коэффициент эксцесса плотности вероятности сигнала, для конечной выборки вычисляется как

где является выборочным средним выделенных сигналов. Константа 3 обеспечивает, чтобы гауссовы сигналы имели нулевой коэффициент эксцесса, супергауссовы сигналы имели положительный коэффициент эксцесса, а субгауссовы сигналы имели отрицательный коэффициент эксцесса. Знаменатель равен дисперсии и он обеспечивает, чтобы измеренный коэффициент эксцесса получал дисперсию сигнала. Целью поиска наилучшей проекции является максимизация коэффициента эксцесса и сделать выделенный сигнал настолько ненормальным, насколько возможно.

Используя коэффициент эксцесса как меру ненормальности мы можем теперь проверить насколько коэффициент эксцесса сигнала , извлечённого из набора M смесей , изменяется по мере того, как вектор весов вращается вокруг начала координат. Если задано, что каждый источник сигнала является супергауссовым, мы можем ожидать

  1. коэффициент эксцесса извлечённого сигнала максимален в точности тогда, когда .
  2. коэффициент эксцесса извлечённого сигнала максимален, когда ортогонален проекциям осей или , поскольку мы знаем, что вектор оптимального веса должен быть ортогонален преобразованным осям и .

Для смеси сигналов от разных источников мы можем использовать коэффициент эксцесса ортогонализации Грама ― Шмидта (ОГШ) для извлечения сигналов. Если дана смесь M сигналов в M-мерном пространстве, ОГШ проектирует эти точки данных в (M-1)-мерное пространство с помощью вектора весов. Мы можем гарантировать независимость выделенных сигналов с помощью ОГШ.

С целью поиска правильного значения мы можем использовать метод градиентного спуска. Прежде всего, мы избавляемся от корреляции и преобразуем в новую смесь , которая имеет единичную дисперсию и . Этот процесс может быть выполнен путём применения сингулярного разложения к ,

Масштабируем каждый вектор и положим . Сигнал, выделенный взвешенным вектором , равен . Если вектор весов w имеет единичную длину, то есть , тогда коэффициент эксцесса можно переписать как:

Процесс обновления для :

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

Другим подходом является использование негэнтропии[8] вместо коэффициента эксцесса. Негэнтропия является устойчивым методом по отношению коэффициента эксцесса, поскольку коэффициент эксцесса очень чувствителен к выбросам. Метод негэнтропии основывается на важном свойстве распределения Гаусса — нормальная случайная величина имеет наибольшую энтропию среди всех непрерывных случайных переменных с одинаковой дисперсией. Это также является причиной, почему мы хотим найти наиболее негауссовые переменные. Простое доказательство можно найти в статье дифференциальной энтропии.

y являются гауссовой случайной переменной некоторой ковариантной матрицы,

Аппроксимация для негэнтропии равна

Доказательство можно найти на странице 131 книги «Анализ независимых компонент», которую написали Аапо Хювяринен, Юха Кархунен и Эркки Ойя[3]. Эта аппроксимация также страдает теми же проблемами, что и коэффициент эксцесса (чувствительность к выбросам). Разрабатывались и другие подходы[9]

Выбор и

и

Основанный на infomax[править | править код]

АНК, по существу, является многомерной параллельной версией поиска наилучшей проекции. В то время как поиск наилучшей проекции выделяет серию сигналов по одному из смеси M сигналов, АНК выделяет M сигналов параллельно. Это приводит к большей устойчивости АНК по сравнению с поиском наилучшей проекции[2].

Метод поиска наилучшей проекции, чтобы обеспечить независимость выделяемых сигналов, использует ортогонализацию Грама ― Шмидта, в то время как АНК использует метод infomax[en] и оценку максимального правдоподобия для обеспечения независимости выделяемого сигнала. Ненормальность выделяемого сигнала достигается с помощью соответствующей модели.

Процесс АНК, основанный на infomax[en], коротко: если дана смесь сигналов и набор одинаковых независимых функций распределения , мы ищем несмешивающую матрицу , которая максимизирует совместную энтропию сигналов , где являются сигналами, отобранными по . Если дана оптимальная , сигналы имеют максимальную энтропию и, потому, независимы, что гарантирует, что выделенные сигналы также независимы. Функция обратима и является моделью сигнала. Заметим, что если плотность вероятности модели источника сигнала соответствует плотности вероятности выделенного сигнала , то максимизация совместной энтропии также максимизирует количество взаимной информации между и . По этой причине, использование энтропии для выделения независимых сигналов известно как infomax[en].

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

Совместная плотность вероятности , как можно показать, связана с совместной плотностью вероятности извлечённых сигналов с помощью многомерной формы:

где является матрицей Якоби. Мы имеем , и является плотностью вероятности, принятых для источников сигналов , поэтому,

поэтому,

Мы знаем, что когда , является однородным распределением, а максимизирована. Поскольку

где является абсолютным значением определителя несмешивающей матрицы . Поэтому,

так что,

поскольку , и максимизация не влияет на , мы можем максимизировать функцию

чтобы получить независимость извлечённого сигнала.

Если имеется M маргинальных плотностей вероятности модели, совместные плотности вероятности независимы и используют супергауссову модель плотности вероятности для источников сигналов , то мы получаем

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

На основе оценки максимального правдоподобия[править | править код]

Оценка максимального правдоподобия (англ. Maximum likelihood estimation, MLE) является стандартным статистическим средством для нахождения значений параметров (например, несмешивающей матрицы ), которые обеспечивают лучшее соответствие некоторых данных (например, извлечённых сигналов ) для данной модели (например, совместной плотности вероятности (ПВ) источников сигналов)[2].

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

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

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

Мы определяем функцию правдоподобия матрицы :

Это равно плотности вероятности в , поскольку .

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

Распространённой практикой является использование логарифма правдоподобия, поскольку его проще всего вычислить. Так как логарифм является монотонной функцией, матрица , которая максимизирует функция , также максимизирует его логарифм . Это позволяет взять логарифм в равенстве выше, что даёт логарифм функции правдоподобия

Если мы подставим широко используемую модель плотности вероятности с высоким коэффициентом эксцесса для источников сигналов , мы получим

Матрица , максимизирующая эту функцию, является оценкой максимального правдоподобия.

История и предпосылки[править | править код]

Раннюю общую основу для анализа независимых компонент предложили Дженни Эро и Бернард Анс в 1984 году[10], затем к ним присоединился Христиан Джуттен с 1985 года[11][12][13]. Наиболее ясно этот метод изложил Пьер Комон в 1994 году[14]. В 1995 году Тони Белл и Терри Седжновски предложили быстрый и эффективный алгоритм АНК, основанный на принципе infomax[en], который ввёл Ральф Линскер в 1987 г.

Многие алгоритмы, реализующие АНК, доступны и описаны в литературе, относящейся к данной области. Алгоритм FastICA, который разработали Аапо Хювяринен и Эркки Ойя, широко используется, включая производственные приложения. В нём применен коэффициент эксцесса в качестве функции цены. Другие примеры скорее связаны со слепым разделением сигнала, в основе которого лежит более общий подход. Например, можно опустить допущение независимости и разделить попарно коррелирующие сигналы, а следовательно, избежать статистически «зависимых» сигналов. Сепп Хохрайтер и Юрген Шмидхубер показали, как получить нелинейный АНК или осуществить разделение источников, если они являются побочным продуктом регуляризации (1999)[15]. Их метод не требует бесспорного и строгого знания о числе независимых источников.

Приложения[править | править код]

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

Некоторые из приложений АНК перечислены ниже[2]:

Анализ независимых компонент в EEGLAB[en]

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

Примечания[править | править код]

Литература[править | править код]

  • Kruskal J. B. Toward a practical method which helps uncover the structure of a set of observations by finding the line transformation which optimizes a new "index of condensation" // Statistical computation / Milton R. C., Nelder J. A.. — New York: Academic Press, 1969.
  • Pierre Comon. Independent Component Analysis: a new concept? // Signal Processing. — 1994. — Т. 36, вып. 3. — С. 287–314. (Оригинальная статья, описывающая концепцию ICA)
  • Comon P., Jutten C. Handbook of Blind Source Separation, Independent Component Analysis and Applications. — Oxford UK: Academic Press, 2010. — ISBN 978-0-12-374726-6.
  • Lee T.-W. Independent component analysis: Theory and applications. — Boston, Mass: Kluwer Academic Publishers, 1998. — ISBN 0-7923-8261-7.
  • Ranjan Acharyya. A New Approach for Blind Source Separation of Convolutive Sources - Wavelet Based Separation Using Shrinkage Function. — 2008. — ISBN 3-639-07797-0. (книга фокусируется на обучении без учителя с помощью слепого выделения источника)
  • Hérault J., Ans B. Réseau de neurones à synapses modifiables : Décodage de messages sensoriels composites par apprentissage non supervisé et permanent // Comptes Rendus de l'Académie des Sciences, Série III. — 1984. — Т. 299. — С. 525–528.
  • Ans B., Hérault J., Jutten C. Architectures neuromimétiques adaptatives: Détection de primitives. // Cognitiva 85, Paris 4-7 Juin 1985. — Paris, 1985. — Т. 2.
  • Hérault J., Jutten C., Ans B. Détection de grandeurs primitives dans un message composite par une architecture de calcul neuromimétique en apprentissage non supervise // Proceedings of the 10th Workshop Traitement du signal et ses applications. — Nice (France): GRETSI, 1985. — Т. 2.
  • Hérault J., Jutten C. Space or time adaptive signal processing by neural networks models // Intern. Conf. on Neural Networks for Computing. — Utah, USA: Snowbird, 1986.
  • Sepp Hochreiter, Jürgen Schmidhuber. Feature Extraction Through LOCOCODE // Neural Computation. — 1999. — Т. 11, вып. 3. — ISSN 0899-7667. — DOI:10.1162/089976699300016629.
  • Brown G. D., Yamada S., Sejnowski T. J. Independent components analysis at the neural cocktail party // Trends in Neurosciences. — 2001. — Т. 24, вып. 1. — DOI:10.1016/s0166-2236(00)01683-0.
  • Lewicki M. S. Areview of methods for spike sorting: detection and classification of neural action potentials // Network: Computation in Neural Systems. — 1998. — Т. 9.
  • Barlett M. S. Face image analysis by unsupervised learning. — Boston: Kluwer International Series on Engineering and Computer Science, 2001. — Т. 612. — (SECS). — ISBN 978-1-4613-5653-0.
  • Bell A. J., Sejnowski T. J. The independent components of natural scenes are edge filters // Vision Research. — 1997. — Т. 37, вып. 23. — DOI:10.1016/s0042-6989(97)00121-1. — PMID 9425547.
  • Back A. D., Weigend A. S. A first application of independent component analysis to extracting structure from stock returns // International Journal of Neural Systems. — 1997. — Т. 8, вып. 4. — DOI:10.1142/s0129065797000458. — PMID 9730022.
  • Hyvarinen A., Karhunen J., Oja E. Independent component analysis / Symon Haykin. — New York: John Wiley and Sons, 2001. — (Adaptive and Learning System for Signal Processing, Communications, and Control). — ISBN 0-471-40540-X.
  • Polder G., van der Heijen F.W.A.M. Estimation of compound distribution in spectral images of tomatoes using independent component analysis // Austrian Computer Society. — 2003.
  • Delorme A., Sejnowski T., Makeig S. Enhanced detection of artifacts in EEG data using higher-order statistics and independent component analysis // NeuroImage. — 2007. — Т. 34, вып. 4. — DOI:10.1016/j.neuroimage.2006.11.004. — PMID 17188898.
  • Trapnell C., Cacchiarelli D., Grimsby J. The dynamics and regulators of cell fate decisions are revealed by pseudotemporal ordering of single cells // Nature Biotechnology. — 2014. — Т. 32, вып. 4. — DOI:10.1038/nbt.2859. — PMID 24658644.
  • Vesa J. Kiviniemi, Juha-Heikki Kantola, Jukka Jauhiainen, Aapo Hyvärinen, Osmo Tervonen. Independent component analysis of nondeterministic fMRI signal sources // NeuroImage. — 2003. — Т. 19. — DOI:10.1016/S1053-8119(03)00097-1. — PMID 12814576.

Ссылки[править | править код]