Информационный метод узкого места

Метод информационного узкого места - это метод теории информации, введенный Нафтали Тишби , Фернандо С. Перейрой и Уильямом Биалеком . ^[1] Он предназначен для поиска наилучшего компромисса между точностью и сложностью ( сжатием ) при суммировании (например, кластеризации ) случайной величины X , учитывая совместное распределение вероятностей p (X, Y) между X и наблюдаемой релевантной переменной Y - и описывается как предоставление«Удивительно богатый фреймворк для обсуждения множества проблем обработки сигналов и обучения» . ^[1]

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

Информация узкого место можно также рассматривать как искажение скорости проблемы, с функцией искажения , что меры , насколько хорошо Y предсказывается из сжатого представления Т по сравнению с его прямым предсказанием с X . Эта интерпретация обеспечивает общий итерационный алгоритм для решения компромисса между информационными узкими местами и вычисления информационной кривой на основе распределения p (X, Y) .

Пусть сжатое представление задано случайной величиной . Алгоритм минимизирует следующий функционал по условному распределению :${\ displaystyle T}$${\ Displaystyle р (т | х)}$

${\ Displaystyle \ мин _ {п (т | х)} \, \, I (X; T) - \ бета I (T; Y),}$

где и - взаимная информация и , и , соответственно, и - множитель Лагранжа .${\ Displaystyle I (X; T)}$${\ Displaystyle I (T; Y)}$${\ displaystyle X}$${\ displaystyle T}$${\ displaystyle T}$${\ displaystyle Y}$${\ displaystyle \ beta}$

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

Этот раздел пуст. Вы можете помочь, добавив к нему . ( Декабрь 2018 г. )

Самосогласованные уравнения [ править ]

Этот раздел пуст. Вы можете помочь, добавив к нему . ( Декабрь 2018 г. )

Теория обучения [ править ]

Этот раздел пуст. Вы можете помочь, добавив к нему . ( Декабрь 2018 г. )

Фазовые переходы [ править ]

Этот раздел пуст. Вы можете помочь, добавив к нему . ( Декабрь 2018 г. )

Информационная теория глубокого обучения [ править ]

Теория информационных узких мест в последнее время используется для изучения глубоких нейронных сетей (DNN). ^[2] Рассмотрим и соответственно как входной и выходной уровни DNN, и пусть будет любым скрытым уровнем сети. Шварц-Зив и Тишби предложили информационное узкое место, которое выражает компромисс между мерами взаимной информации и . В этом случае и, соответственно, количественно определите количество информации, которую скрытый слой содержит о входных и выходных данных. Они предположили, что процесс обучения DNN состоит из двух отдельных фаз; 1) начальная фаза подгонки, в которой увеличивается, и 2) последующая фаза сжатия, в которой уменьшается. Saxe et al. в ^[3]${\ displaystyle X}$${\ displaystyle Y}$${\ displaystyle T}$${\displaystyle I(X,T)}$${\displaystyle I(T,Y)}$${\displaystyle I(X,T)}$${\displaystyle I(T,Y)}$${\displaystyle I(T,Y)}$${\displaystyle I(X,T)}$противодействовал утверждению Шварц-Зива и Тишби ^[2], заявив, что это явление сжатия в DNN не является всеобъемлющим и зависит от конкретной функции активации. В частности, они утверждали, что сжатия не происходит с функциями активации ReLu. Шварц-Зив и Тишби оспорили эти утверждения, утверждая, что Сакс и др. Не наблюдали сжатия из-за слабой оценки взаимной информации. Недавно Noshad et al. использовали оптимальную по скорости оценку взаимной информации, чтобы исследовать это противоречие, заметив, что оптимальная оценка на основе хешей выявляет явление сжатия в более широком диапазоне сетей с активациями ReLu и maxpooling. ^[4]С другой стороны, недавно Goldfeld et al. утверждали, что наблюдаемое сжатие является результатом геометрических, а не теоретико-информационных явлений ^[5], точка зрения, которую разделяли также. ^[6]

Вариационное узкое место [ править ]

Узкое место по Гауссу [ править ]

Гауссово узкое место ^[7], а именно применение подхода информационного узкого места к гауссовским переменным, приводит к решениям, связанным с каноническим корреляционным анализом. Предположим, что это совместно многомерные векторы нормалей с нулевым средним и ковариациями, и это сжатая версия, которая должна поддерживать заданное значение взаимной информации с . Можно показать, что оптимум - это нормальный вектор, состоящий из линейных комбинаций элементов, где матрица имеет ортогональные строки. ${\displaystyle X,Y\,}$${\displaystyle \Sigma _{XX},\,\,\Sigma _{YY}}$${\displaystyle T\,}$${\displaystyle X\,}$${\displaystyle Y\,}$${\displaystyle T\,}$${\displaystyle X,\,\,T=AX\,}$${\displaystyle A\,}$

Матрица проекции на самом деле содержит строки, выбранные из взвешенных левых собственных векторов сингулярного разложения матрицы (обычно асимметричной)${\displaystyle A\,}$${\displaystyle M\,}$

${\displaystyle \Omega =\Sigma _{X|Y}\Sigma _{XX}^{-1}=I-\Sigma _{XY}\Sigma _{YY}^{-1}\Sigma _{XY}^{T}\Sigma _{XX}^{-1}.\,}$

Определите разложение по сингулярным числам

${\displaystyle \Omega =U\Lambda V^{T}{\text{ with }}\Lambda =\operatorname {Diag} {\big (}\lambda _{1}\leq \lambda _{2}\cdots \lambda _{N}{\big )}\,}$

и критические значения

${\displaystyle \beta _{i}^{C}{\underset {\lambda _{i}<1}{=}}(1-\lambda _{i})^{-1}.\,}$

тогда количество активных собственных векторов в проекции или порядок приближения определяется выражением${\displaystyle M\,}$

${\displaystyle \beta _{M-1}^{C}<\beta \leq \beta _{M}^{C}}$

И мы наконец получаем

${\displaystyle A=[w_{1}U_{1},\dots ,w_{M}U_{M}]^{T}}$

В котором веса даны как

${\displaystyle w_{i}={\sqrt {(\beta (1-\lambda _{i})/\lambda _{i}r_{i}}}}$

где ${\displaystyle r_{i}=U_{i}^{T}\Sigma _{XX}U_{i}.\,}$

Применение гауссовского информационного узкого места к временным рядам (процессам) дает решения, связанные с оптимальным прогнозирующим кодированием. Эта процедура формально эквивалентна линейному анализу медленных признаков. ^[8]

Оптимальные временные структуры в линейных динамических системах могут быть обнаружены в так называемом узком месте информации прошлого и будущего, применении метода узкого места к негауссовским выборочным данным. ^[9] Концепция, трактуемая Крейтцигом, Тишби и др., Не лишена сложности, поскольку в упражнении складываются две независимые фазы: во-первых, оценка неизвестных родительских плотностей вероятностей, из которых берутся образцы данных, и, во-вторых, использование эти плотности в рамках теоретической информации узкого места.

Оценка плотности [ править ]

Поскольку метод узких мест основан на вероятностных, а не статистических терминах, необходимо оценить основную плотность вероятности в точках выборки . Это хорошо известная проблема с множеством решений, описанных Сильверманом . ^[10] В настоящем методе вероятности совместной выборки находятся с использованием метода матрицы переходов Маркова, и это имеет некоторую математическую синергию с самим методом узких мест.${\displaystyle X={x_{i}}\,}$

Произвольно увеличивающаяся метрика расстояния между всеми парами отсчетов и матрицей расстояний равна . Затем необходимо вычислить вероятности перехода между парами выборок для некоторых . Рассматривая образцы как состояния и нормализованную версию как матрицу вероятностей перехода состояний Маркова, вектор вероятностей «состояний» после шагов, обусловленных начальным состоянием , равен . Вектор равновесной вероятности, заданный обычным способом доминантным собственным вектором матрицы, который не зависит от инициализирующего вектора${\displaystyle f\,}$${\displaystyle d_{i,j}=f{\Big (}{\Big |}x_{i}-x_{j}{\Big |}{\Big )}}$${\displaystyle P_{i,j}=\exp(-\lambda d_{i,j})\,}$${\displaystyle \lambda >0\,}$${\displaystyle P\,}$${\displaystyle t\,}$${\displaystyle p(0)\,}$${\displaystyle p(t)=P^{t}p(0)\,}$${\displaystyle p(\infty )\,}$${\displaystyle P\,}$${\displaystyle p(0)\,}$. Этот метод перехода Маркова устанавливает вероятность в точках выборки, которая, как утверждается, пропорциональна плотности вероятностей в них.

Другие интерпретации использования собственных значений матрицы расстояний обсуждаются в книге Сильвермана « Оценка плотности для статистики и анализа данных» . ^[10]${\displaystyle d\,}$

Кластеры [ править ]

В следующем примере мягкой кластеризации опорный вектор содержит категории выборки, и предполагается, что совместная вероятность известна. Мягкий кластер определяется его распределением вероятностей по выборкам данных . Тишби и др. представил ^[1] следующий итерационный набор уравнений для определения кластеров, которые в конечном итоге являются обобщением алгоритма Блахута-Аримото , разработанного в теории искажения скорости . Применение этого типа алгоритма в нейронных сетях, по-видимому, связано с энтропийными аргументами, возникающими при применении распределений Гиббса при детерминированном отжиге. ^{[11] [12]}${\displaystyle Y\,}$${\displaystyle p(X,Y)\,}$${\displaystyle c_{k}\,}$${\displaystyle x_{i}:\,\,\,p(c_{k}|x_{i})}$

${\displaystyle {\begin{cases}p(c|x)=Kp(c)\exp {\Big (}-\beta \,D^{KL}{\Big [}p(y|x)\,||\,p(y|c){\Big ]}{\Big )}\\p(y|c)=\textstyle \sum _{x}p(y|x)p(c|x)p(x){\big /}p(c)\\p(c)=\textstyle \sum _{x}p(c|x)p(x)\\\end{cases}}}$

Функция каждой строки итерации расширяется как

Строка 1: это матричный набор условных вероятностей.

${\displaystyle A_{i,j}=p(c_{i}|x_{j})=Kp(c_{i})\exp {\Big (}-\beta \,D^{KL}{\Big [}p(y|x_{j})\,||\,p(y|c_{i}){\Big ]}{\Big )}}$

Кульбак-Либлер расхождение между векторами генерируемых данными выборки и те , генерируемых его уменьшенной информацией прокси применяется для оценки верности сжатого вектора относительно контрольных данных (или категоричен) в соответствии с фундаментальным уравнением узкого места. - расхождение Кульбака – Лейблера между распределениями${\displaystyle D^{KL}\,}$${\displaystyle Y\,}$${\displaystyle x\,}$${\displaystyle c\,}$${\displaystyle Y\,}$${\displaystyle D^{KL}(a||b)\,}$${\displaystyle a,b\,}$

${\displaystyle D^{KL}(a||b)=\sum _{i}p(a_{i})\log {\Big (}{\frac {p(a_{i})}{p(b_{i})}}{\Big )}}$

и - скалярная нормализация. Взвешивание отрицательного показателя расстояния означает, что вероятности предшествующих кластеров уменьшаются в строке 1, когда расхождение Кульбака – Лейблера велико, таким образом, успешные кластеры увеличиваются в вероятности, а неудачные - распадаются.${\displaystyle K\,}$

Строка 2: Второй матричнозначный набор условных вероятностей. По определению

${\displaystyle {\begin{aligned}p(y_{i}|c_{k})&=\sum _{j}p(y_{i}|x_{j})p(x_{j}|c_{k})\\&=\sum _{j}p(y_{i}|x_{j})p(x_{j},c_{k}){\big /}p(c_{k})\\&=\sum _{j}p(y_{i}|x_{j})p(c_{k}|x_{j})p(x_{j}){\big /}p(c_{k})\\\end{aligned}}}$

где используются байесовские тождества .${\displaystyle p(a,b)=p(a|b)p(b)=p(b|a)p(a)\,}$

Строка 3: эта строка находит предельное распределение кластеров.${\displaystyle c\,}$

${\displaystyle {\begin{aligned}p(c_{i})&=\sum _{j}p(c_{i},x_{j})&=\sum _{j}p(c_{i}|x_{j})p(x_{j})\end{aligned}}}$

Это стандартный результат.

Дальнейшие входные данные для алгоритма - это предельное выборочное распределение, которое уже было определено доминирующим собственным вектором, и матричнозначная функция дивергенции Кульбака – Лейблера.${\displaystyle p(x)\,}$${\displaystyle P\,}$

${\displaystyle D_{i,j}^{KL}=D^{KL}{\Big [}p(y|x_{j})\,||\,p(y|c_{i}){\Big ]}{\Big )}}$

полученные из интервалов между образцами и вероятностей переходов.

Матрица может быть инициализирована случайным образом или с разумным предположением, в то время как матрица не требует предварительных значений. Хотя алгоритм сходится, может существовать несколько минимумов, которые необходимо разрешить. ^[13]${\displaystyle p(y_{i}|c_{j})\,}$${\displaystyle p(c_{i}|x_{j})\,}$

Определение контуров принятия решений [ править ]

Для того, чтобы классифицировать новый образец внешнего по отношению к обучающему набору , предыдущего расстояние метрических находки вероятность переходов между и все образцы в , с нормализацией. Во-вторых, примените последние две строки трехстрочного алгоритма, чтобы получить вероятности кластера и условной категории.${\displaystyle x'\,}$${\displaystyle X\,}$${\displaystyle x'\,}$${\displaystyle X:\,\,}$${\displaystyle {\tilde {p}}(x_{i})=p(x_{i}|x')=\mathrm {K} \exp {\Big (}-\lambda f{\big (}{\Big |}x_{i}-x'{\Big |}{\big )}{\Big )}}$${\displaystyle \mathrm {K} \,}$

${\displaystyle {\begin{aligned}&{\tilde {p}}(c_{i})=p(c_{i}|x')=\sum _{j}p(c_{i}|x_{j})p(x_{j}|x')=\sum _{j}p(c_{i}|x_{j}){\tilde {p}}(x_{j})\\&p(y_{i}|c_{j})=\sum _{k}p(y_{i}|x_{k})p(c_{j}|x_{k})p(x_{k}|x')/p(c_{j}|x')=\sum _{k}p(y_{i}|x_{k})p(c_{j}|x_{k}){\tilde {p}}(x_{k})/{\tilde {p}}(c_{j})\\\end{aligned}}}$

Ну наконец то

${\displaystyle p(y_{i}|x')=\sum _{j}p(y_{i}|c_{j})p(c_{j}|x'))=\sum _{j}p(y_{i}|c_{j}){\tilde {p}}(c_{j})\,}$

Параметр должен находиться под тщательным наблюдением, поскольку по мере его увеличения от нуля увеличивающееся количество функций в пространстве вероятностей категорий становится в фокусе при определенных критических порогах.${\displaystyle \beta \,}$

Пример [ править ]

В следующем примере рассматривается кластеризация в четырехквадрантном множителе со случайными входными данными и двумя категориями выходных данных , генерируемых . Эта функция имеет два пространственно разделенных кластера для каждой категории и, таким образом, демонстрирует, что метод может обрабатывать такие распределения.${\displaystyle u,v\,}$${\displaystyle \pm 1\,}$${\displaystyle y=\operatorname {sign} (uv)\,}$

Отбирают 20 проб, равномерно распределяемых по площади . Количество используемых кластеров превышает количество категорий, в данном случае два, мало влияет на производительность, и результаты показаны для двух кластеров с использованием параметров .${\displaystyle [-1,1]^{2}\,}$${\displaystyle \lambda =3,\,\beta =2.5}$

Функция расстояния - это где, в то время как условное распределение представляет собой матрицу 2 × 20${\displaystyle d_{i,j}={\Big |}x_{i}-x_{j}{\Big |}^{2}}$${\displaystyle x_{i}=(u_{i},v_{i})^{T}\,}$${\displaystyle p(y|x)\,}$

${\displaystyle {\begin{aligned}&Pr(y_{i}=1)=1{\text{ if }}\operatorname {sign} (u_{i}v_{i})=1\,\\&Pr(y_{i}=-1)=1{\text{ if }}\operatorname {sign} (u_{i}v_{i})=-1\,\end{aligned}}}$

и ноль в других местах.

Суммирование в строке 2 включает только два значения, представляющих обучающие значения +1 или -1, но, тем не менее, работает хорошо. На рисунке показано расположение двадцати выборок, где «0» представляет Y = 1, а «x» представляет Y = -1. Показан контур на уровне отношения правдоподобия,

${\displaystyle L={\frac {\Pr(1)}{\Pr(-1)}}=1}$

поскольку новый образец сканируется по квадрату. Теоретически контур следует привести в соответствие с и координатами , но для таких небольших количеств образца они вместо того, чтобы вслед за паразитные кластеризации точек выборки.${\displaystyle x'\,}$${\displaystyle u=0\,}$${\displaystyle v=0\,}$

Аналогии нейронной сети / нечеткой логики [ править ]

Этот алгоритм чем-то аналогичен нейронной сети с единственным скрытым слоем. Внутренние узлы представлены кластерами, а первый и второй уровни весов сети являются условными вероятностями и соответственно. Однако, в отличие от стандартной нейронной сети, алгоритм полностью полагается на вероятности в качестве входных данных, а не на сами значения выборки, в то время как внутренние и выходные значения представляют собой условные распределения плотности вероятности. Нелинейные функции инкапсулируются в метрику расстояния (или функции влияния / радиальные базисные функции ) и вероятности перехода вместо сигмоидальных функций.${\displaystyle c_{j}\,}$${\displaystyle p(c_{j}|x_{i})\,}$${\displaystyle p(y_{k}|c_{j})\,}$${\displaystyle f(.)\,}$

Алгоритм три строки Блейхута-Аримото быстро сходится, часто в десятки итераций, и варьирование , а и мощность кластеров, различные уровни внимания на особенности может быть достигнута.${\displaystyle \beta \,}$${\displaystyle \lambda \,}$${\displaystyle f\,}$

Определение статистической мягкой кластеризации частично совпадает с концепцией вербальной нечеткой принадлежности нечеткой логики .${\displaystyle p(c_{i}|x_{j})\,}$

Расширения [ править ]

Интересным расширением является случай информационного узкого места с дополнительной информацией. ^[14] Здесь информация максимизируется об одной целевой переменной и минимизируется о другой, изучая представление, которое является информативным о выбранных аспектах данных. Формально

${\displaystyle \min _{p(t|x)}\,\,I(X;T)-\beta ^{+}I(T;Y^{+})+\beta ^{-}I(T;Y^{-})}$

Библиография [ править ]

• Вайс, Ю. (1999), "Сегментация с использованием собственных векторов: объединяющая точка зрения", Труды Международной конференции IEEE по компьютерному зрению (PDF) , стр. 975–982
• П. Харремоес и Н. Тишби "Новый взгляд на узкое место в информации или как выбрать хорошую меру искажения". В трудах Международного симпозиума по теории информации (ISIT) 2007 г.

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