Кванторы и остальная нотация

Кванторы

$\forall x \in X : P(x)$ — «для всякого $x$ из $X$ верно $P(x)$».

$\exists x \in X : P(x)$ — «существует $x$ из $X$, для которого верно $P(x)$».

Двоеточие часто заменяют точкой, запятой или вообще опускают. Это не несёт смысла.

Порядок кванторов меняет смысл

Это главное, ради чего написан урок.

у каждого свой ключесть мастер-замоку Веры нет ключа

Кто какой замок открывает

	замок 1	замок 2	замок 3
Аня	✓	·	·
Боря	·	✓	·
Вера	·	·	✓

• ∀ человек ∃ замок «у каждого есть хоть один замок» — верно
• ∃ замок ∀ человек «есть замок, который открывают все» — ложно

$\forall x \, \exists y : P(x, y)$ — «для каждого $x$ найдётся свой $y$». Подходящий $y$ зависит от $x$.

$\exists y \, \forall x : P(x, y)$ — «есть один $y$, годящийся для всех $x$». Тот же $y$ обязан работать для каждого $x$.

Второе утверждение строго сильнее: из $\exists\forall$ всегда следует $\forall\exists$, но не наоборот.

В машинном обучении это различие живое. Сравните:

• «для любого $\varepsilon > 0$ существует $N$, такое что при $n > N$ ошибка меньше $\varepsilon$» — сходимость, $N$ зависит от $\varepsilon$;
• «существует $N$, такое что для любого $\varepsilon > 0$ …» — это было бы утверждение о точном равенстве после конечного числа шагов.

Первое верно, второе почти никогда.

Отрицание

Правило механическое: при отрицании кванторы меняются местами, отрицание проваливается внутрь.

$\neg\,\forall x : P(x) \;\equiv\; \exists x : \neg P(x)$ $\neg\,\exists x : P(x) \;\equiv\; \forall x : \neg P(x)$

Отсюда сразу следует, как опровергать утверждения: чтобы опровергнуть «для всех», достаточно одного контрпримера. Чтобы опровергнуть «существует», надо разобрать все случаи. Первое обычно легко, второе обычно тяжело.

argmin и argmax

$\min_x f(x) \in \R, \qquad \argmin_x f(x) \subseteq \text{область определения}$

$\min$ — это значение. $\argmin$ — это точка (или множество точек), где значение достигается. Разные типы.

Строго говоря, $\argmin$ возвращает множество, поэтому корректная запись — $\theta^* \in \argmin_\theta L(\theta)$. В статьях почти всегда пишут $=$, подразумевая, что минимум единственный.

Знаки, которые легко перепутать

Знак	Значение
$:=$	«определяется как» — вводит новое обозначение
$\equiv$	тождественно равно; иногда — сравнение по модулю
$\propto$	пропорционально: равно с точностью до константы
$\approx$	приближённо равно
$\sim$	«распределено как»: $X \sim \mathcal{N}(0,1)$. Или эквивалентность. По контексту
$\iff$	тогда и только тогда
$\Rightarrow$	влечёт
$\triangleq$	то же, что $:=$

Знак $\propto$ встречается в байесовском выводе постоянно: $p(\theta \mid x) \propto p(x \mid \theta)\, p(\theta)$ — нормировочная константа опущена, потому что её не надо считать.

Сокращения

Сокращение	Расшифровка	Что означает
iid	independent and identically distributed	независимы и одинаково распределены
s.t.	such that / subject to	«такой что» или «при ограничениях»
w.r.t.	with respect to	«по отношению к», «по переменной»
a.e.	almost everywhere	всюду, кроме множества меры нуль
a.s.	almost surely	с вероятностью 1
w.l.o.g.	without loss of generality	без ограничения общности
resp.	respectively	соответственно
i.e. / e.g.	id est / exempli gratia	«то есть» / «например»

Отдельно про s.t.: в задачах оптимизации это «subject to», ограничения:

$\min_x f(x) \quad \text{s.t.} \quad g(x) \le 0$

А в определениях — «such that». Одно и то же сокращение, два разных смысла, различаются контекстом.

Соглашения о буквах

• строчные греческие — параметры, скаляры: $\alpha$, $\theta$, $\lambda$
• строчные латинские — скаляры и векторы: $x$, $w$, $b$
• жирные строчные — векторы: $\mathbf{x}$
• заглавные — матрицы: $A$, $W$
• каллиграфические — множества и распределения: $\mathcal{X}$, $\mathcal{D}$, $\mathcal{N}$
• $\hat{\cdot}$ — оценка или предсказание: $\hat{y}$, $\hat{\theta}$
• $\tilde{\cdot}$ — «изменённая версия»: зашумлённая, аппроксимированная
• $\bar{\cdot}$ — среднее: $\bar{x}$
• $\cdot^*$ — оптимальное значение: $\theta^*$

O-нотация на рабочем уровне

$f = O(g)$ — «$f$ растёт не быстрее $g$ с точностью до константы». $\Omega$ — не медленнее. $\Theta$ — и то, и другое.

Знак равенства здесь — злоупотребление обозначением: $O(g)$ на самом деле множество функций, и правильнее было бы $f \in O(g)$. Все пишут $=$; читать это надо как «принадлежит».

В ML O-нотация чаще всего встречается в описаниях сложности внимания: $O(n^2 d)$ для обычного attention против $O(n d^2)$ для линейных вариантов — и весь смысл SSM-архитектур в этой замене.