Алфавит — произвольное конечное множество $X$.
Длина алфавита — мощность множества $X$ (обозначение:
$l(X)$).
Определение: алфавит
Определение: энтропия (Хартли)
Рассмотрим алфавит $X$ длины $n$. Величина
\[
H(n) = K \log_2 n
\]
называется энтропией по Хартли.
Константа $K$ отвечает за размерность.
Нетрудно видеть, что функция $H(n)$ обладает следующими свойствами:
- $H(1) = 0$, т.е. алфавитом из одного символа нельзя передавать информацию.
- $H(mn) = H(m) + H(n)$.
Определение: энтропия (Шеннон)
Рассмотрим алфавит $X$ длины $N$. Пусть $x$ — случайная
величина, принимающая $N$ независимых случайных значений $x_i$ с
вероятностями $p_i$. Тогда величина
\[
H(x) = - K \sum_{i=1}^n p_i \log_2 p_i
\]
называется энтропией по Шеннону.
Свойства энтропии
Рассмотрим энтропию
\[
H(x) = - \sum_{i=1}^n p_i \log p_i.
\]
Она удовлетворяет следующим свойствам:
-
$H(x) \leqslant \log n$, где $n$ — длина алфавита.
Рассмотрим разницу: \[ \begin{aligned} H(x) - \log n &= - \sum_{i=1}^n p_i \log p_i - \sum_{i=1}^n p_i \log n = \\ &= - \sum_{i=1}^n p_i \left[ \log p_i + \log n \right] = \\ &= \phantom{-} \sum_{i=1}^n p_i \log \frac{1}{p_i n}. \end{aligned} \] Пользуясь свойством логарифма \[ \log_a b = \frac{\log_c b}{\log_c a} \implies \log_c b = \log_c a \cdot \log_a b, \] получаем \[ \sum_{i=1}^n p_i \log \frac{1}{p_i n} = \log e \cdot \sum_{i=1}^n p_i \ln \frac{1}{p_i n}. \] Известно, что \[ \ln x \leqslant x - 1, \] поэтому \[ \log e \cdot \sum_{i=1}^n p_i \ln \frac{1}{p_i n} \leqslant \log e \cdot \sum_{i=1}^n p_i \left[ \frac{1}{p_i n} - 1 \right] = \log e \cdot \sum_{i=1}^n \left[ \frac{1}{n} - p_i \right]. \] Окончательно, учитывая, что \[ \sum_{i=1}^n \frac{1}{n} = 1, \qquad \sum_{i=1}^n p_i = 1, \] имеем \[ \log e \cdot \sum_{i=1}^n \left[ \frac{1}{n} - p_i \right] = 0, \] то есть \[ H(x) - \log n \leqslant 0, \implies H(x) \leqslant \log n, \] причём равенство выполняется, если \[ \frac{1}{p_i n} = 1, \implies p_i = \frac{1}{n}. \]
- $H(x) \geqslant 0$, причём равенство достигается, если \[ \exists i \in \overline{1,n}: \quad p_i = 1. \]
Единственность определения функции энтропии
Требования к функции энтропии:
- $H(p_1, \dots, p_n)$ определена и непрерывна для всех $p_1, \dots, p_n$, причём \[ \sum_{i=1}^n p_i = 1. \]
- В случае, когда все буквы равновероятны, увеличение количества букв должно всегда увеличивать значение функции, то есть \[ H \underbrace{ \paren{ \frac{1}{n}, \dots, \frac{1}{n} } }_{n} \lt H \underbrace{ \paren{ \frac{1}{n+1}, \dots, \frac{1}{n+1} } }_{n+1}. \]
-
Должно быть выполнено соотношение
\[
H(p_1 q_1, \dots, p_1 q_m,
\dots,
p_n r_1, \dots, p_n r_s)
=
H(p_1, \dots, p_n) + p_1 H(q_1, \dots, q_m) +
\cdots
+ p_n H(r_1, \dots, r_s).
\]
В этом случае \[ H\paren{ \frac{1}{2}, \frac{1}{3}, \frac{1}{6} } = H\paren{ \frac{1}{2}, \frac{1}{2} } + \frac{1}{2} H\paren{ \frac{2}{3}, \frac{1}{3} }. \]
Свойствам 1-3 удовлетворяет только функция
\[
H = -K \sum_{i=1}^n p_i \log p_i, \qquad K \gt 0.
\]
Пусть \[ A(n) := H\paren{ \frac{1}{n}, \dots, \frac{1}{n} }. \] Рассмотрим некоторые $s \gt 1, m \in \mathbb{N}$. Из свойства 3 следует, что \[ A(s^m) = m A(s). \] Аналогично, для некоторых $t \gt 1, n \in \mathbb{N}$ \[ A(t^n) = n A(t). \]
Для любого $n \in \mathbb{N}$ всегда найдётся $m \in \mathbb{N}$ такой, что \[ s^m \leqslant t^n \lt s^{m+1}. \] Преобразуем эти неравенства: возьмём логарифм \[ m \log s \leqslant n \log t \lt (m+1) \log s \] и поделим на $n \log s$: \[ \frac{m}{n} \leqslant \frac{\log t}{\log s} \lt \frac{m}{n} + \frac{1}{n}. \] Очевидно, что \[ \frac{m}{n} - \frac{1}{n} \lt \frac{\log t}{\log s} \lt \frac{m}{n} + \frac{1}{n}, \] откуда следует, что \[ \abs{ \frac{\log t}{\log s} - \frac{m}{n} } \lt \varepsilon \] для любого $\varepsilon \gt 0$.
Из монотонности $A(n)$ следует, что \[ \begin{gathered} A(s^m) \leqslant A(t^n) \lt A(s^{m+1}), \\ m A(s) \leqslant n A(t) \lt (m+1) A(s). \end{gathered} \] Поделим на $n A(s)$: \[ \frac{m}{n} \leqslant \frac{A(t)}{A(s)} \lt \frac{m}{n} + \frac{1}{n}, \] или \[ \abs{ \frac{m}{n} - \frac{A(t)}{A(s)} } \lt \varepsilon, \] откуда окончательно получаем, что \[ \abs{ \frac{A(t)}{A(s)} - \frac{\log t}{\log s} } \lt 2 \varepsilon, \] то есть \[ A(t) = K \log t, \] причём $K \gt 0$ для выполнения условия 2.
Предположим теперь, что вероятность появления $i$-ой буквы равна \[ p_i = \frac{n_i}{\sum_{j=1}^n n_j}, \qquad n_i \in \mathbb{Z}. \] Разобьём выбор из $\sum n_j$ букв на два этапа:
- выбор из $n$ вариантов с вероятностями $p_1, \dots, p_n$;
- пусть выбрали $p_i$, тогда выбираем из $n_i$ равновероятных вариантов.
Математически это можно записать в виде \[ K \log \sum_{j=1}^n n_j = H(p_1, \dots, p_n) + \sum_{j=1}^{n} p_j \cdot K \log n_j. \] Выразим из этого равенства функцию $H$: \[ \begin{aligned} H(p_1, \dots, p_n) &= K \left[ \sum_{j=1}^n p_j \log \sum_{k=1}^n n_k - \sum_{j=1}^n p_j \log n_j \right] = \\ &= -K \sum_{j=1}^n p_j \log \frac{n_j}{\sum_{k=1}^n n_k} = \\ &= -K \sum_{j=1}^n p_j \log p_j, & p_j \in \mathbb{Q}. \end{aligned} \]
Если же $p_j \in \mathbb{R}$, то их можно сколь угодно хорошо приблизить рациональными числами, и в силу непрерывности функции $H(p_1, \dots, p_n)$ выполняется то же равенство \[ H(p_1, \dots, p_n) = -K \sum_{j=1}^n p_j \log p_j. \]
Определение: совместная энтропия
Рассмотрим два источника сигнала: $X$ и $Y$. Обозначим за
\[
p(x,y) = p(x | y) p(y)
\]
вероятность появления пары $(x,y)$.
Величина
\[
H(X, Y) = - \sum_{x \in X} \sum_{y \in Y} p(x,y) \log p(x,y)
\]
называется совместной энтропией.
Определение: условная энтропия
Величину
\[
H(X|Y) = -\sum_{x \in X} \sum_{y \in Y} p(x,y) \log p(x|y)
\]
называют условной энтропией.
Свойство условной энтропии
\[
H(X|Y) \leqslant H(X),
\]
причём равенство достигается только тогда, когда $X,Y$ —
независимые сигналы.
Рассмотрим разницу
\[
H(X|Y) - H(X) = - \sum_{x \in X} \sum_{y \in Y} p(x,y) \log p(x|y)
+ \sum_{x \in X} p(x) \log p(x).
\]
Так как
\[
p(x) = \sum_{y \in Y} p(x|y) p(y) = \sum_{y \in Y} p(x,y),
\]
то
\[
\begin{aligned}
H(X|Y) - H(X)
&= - \sum_{x \in X} \sum_{y \in Y} p(x,y) \log p(x|y)
+ \sum_{x \in X} p(x) \log p(x) = \\
&= - \sum_{x \in X} \sum_{y \in Y} p(x,y) \log p(x|y)
+ \sum_{x \in X} \sum_{y \in Y} p(x,y) \log p(x) = \\
&= \sum_{x \in X} \sum_{y \in Y} p(x,y)
\left[
\log p(x) - \log p(x|y)
\right] = \\
&= \sum_{x \in X} \sum_{y \in Y} p(x,y) \log \frac{p(x)}{p(x|y)}.
\end{aligned}
\]
Заметим, что если $X, Y$ — независимые величины, то
$p(x|y) = p(x)$ и
\[
H(X|Y) - H(X) = 0, \implies H(X|Y) = H(X).
\]
Пусть $X,Y$ — зависимые величины. Воспользуемся свойствами
\[
\log_a b = \log_a c \cdot \log_c b
\quad \mbox{ и } \quad
\ln x \leqslant x - 1;
\]
имеем
\[
\begin{aligned}
H(X|Y) - H(X)
&= \sum_{x \in X} \sum_{y \in Y} p(x,y) \log \frac{p(x)}{p(x|y)}
= \\
&= \log e \sum_{x \in X} \sum_{y \in Y} p(x,y)
\ln \frac{p(x)}{p(x|y)} \leqslant \\
&\leqslant \log e \sum_{x \in X} \sum_{y \in Y} p(x,y) \paren{
\frac{p(x)}{p(x|y)} - 1
} = \\
&= \log e \sum_{x \in X} \sum_{y \in Y} \paren{
p(y) p(x) - p(x,y)
} = \\
&= \log e \cdot (1 - 1) = 0,
\end{aligned}
\]
откуда и следует, что
\[
H(X|Y) \leqslant H(X).
\]
Задача: выразить совместную энтропию через условную
Справедливо равенство
\[
H(X,Y) = H(X) + H(Y|X).
\]
По определению совместной энтропии
\[
H(X, Y) = - \sum_{x \in X} \sum_{y \in Y} p(x,y) \log p(x,y).
\]
Так как
\[
p(x,y) = p(x) p(y|x),
\]
то
\[
\begin{aligned}
H(X, Y)
&= - \sum_{x \in X} \sum_{y \in Y} p(x,y) \log p(x,y) = \\
&= - \sum_{x \in X} \sum_{y \in Y} p(x,y) \left[
\log p(x) + \log p(y|x)
\right] = \\
&= - \sum_{x \in X} \sum_{y \in Y} p(x,y) \log p(x)
- \sum_{x \in X} \sum_{y \in Y} p(x,y) \log p(y|x).
\end{aligned}
\]
Используя равенство
\[
\begin{gathered}
\sum_{y \in Y} p(x,y) = p(x), \\
\implies
H(X) = - \sum_{x \in X} p(x) \log p(x)
= - \sum_{x \in X} \sum_{y \in Y} p(x,y) \log p(x),
\end{gathered}
\]
а также определение условной энтропии
\[
H(Y|X) \bydef= - \sum_{x \in X} \sum_{y \in Y} p(x,y) \log p(y|x),
\]
окончательно получаем, что
\[
H(X,Y) = H(X) + H(Y|X).
\]
\[
H(X,Y) \leqslant H(X) + H(Y),
\]
причём равенство достигается только тогда, когда $X,Y$ —
независимые величины.
Действительно, известно свойство условной энтропии:
\[
H(Y|X) \leqslant H(Y),
\]
причём равенство достигается только тогда, когда $X,Y$ —
независимые величины.
Определение: взаимная информация
Величину
\[
I(X,Y) = \sum_{x \in X} \sum_{y \in Y} p(x,y)
\log \frac{p(x,y)}{p(x) p(y)}
\]
называют взаимной информацией.
Чему равна взаимная информация двух независимых величин $X$ и $Y$?
Взаимная информация двух независимых величин равна нулю.
По определению взаимной информации
\[
\begin{aligned}
I(X,Y) &= \sum_{x \in X} \sum_{y \in Y} p(x,y)
\log \frac{p(x,y)}{p(x) p(y)} = \\
&= \sum_{x \in X} \sum_{y \in Y} p(x,y) \log \frac{p(y|x)}{p(y)},
\end{aligned}
\]
но для независимых случайных величин $p(y|x) = p(y)$, поэтому
\[
\begin{aligned}
I(X,Y)
&= \sum_{x \in X} \sum_{y \in Y}
p(x,y) \log \frac{p(y|x)}{p(y)} = \\
&= \sum_{x \in X} \sum_{y \in Y}
p(x,y) \log \frac{p(y)}{p(y)} = \\
&= 0.
\end{aligned}
\]
Задача: выразить совместную энтропию через взаимную информацию
Справедливо равенство
\[
H(X,Y) = H(X) + H(Y) - I(X,Y).
\]
По определению взаимной информации
\[
I(X,Y) = \sum_{x \in X} \sum_{y \in Y} p(x,y)
\log \frac{p(x,y)}{p(x) p(y)}.
\]
Пользуясь равенством
\[
p(x,y) = p(y|x) p(x),
\]
запишем
\[
\begin{aligned}
I(X,Y)
&= \sum_{x \in X} \sum_{y \in Y} p(x,y)
\log \frac{p(x,y)}{p(x) p(y)} = \\
&= \sum_{x \in X} \sum_{y \in Y} p(x,y)
\log \frac{p(y|x)}{p(y)} = \\
&= \sum_{x \in X} \sum_{y \in Y} p(x,y) \log p(y|x)
- \sum_{x \in X} \sum_{y \in Y} p(x,y) \log p(y).
\end{aligned}
\]
Из равенства
\[
\begin{gathered}
\sum_{x \in X} p(x,y) = p(y), \\
\implies
H(Y)
= - \sum_{y \in Y} p(y) \log p(y)
= - \sum_{x \in X} \sum_{y \in Y} p(x,y) \log p(y),
\end{gathered}
\]
а также из определения условной энтропии
\[
H(Y|X) \bydef
= - \sum_{x \in X} \sum_{y \in Y} p(x,y) \log p(y|x)
\]
следует, что
\[
I(X,Y) = H(Y) - H(Y|X).
\]
Аналогичные рассуждения можно провести, заметив, что
\[
p(x,y) = p(x|y) p(y);
\]
тогда получим, что
\[
I(X,Y) = H(X) - H(X|Y).
\]
Заметим, что из свойства условной энтропии
\[
H(X|Y) \leqslant H(X)
\]
следует, что $I(X,Y) \geqslant 0$, причём равенство достигается,
когда $X,Y$ — независимые величины.
Используя равенства
\[
H(X,Y) = H(X) + H(Y|X), \qquad
H(X,Y) = H(Y) + H(X|Y),
\]
получаем, что
\[
I(X,Y) = H(X) + H(Y) - H(X,Y).
\]
Определение: код
Рассмотрим два алфавита: исходный $X$ и для кодирования $D$. Обозначим
множество всех слов алфавита $D$ как
\[
D^* := \bigcup_{k=1}^\infty D^k,
\]
где $D^k$ — все слова длины $k$.
Отображение
\[
C: X \to D^*
\]
называют кодом.
Определение: сингулярный (вырожденный) код
Код
\[
C: X \to D^*
\]
называют сингулярным (вырожденным), если
\[
\exists x_1, x_2 \in X: \qquad C(x_1) = C(x_2).
\]
Определение: невырожденный код
Код
\[
C: X \to D^*
\]
называют невырожденным, если
\[
\forall x_1, x_2 \in X:
\qquad x_1 \neq x_2 \implies C(x_1) \neq C(x_2).
\]
Определение: расширение кода
Код
\[
C^*: X^* \to D^*
\]
называют расширением кода
\[
C: X \to D^*,
\]
если
\[
C^*(x_1, \dots, x_n) = C(x_1) \cdots C(x_2),
\]
где справа стоит конкатенация.
Когда говорят, что код допускает однозначное декодирование?
Говорят, что код
\[
C: X \to D^*
\]
допускает однозначное декодирование, если его расширение
$C^*$ невырождено.
Определение: префиксный код
Код
\[
C: X \to D^*
\]
называют префиксным, если для любого символа $x \in X$ его
кодовое слово не является началом другого кодового слова.
Определение: оптимальный код
Рассмотрим код
\[
C: X \to D^*.
\]
Введём обозначение: $l(x)$ — длина кодового слова для символа
$x \in X$.
Обозначим вероятность появления символа $x$ за $p(x)$. Тогда
величину
\[
L(C) = \sum_{x \in X} p(x) l(x)
\]
называют средней длиной.
Код $\overline{C}$ (префиксный или однозначно декодируемый)
называют оптимальным, если для любого другого кода $C$
(префиксного или однозначно декодируемого) выполняется неравенство
\[
L(\overline{C}) \leqslant L(C).
\]
Неравенство Крафта для префиксных кодов
(неравенство Крафта).
Рассмотрим алфавиты $X$ и $D$ длин $l(X) = n$ и $l(D) = d$ соответственно. Пусть $C: X \to D^*$ — префиксный код, причём $l_1, \dots, l_n$ — длины кодовых слов для символов $x_1, \dots, x_n$. Тогда \[ \sum_{k=1}^n d^{-l_k} \leqslant 1. \] Более того, если найдутся $l_1, \dots, l_n \in \mathbb{N}$, удовлетворяющие этому неравенству, то существует префиксный код $C$ такой, что длины кодовых слов — $l_1, \dots, l_n$.
Рассмотрим алфавиты $X$ и $D$ длин $l(X) = n$ и $l(D) = d$ соответственно. Пусть $C: X \to D^*$ — префиксный код, причём $l_1, \dots, l_n$ — длины кодовых слов для символов $x_1, \dots, x_n$. Тогда \[ \sum_{k=1}^n d^{-l_k} \leqslant 1. \] Более того, если найдутся $l_1, \dots, l_n \in \mathbb{N}$, удовлетворяющие этому неравенству, то существует префиксный код $C$ такой, что длины кодовых слов — $l_1, \dots, l_n$.
Пусть $l_{\max} = \max_{k=1}^n l_k$. Обозначим за $d^{l_{\max}}$
все слова длины $l_{\max}$. Заметим, что если у слова длины
$l_{\max}$ последний символ имеет код $l_i$, то это слово могло
получиться из любого слова длины $l_{\max} - l_i$. Обозначим
множество всех таких слов за $d^{l_{\max} - l_i}$ и рассмотрим их
сумму
\[
\sum_{i=1}^n d^{l_{\max} - l_i}.
\]
Так как код префиксный, то он невырожденный, поэтому
\[
\sum_{i=1}^n d^{l_{\max} - l_i} \leqslant d^{l_{\max}}.
\]
Действительно, если предположить, что
\[
\sum_{i=1}^n d^{l_{\max} - l_i} \gt d^{l_{\max}},
\]
то это означает, что, прибавив по одному символу к уже имеющимся
словам, мы уменьшили их количество, то есть по крайней мере два
кодовых слова совпали, что противоречит предположению о
невырожденности кода $C$.
Переписав сумму как
\[
\sum_{i=1}^n d^{l_{\max} - l_i} =
d^{l_{\max}} \sum_{i=1}^n d^{-l_i}
\]
и разделив обе части неравенства на $d^{l_{\max}} \gt 0$,
окончательно получаем, что
\[
\sum_{k=1}^n d^{-l_k} \leqslant 1.
\]
Для префиксного кода $C$ справедливо неравенство
\[
L(C) \geqslant H_d(X) = - \sum_{x \in X} p(x) \log_d p(x).
\]
Рассмотрим разницу
\[
H_d(X) - L(C)
=
- \sum_{x \in X} p(x) \log_d p(x) - \sum_{x \in X} p(x) l(x).
\]
Представив $l(x)$ в виде
\[
-l(x) = \log_d d^{-l(x)},
\]
получим, что
\[
\begin{aligned}
H_d(X) - L(C)
&=
- \sum_{x \in X} p(x) \log_d p(x)
- \sum_{x \in X} p(x) l(x) = \\
&=
- \sum_{x \in X} p(x) \log_d p(x)
+ \sum_{x \in X} p(x) \log_d d^{-l(x)} = \\
&=
\sum_{x \in X} p(x) \log_d \frac{d^{-l(x)}}{p(x)}.
\end{aligned}
\]
Пользуясь тем, что
\[
\begin{gathered}
\log_a b = \log_a c \cdot \log_c b, \\
\ln x \leqslant x - 1,
\end{gathered}
\]
получаем, что
\[
\begin{aligned}
H_d(X) - L(C)
&=
\sum_{x \in X} p(x) \log_d \frac{d^{-l(x)}}{p(x)} = \\
&=
\log_d e \sum_{x \in X} p(x) \ln \frac{d^{-l(x)}}{p(x)}
\leqslant \\
&\leqslant
\log_d e \sum_{x \in X} p(x)
\left[
\frac{d^{-l(x)}}{p(x)} - 1
\right]
= \\
&=
\log_d e \sum_{x \in X} \left[ d^{-l(x)} - p(x) \right] = \\
&=
\log_d e \left[ \sum_{x \in X} d^{-l(x)} - 1 \right] \leqslant 0
\end{aligned}
\]
в силу неравенства Крафта.
Итак, окончательно получаем, что \[ L(C) \geqslant H_d(X). \]
Оптимальное кодирование
Поставим прямую задачу условной оптимизации:
\[
\left\{
\begin{aligned}
&\sum_{x \in X} p(x) l(x) \to \min, \\
&\sum_{x \in X} d^{-l(x)} = 1.
\end{aligned}
\right.
\]
Составим для неё функцию Лагранжа:
\[
L(l(x), \lambda) = \sum_{x \in X} p(x) l(x) + \lambda \left[
\sum_{x \in X} d^{-l(x)} - 1
\right].
\]
Необходимое условие экстремума:
\[
\pd{L}{l(x)} = 0,
\]
то есть
\[
p(x) - \lambda \ln d \cdot d^{-l(x)} = 0.
\]
Отсюда найдём, что
\[
\sum_{x \in X} \frac{p(x)}{\lambda \ln d}
= \sum_{x \in X} d^{-l(x)} = 1.
\]
Но
\[
\sum_{x \in X} p(x) = 1,
\]
поэтому
\[
\frac{1}{\lambda \ln d} = 1, \implies \lambda = \frac{1}{\ln d}.
\]
Подставляя значение $\lambda$ в необходимое условие экстремума,
получаем, что
\[
d^{-l(x)} = p(x),
\]
то есть
\[
l(x) = \log_d \frac{1}{p(x)}.
\]
Так как длина должна быть целой, положим
\[
l(x) = \ceil{ -\log_d p(x) }.
\]
Если $\overline{C}$ — оптимальный префиксный код (в смысле
решения прямой задачи условной оптимизации), то
\[
L(\overline{C}) \leqslant H_d(X) + 1.
\]
Рассмотрим
\[
\begin{aligned}
\sum_{x \in X} d^{-l(x)}
&= \sum_{x \in X} d^{\ceil{ \log_d p(x) }} \leqslant \\
&\leqslant \sum_{x \in X} d^{\log_d p(x)} = \\
&= \sum_{x \in X} p(x) = 1,
\end{aligned}
\]
поэтому из теоремы Крафта следует, что существует префиксный код
$C$ длины $l(x)$.
По определению средней длины \[ \begin{aligned} L(C) &\bydef= \sum_{x \in X} p(x) l(x) = \\ &= \sum_{x \in X} p(x) \ceil{-\log_d p(x)} \leqslant \\ &\leqslant \sum_{x \in X} p(x) \paren{- \log_d p(x) + 1} = \\ &= H_d(x) + \sum_{x \in X} p(x) = \\ &= H_d(x) + 1. \end{aligned} \]
Код $\overline{C}$, для которого $l(x) = \ceil{ -\log_d p(x) }$,
называют кодом Шеннона.
Построение кода Шеннона происходит по следующему алгоритму:
- подсчитывают вероятности $p_i$ появления символов $x_i$;
- вычисляют длины $l_i = l(x_i) \bydef= \ceil{ -\log_d p_i }$;
- составляют кумулятивную вероятность: \[ \sum_{k=1}^{i-1} p_k; \]
- переводят каждую кумулятивную вероятность в двоичный код
- в качестве кодового слова для символа $x_i$ берут из разложения $i$-ой кумулятивной вероятности $l_i$ знаков после запятой.
| $x_i$ | $p(x_i)$ | $l_i$ | сумма от $0$ до $i-1$ | двоичный код суммы | итоговый код |
|---|---|---|---|---|---|
| $x_1$ | 0,36 | 2 | 0,0 | 0,0000 | 00 |
| $x_2$ | 0,18 | 3 | 0,36 | 0,0101 | 010 |
| $x_3$ | 0,18 | 3 | 0,54 | 0,1000 | 100 |
| $x_4$ | 0,12 | 4 | 0,72 | 0,1011 | 1011 |
| $x_5$ | 0,09 | 4 | 0,84 | 0,1101 | 1101 |
| $x_6$ | 0,07 | 4 | 0,93 | 0,1110 | 1110 |
Неравенство Крафта-Макмиллана для однозначно декодируемых кодов
(неравенство Крафта-Макмиллана).
Если код $C$ однозначно декодируемый, то \[ \sum_{x \in X} d^{-l(x)} \leqslant 1. \]
Если код $C$ однозначно декодируемый, то \[ \sum_{x \in X} d^{-l(x)} \leqslant 1. \]
Рассмотрим
\[
\begin{aligned}
\paren{ \sum_{x \in X} d^{-l(x)} }^k
&= \sum_{x_1 \in X} d^{-l(x_1)}
\cdots
\sum_{x_k \in X} d^{-l(x_k)} = \\
&= \sum_{(x_1, \dots, x_k) \in X^k}
d^{-l(x_1)} \cdots d^{-l(x_k)} = \\
&= \sum_{(x_1, \dots, x_k) \in X^k}
d^{-\left[l(x_1) + \cdots + l(x_k)\right]} = \\
&= \sum_{(x_1, \dots, x_k) \in X^k}
d^{-l(x_1, \dots, x_k)}.
\end{aligned}
\]
Обозначим число слов $(x_1, \dots, x_k)$, которые кодируются
словом длины $i$, как $\alpha(i)$. Заметим, что
\[
\alpha(i) \leqslant d^i
\]
в силу невырожденности кода $C$.
Действительно, если бы
\[
\alpha(i) \gt d^i,
\]
то, по
принципу Дирихле, нашлись бы по крайней мере два символа,
кодовые слова которых совпадали бы.
Тогда
\[
\begin{aligned}
\sum_{(x_1, \dots, x_k) \in X^k} d^{-l(x_1, \dots, x_k)}
&\leqslant
\sum_{i=k}^{k l_{\max}} 1 = \\
&= k l_{\max} - k + 1 \leqslant \\
&\leqslant k l_{\max}.
\end{aligned}
\]
Итак,
\[
\paren{ \sum_{x \in X} d^{-l(x)} }^k \leqslant k l_{\max}
\implies
\sum_{x \in X} d^{-l(x)} \leqslant \paren{ k l_{\max} }^{1/k}.
\]
В силу того, что $k \in \mathbb{N}$ произвольно, получаем, что
\[
\sum_{x \in X} d^{-l(x)}
\leqslant \lim_{k \to \infty} \paren{ k l_{\max} }^{1/k}
= 1.
\]
Если $C$ — однозначно декодируемый код с длинами кодовых слов
$l(x)$, то существует префиксный код $C'$ с теми же длинами кодовых
слов; отсюда также следует, что
\[
L(C) = L(C').
\]
Определение: информационная ёмкость канала
Рассмотрим два алфавита: входных $X$ и выходных $Y$ символов. Будем предполагать, что канал связи подвержен шумам. Пусть заданы условные вероятности $p(y|x)$ — вероятности получить на выходе $y$ при условии, что на вход подавался символ $x$.
Если известны вероятности $p(x)$ появления символа $x \in X$, то известны и вероятности $p(y)$, так как \[ p(y) = \sum_{x \in X} p(y|x) p(x). \] Для наглядности можно представить их в виде матрицы: \[ \begin{pmatrix} p(y_1|x_1) & \dots & p(y_1|x_n) \\ p(y_2|x_1) & \dots & p(y_2|x_n) \\ \vdots & \ddots & \vdots \\ p(y_m|x_1) & \dots & p(y_m|x_n) \end{pmatrix} \]
Величину
\[
C := \max_{p(x)} I(X,Y)
\]
называют информационной ёмкостью канала.
Свойства информационной ёмкости канала
-
$C \geqslant 0$.
Этот факт следует из неотрицательности взаимной информации $I(X,Y)$.
-
$C \leqslant \min \left[ \log l(X), \log l(Y) \right]$.
Неравенство напрямую следует из следующих соотношений: \[ \begin{gathered} I(X,Y) = H(X) - H(X|Y) \leqslant H(X) \leqslant l(X), \\ I(X,Y) = H(Y) - H(Y|X) \leqslant H(Y) \leqslant l(Y). \end{gathered} \]
- $C$ — непрерывная функция, достигающая максимума на компакте.
Примеры информационной ёмкости канала
$X = Y = \set{0, 1}$. Считаем, что шума нет:
Тогда взаимная информация
\[
I(X,Y) = H(X) - \underbrace{H(X|Y)}_{=0} = H(X)
\]
достигает максимума при $p(x=0) = p(x=1) = 1/2$, то есть
\[
C = \max_{p(x)} I(X,Y) = \log_2 2 = 1.
\]
$X = Y = \set{0, 1}$. Пусть канал симметричен:
Тогда
\[
I(X,Y) = H(Y) - H(Y|X).
\]
Но
\[
H(Y) \bydef= p(x=0) H(Y|x=0) + p(x=1) H(Y|x=1),
\]
причём
\[
H(Y|x=0) = H(Y|x=1) = -p \log p - (1-p) \log (1 - p).
\]
Введя обозначение
\[
h(p) := -p \log p - (1-p) \log (1 - p),
\]
получим, что
\[
\begin{aligned}
H(Y) &= p(x=0) h(p) + p(x=1) h(p) = \\
&= h(p) \left[ p(x=0) + p(x=1) \right] = \\
&= h(p).
\end{aligned}
\]
Принимая во внимание, что
\[
H(Y) \leqslant \log_2 l(Y) = \log_2 2 = 1,
\]
получаем, что
\[
C \leqslant 1 - h(p).
\]
Отметим, что при $p = 1/2$ информационная ёмкость канала обнуляется:
\[
\begin{aligned}
C &\leqslant 1 - h(p) = \\
&= 1 + p \log p + (1-p) \log (1 - p) = \\
&= 1 - \frac{1}{2} \log_2 2 - \frac{1}{2} \log_2 2 = \\
&= 1 - \log_2 2 = \\
&= 0.
\end{aligned}
\]
Это связано с тем, что при такой вероятности невозможно восстановить
информацию.
Передача информации по каналам с шумом. Основные определения
Рассмотрим процесс отправки сообщений:
\[
1,\dots,M
\overset{W}{\longrightarrow} E
\overset{x \in X^n}{\longrightarrow} p(Y|X)
\overset{y \in Y^n}{\longrightarrow} D
\overset{\hat{W}}{\longrightarrow}
\]
Будем предполагать, что
- сообщения равновероятны: \[ p_i = \frac{1}{M} \implies H = \log M; \]
- канал без памяти и без обратной связи: \[ p(y|x) = \prod_{i=1}^n p(y_i|x_i) \]
Величину
\[
R := \frac{\log M}{n}
\]
называют скоростью передачи информации при кодировании.
Величина
\[
\lambda_i := p(\hat{W} \neq i | w = i)
\]
характеризует
вероятность ошибиться при передачи сообщения $i$.
Обозначим максимальную вероятность ошибки как
\[
\lambda_{(n)} = \max_{i = 1,\dots,M} \lambda_i,
\]
а среднюю вероятность — как
\[
P_n^{\text{err}} := \frac{1}{M} \sum_{i=1}^M \lambda_i
\leqslant \lambda_{(n)}.
\]
Заметим, что
\[
R = \frac{\log M}{n} \implies
nR = \log M \implies M = 2^{nR}.
\]
Говорят, что скорость $R$ достижима, если существует
последовательность кодов для $\ceil{ 2^{nR} }$ сообщений словами
длины $n$, для которой
\[
\lim_{n \to \infty} \lambda_{(n)} = 0.
\]
Теорема Шеннона
Для доказательства понадобится
(Шеннона).
- Если скорость передачи информации $R$ такая, что \[ 0 \lt R \lt C, \] то $R$ достижима.
- Если $R$ — достижима, то $R \leqslant C$.
Определение: задача кластеризации
Кластеризация — задача группировки множества объектов
на подмножества (кластеры) таким образом, чтобы объекты из однго
кластера были более похожи друг на друга, чем на объекты из других
кластеров по какому-то критерию.
Определение: иерархическая кластеризация
Иерархическая кластеризация — множество алгоритмов
кластеризации, направленных на создание иерархии вложенных разбиений
исходного множества объектов.
Алгоритм иерархической кластеризации
Будем строить дерево от листьев к корню. В начальный момент времени
каждый объект содержится в собственном кластере. Далее происходит
итеративный процесс слияния двух ближайших кластеров до тех пор, пока
все кластеры не объединятся в один или не будет найдено необходимое
число кластеров. На каждом шаге необходимо уметь вычислять расстояние
между кластерами и пересчитывать расстояние между новыми кластерами.
Расстояние между одноэлементными кластерами определяется через
расстояние между объектами. Для вычисления расстояния между кластерами
на практике используются различные функции в зависимости от специфики
задачи:
- Метод одиночной связи: \[ R_{\min}(U,V) = \min_{u \in U, v \in V} \rho(u,v). \]
- Метод полной связи: \[ R_{\max}(U,V) = \max_{u \in U, v \in V} \rho(u,v). \]
- Метод средней связи: \[ R_{\avg}(U,V) = \frac{1}{\abs{U} \cdot \abs{V}} \sum_{u \in U} \sum_{v \in V} \rho(u,v). \]
Определение: алгоритм $k$-средних. Основная идея, цель алгоритма
Алгоритм $k$-средних — один из алгоритмов машинного
обучения, решающий задачу кластеризации. Этот алгоритм является
неиерархическим, итерационным методом кластеризации.
Основная идея алгоритма $k$-средних заключается в том, что данные произвольно разбиваются на кластеры, после чего итеративно перевычисляется центр масс для каждого кластера, полученного на предыдущем шаге, затем векторы разбиваются на кластеры вновь в соответствии с тем, какой из новых центров оказался ближе по выбранной метрике.
Цель алгоритма заключается в разделении $n$ наблюдений на $k$ кластеров таким образом, чтобы каждое наблюдение принадлежало ровно одному кластеру, расположенному на наименьшем расстоянии от наблюдения.
Математическое описание алгоритма $k$-средних
Дано:
- набор из $n$ наблюдений $X = \set{x_1, \dots, x_n}$, причём $x_i \in \mathbb{R}^d$;
- требуемое число кластеров $k \in \mathbb{N}$, причём\ $k \leqslant n$.
- $S_i \cap S_j = \varnothing, \quad i \neq j$;
- $\bigcup_{i=1}^k S_i = X$.
Шаги алгоритма $k$-средних
- Инициализация кластеров: выбирается произвольное множество точек $\mu_i$ рассматриваемых как начальные центры кластеров: \[ \mu_i^{(0)} = \mu_i, \qquad i = 1,\dots,k. \]
- Распределение векторов по кластерам: для всех $x_i \in X$ выбирается число $j$ такое, чтобы \[ j = \argmin_k \rho\paren{x_i, \mu_i^{(t-1)}}^2. \] Считаем, что $x_i \in S_j$.
- Пересчёт центров кластеров: \[ \mu_i^{(t)} = \frac{1}{\abs{S_i}} \sum_{x \in S_i} x_i, \qquad i = 1,\dots,k. \]
- Если \[ \mu_i^{(t)} = \mu_i^{(t-1)} \qquad \forall i = 1, \dots, k, \] то есть центры кластеров не изменились, то завершаем работу, иначе $t = t+1$ и возвращаемся на шаг 2.
Спектральная кластеризация. Постановка задачи
Имея набор данных $x_1, \dots, x_n$ и некоторую меру сходства
$s_{ij} \gt 0$, кластеризовать точки таким образом, чтобы в каждом
кластере точки были "похожи", а между кластерами — "не
похожи".
Если кроме меры сходства другой информации нет, то можно построить
граф сходства $G = (V,E)$:
- каждая вершина $v_i$ соответствует точке $x_i$;
- две вершины $v_i$ и $v_j$ соединены ребром $(v_i, v_j)$, если мера схожести $s_{ij}$ точек $x_i$ и $x_j$ положительна или превышает какое-нибудь заранее заданное пороговое значение, причём вес ребра зависит от $s_{ij}$.
Рассмотрим неориентированный взвешенный граф $G = (V,E)$ с весами
$w_{ij} \geqslant 0$.
Существует несколько подходов к построению графа по заданным точкам
$x_1, \dots, x_n$ с попарной мерой схожести $s_{ij}$ или попарным
расстоянием $d_{ij}$:
- Взвешенной матрицей смежности называют матрицу $W = \paren{w_{ij}}_{i,j=1,\dots,n}$. Если $w_{ij} = 0$, то вершины $v_i,v_j$ не соединены ребром. Граф неориентирован, поэтому $w_{ij} = w_{ji}$.
- Степенью вершины $v_i \in V$ называют величину \[ d_i = \sum_{j=1}^n w_{ij}. \] Степенной матрицей называют диагональную матрицу $D = \diag(d_1, \dots, d_n)$.
-
Граф $\varepsilon$-окрестностей
Соединяем все точки, расстояние между которыми не превышает некоторого наперёд заданного $\varepsilon$. Так как расстояния между всеми точками отличаются несильно, обычно такой граф считают невзвешенным.
-
Граф $k$-ближайших соседей
Соединяем вершину $v_i$ с ближайшими $k$ вершинами $v_j$. Однако отношение близости может быть несимметричным, поэтому получится ориентированный граф. Чтобы построить неориентированный граф, можно воспользоваться одним из двух подходов:
- можно проигнорировать ориентированность ребра, то есть соединить $v_i$ и $v_j$, если $v_j$ находится среди $k$ ближайших соседей $v_i$ или $v_i$ находится среди $k$ ближайших соседей $v_j$. Получившийся граф называют графом $k$ ближайших соседей.
- можно соединять вершины $v_i$ и $v_j$ только если $v_j$ находится среди $k$ ближайших соседей $v_i$ и $v_i$ находится среди $k$ ближайших соседей $v_j$. Получившийся граф называют графом $k$ взаимно ближайших соседей.
-
Полностью связный граф
В данном подходе мы просто соединяем все вершины $v_i$ и $v_j$ с положительной мерой схожести $s_{ij}$, и придаём им вес $s_{ij}$. Так как граф должен представлять отношение близости, построение подобного графа имеет смысл только в том случае, когда мера схожести сама моделирует окрестности. Пример такой меры — функция Гаусса: \[ s(x_i, x_j) = \exp \paren{ -\norm{x_i - x_j}^2 / (2 \sigma^2) }, \] причём параметр $\sigma$ регулирует размах окрестности.
Алгоритм спектральной кластеризации
-
Построить матрицу Кирхгофа:
\[
L = D - W,
\]
где
- $D$ — степенная матрица: \[ D_{i,j} = \begin{cases} \deg(v_i), & i = j, \\ 0, & \mbox{иначе}, \end{cases} \] где \[ \deg(v_i) := \sum_{j=1}^n w_{ij} \quad \mbox{—} \quad \mbox{степень вершины;} \]
- $W$ — матрица смежности: \[ W_{i,j} = \begin{cases} w_{ij}, & i \neq j \; \mbox{ и существует ребро } (v_i, v_j), \\ 0, & \mbox{иначе}, \end{cases} \] $w_{ij}$ — вес ребра $(v_i, v_j)$.
- Найти $k$ собственных векторов $u_i, \dots, u_k$, соответствующих наименьшим собственным числам (кроме 0);
- Построить матрицу $U \in \mathbb{R}^{n \times k}$ из векторов $u_1, \dots, u_k$ в качестве столбцов;
- Кластеризовать точки $y_k \in \mathbb{R}^k$, соответствующие строкам матрицы $U$ (например, с помощью алгоритма $k$-средних).
Метод опорных векторов для линейно разделимых выборок
Метод опорных векторов (support vector machine, SVM) — один из наиболее популярных методов обучения, который применяется для решения задач классификации и регрессии.
Основная идея метода заключается в построении гиперплоскости, разделяющей объекты выборки оптимальным способом. Алгоритм работает в предположении, что чем больше расстояние (зазор) между разделяющей гиперплоскостью и объектами разделяемых классов, тем меньше будет средняя ошибка классификатора.
Рассмотрим задачу бинарной классификации, в которой объектам из
$X = \mathbb{R}^n$ соответствует один из двух классов
$Y = \set{-1,+1}$. Пусть задана обучающая выборка пар "объект-ответ"
\[
T^l = (\vec{x}_i, y_i)_{i=1}^l.
\]
Необходимо построить алгоритм классификации $a: X \to Y$.
Пусть выборка линейно разделима, то есть существует некоторая гиперплоскость, разделяющая классы -1 и +1. Тогда в качестве алгоритма классификации можно использовать линейный пороговый классификатор: \[ \begin{aligned} a(\vec{x}) &= \sign \paren{ \dp{\vec{w}}{\vec{x}} - b} = \\ &= \sign \paren{ \sum_{i=1}^n w_i x_i - b}, \end{aligned} \] где $\vec{w} \in \mathbb{R}^n$ и $b \in \mathbb{R}$ — параметры гиперплоскости.
Для двух линейно разделимых классов возможны различные варианты построения гиперплоскостей. Метод опорных векторов выбирает ту гиперплоскость, которая максимизирует отступ между классами.
Отступ — характеристика, оценивающая, насколько объект
"погружён" в свой класс, насколько типичным представителем своего
класса он является. Чем меньше значение отступа, тем ближе объект
подходит к границе классов и тем выше становится вероятность ошибки.
Отступ $M_i$ отрицателен тогда и только тогда, когда алгоритм
$a(\vec{x})$ допускает ошибку на элементе.
Для линейного порогового классификатора отступ определяется уравнением: \[ M_i(\vec{w}, b) = y_i \cdot \paren{ \dp{\vec{w}}{\vec{x_i}} - b }. \]
Если выборка линейно разделима, то существует такая гиперплоскость,
отступ от которой до каждого объекта положителен:
\[
\exists \vec{w}, b: \qquad M_i(\vec{w}, b) \gt 0, \quad i = 1,
\dots, l.
\]
Заметим, что при умножении $\vec{w}$ и $b$ на константу $c \neq 0$ уравнение \[ \dp{c \vec{w}}{\vec{x_i}} - c b = 0 \] определяет ту же гиперплоскость, что и \[ \dp{\vec{w}}{\vec{x_i}} - b = 0, \] поэтому для удобства проведём нормировку: выберем константу $c \neq 0$ таким образом, чтобы $\min M_i(\vec{w}, b) = 1$. При этом в каждом из двух классов найдётся хотя бы один объект обучающей выборки, отступ которого равен этому минимуму: иначе можно было бы сместить гиперплоскость в сторону класса с бóльшим отступом, тем самым увеличив минимальное расстояние от гиперплоскости до объектов обучающей выборки.
Обозначим любой "граничный" объект из класса $+1$ как $\vec{x}_+$, а из класса $-1$ — как $\vec{x}_-$. их отступ равен единице, то есть \[ \left\{ \begin{aligned} M_+(\vec{w}, b) &= (+1) \cdot \paren{ \dp{\vec{w}}{\vec{x}_+} - b } = 1, \\ M_-(\vec{w}, b) &= (-1) \cdot \paren{ \dp{\vec{w}}{\vec{x}_-} - b } = 1. \end{aligned} \right. \] Нормировка позволяет ограничить разделяющую полосу между классами: \[ \set{ x: -1 \lt \dp{\vec{w}}{\vec{x}_i} - b \lt 1 }. \] Внутри неё не может лежать ни один объект обучающей выборки. Ширину разделяющей полосы можно выразить как проекцию вектора $\vec{x}_+ - \vec{x}_-$ на нормаль к гиперплоскости $\vec{w}$. Чтобы разделяющая гиперплоскость находилась на наибольшем расстоянии от точек выборки, ширина полосы должна быть максимальной: \[ \begin{aligned} \frac{\dp{\vec{x}_+ - \vec{x}_-}{\vec{w}}}{\norm{w}} &= \frac{ \dp{\vec{x}_+}{\vec{w}} - \dp{\vec{x}_-}{\vec{w}} - b + b }{\norm{w}} = \\ &= \frac{ (+1) \paren{ \dp{\vec{x}_+}{\vec{w}} - b } + (-1) \paren{ \dp{\vec{x}_-}{\vec{w}} - b } }{\norm{w}} = \\ &= \frac{ M_+(\vec{w}, b) + M_-(\vec{w}, b) }{\norm{w}} = \\ &= \frac{2}{\norm{w}} \to \max \implies \norm{w} \to \min. \end{aligned} \]
Полученный результат можно записать как постановку задачи оптимизации в терминах квадратичного программирования: \[ \left\{ \begin{aligned} &\norm{\vec{w}}^2 \to \min_{\vec{w}, b}, \\ &M_i(\vec{w}, b) \geqslant 1, \quad i = 1,\dots,l. \end{aligned} \right. \]
Метод опорных векторов с мягким зазором
На практике линейно разделимые выборки практически не встречаются: в данных возможны выбросы и нечёткие границы между классами. В таком случае метод опорных векторов требуется модифицировать, ослабив ограничения и позволив некоторым объектам попадать на территорию другого класса. Для каждого объекта отнимем от отступа некоторую положительную величину $\xi_i \gt 0$, но потребуем, чтобы эти введённые поправки были минимальны. Это приведёт нас к постановке задачи, называемой также методом опорных векторов с мягким отступом: \[ \left\{ \begin{aligned} &\frac{1}{2} \norm{\vec{w}}^2 + C \sum_{i=1}^l \xi_i \to \min_{\vec{w}, b, \xi}, \\ &M_i(\vec{w}, b) \geqslant 1 - \xi_i, \quad i = 1,\dots,l, \\ &\xi_i \geqslant 0, \quad i = 1, \dots, l. \end{aligned} \right. \] Отметим, что константу $C$ необходимо будет определить при помощи кросс-валидации.
См. больше в викиконспектах.
Задача линейной регрессии
Линейная регрессия — метод восстановления зависимости одной переменной $y$ от другой или нескольких других переменных $x$ с линейной функцией зависимости. Данный метод позволяет предсказывать значения зависимой переменной $y$ по значениям независимой переменной $x$.
Дано:
Задача:
\[
Q(\alpha) = \sum_{i=1}^n \paren{
f(x_i, \alpha) - y_i
}^2 = \norm{F \alpha - y}^2 \to \min_\alpha.
\]
- $f_1(x), \dots, f_n(x)$ — числовые признаки;
- модель многомерной регрессии: \[ f(x,\alpha) = \sum_{j=1}^n \alpha_j f_j(x), \qquad \alpha \in \mathbb{R}^n; \]
- обучающая выборка: \[ T^n = (x_i, y_i)_{i=1}^n; \]
- $x_i \in \mathbb{R}^n, y_i \in \mathbb{R}$.
Запишем необходимые условия экстремума в матричном виде: \[ \pd{Q}{\alpha} = 2 F^T \paren{ F \alpha - y } = 0. \] Отсюда следует нормальная система задачи МНК: \[ F^T F \alpha = F^T y, \] где $\dim F^T F = n \times n$.
Пусть \[ \alpha^* = (F^T F)^{-1} F^T y = F^+ y \] — решение, где $F^+$ — псевдообратная матрица. Тогда функционал примет значение \[ Q(\alpha^*) = \norm{P_F y - y}^2, \] где \[ P_F = F F^+ = F \paren{F^T F}^{-1} F^T \] — проекционная матрица.
Сингулярное разложение матрицы
У любой матрицы $A_{n \times m}$ существует разложение
\[
A_{n \times m} = U_{n \times n} \times \Sigma_{n \times m} \times
V_{m \times m}^T,
\]
где $U,V$ — ортогональные матрицы, а $\Sigma$ —
диагональная.
Свойства сингулярного разложения
- $U_{n \times n}$ ортогональна, $U^T U = I_n$, столбцы $u_i$ — собственные векторы матрицы $F F^*$;
- $V_{m \times m}$ ортогональна, $V^T V = I_m$, столбцы $u_i$ — собственные векторы матрицы $F^* F$;
- $\Sigma_{n \times m}$ диагональная: \[ \Sigma = \diag\paren{ \sqrt{\lambda_1}, \dots, \sqrt{\lambda_{\min(n,m)}} }, \] где $\lambda_j \geqslant 0$ — собственные значения матриц $F F^T$ и $F^T F$.
Гребневая регрессия
Гребневая, или ридж-регрессия — один из методов понижения размерности. Применяется для борьбы с избыточностью данных, когда независимые переменные коррелируют друг с другом, вследствие чего проявляется неустойчивость оценок коэффициентов многомерной линейной регрессии.
Рассмотрим задачу многомерной линейной регрессии: пусть существует линейная зависимость $f(x,\beta) = \dp{\beta}{x}$. Найдём вектор $\beta^*$, при котором достигается минимум среднего квадрата ошибки: \[ \begin{aligned} &Q(\beta) = \norm{F\beta - y}^2, \\ &\beta^* = \argmin_\beta Q(\beta). \end{aligned} \]
Используя МНК, находим решение: \[ \beta^* = (F^T F)^{-1} F^T y. \]
В условиях мультиколлинеарности матрица $F^T F$ становится плохо обусловленной. Для решения этой проблемы представим решение в виде \[ \beta^* = \paren{ F^T F + \lambda I_n }^{-1} F^T y, \qquad \lambda \geqslant 0. \] Это изменение увеличивает собственные значения матрицы $F^T F$, но не изменяет её собственные векторы. В результате получаем хорошо обусловленную матрицу.
Диагональная матрица $\lambda I_n$ называется гребнем.