Vectors

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

• векторы обозначаются строчными жирными буквами: \(\boldsymbol x\), \(\boldsymbol y\), \(\boldsymbol u\), \(\boldsymbol v\), \(\boldsymbol a\), \(\boldsymbol b, \ldots\);

• по умолчанию подразумевается, что вектор \(\boldsymbol x\) — это вектор-столбец:

\[\begin{split} \boldsymbol x = \begin{pmatrix} x_1 \\ \vdots \\ x_n \end{pmatrix}; \end{split}\]

• для записи в строчку вектор-столбец \(\boldsymbol x\) надо транспонировать:

  \[ \boldsymbol x^\top = (x_1, \ldots, x_n); \]

• зачастую направление записи вектора (в строчку или в столбец) не имеет существенного значения, и тогда для экономии места вполне допустима запись \(\boldsymbol x = (x_1, \ldots, x_n)\).

Компоненты вектора \(\boldsymbol x = (x_1, \ldots, x_n)\) называются его координатами. Обычно подразумевается, что компоненты вектора — это действительные числа, и поэтому пространство числовых векторов с \(n\) координатами обозначают \(\mathbb R^n\).

Vectors in Python

For numeric operations with matrices and vectors in Python there is NumPy library.

import numpy as np
vector = np.array([1, 2, 7])
print(vector)

[1 2 7]

The attribute dtype specifies the underlying type of the vector’s elements:

print(vector.dtype)
float_vector = np.array([-0.1, 1.123])
print(float_vector.dtype)

int64
float64

Vector operations

Над векторами определены две основные операции.

1. Сложение векторов: если

   \[\begin{split} \boldsymbol x = \begin{pmatrix} x_1 \\ \vdots \\ x_n \end{pmatrix}, \quad \boldsymbol y = \begin{pmatrix} y_1 \\ \vdots \\ y_n \end{pmatrix}, \text{ то } \boldsymbol x + \boldsymbol y = \begin{pmatrix} x_1 + y_1 \\ \vdots \\ x_n + y_n \end{pmatrix}. \end{split}\]

2. Умножение вектора на скаляр (число): если

   \[\begin{split} \boldsymbol x = \begin{pmatrix} x_1 \\ \vdots \\ x_n \end{pmatrix},\quad \alpha \in \mathbb R, \text{ то } \alpha \boldsymbol x = \begin{pmatrix} \alpha x_1 \\ \vdots \\ \alpha x_n \end{pmatrix}. \end{split}\]

Нулевой вектор \(\boldsymbol 0\), все координаты которого равны нулю, обладает свойством \(\boldsymbol x + \boldsymbol 0 = \boldsymbol x\), \(\boldsymbol x \in \mathbb R^n\).

Вектор \(-\boldsymbol x = (-1)\cdot \boldsymbol x\) называется противоположным вектором для вектора \(\boldsymbol x\). Вычитание векторов сводится к добавлению противоположного вектора: \(\boldsymbol y - \boldsymbol x = \boldsymbol y + (-\boldsymbol x)\).

Векторы \(\boldsymbol x\) и \(\boldsymbol y\) коллинеарны, если \(\boldsymbol y = \alpha \boldsymbol x\) при некотором \(\alpha \in \mathbb R\). Геометрически это означает, что коллинеарные векторы лежат на одной прямой, проходящей через начало координат.

In NumPy all these operations are straightforward:

x = np.linspace(0, 1, num=5)
y = np.arange(1, 6)
z = np.zeros(5)
print(x)
print(y)
print("Zero vector:", z)

[0.   0.25 0.5  0.75 1.  ]
[1 2 3 4 5]
Zero vector: [0. 0. 0. 0. 0.]

print("Sum:", x+y)
print("Diff:", y-x)

Sum: [1.   2.25 3.5  4.75 6.  ]
Diff: [1.   1.75 2.5  3.25 4.  ]

print(-y)

[-1 -2 -3 -4 -5]

Vector norm

Под длиной, или нормой, вектора \(\boldsymbol x = (x_1, \ldots, x_n)\) чаще всего понимают величину

\[ \Vert \boldsymbol x \Vert = \sqrt{\sum\limits_{k=1}^n x_k^2}. \]

Это так называемая евклидова норма вектора \(\boldsymbol x\), представляющая собой обобщение теоремы Пифагора на случай \(\mathbb R^n\).

Евклидова норма является частным случаем \(p\)-нормы (или нормы Минковского)

\[ \Vert \boldsymbol x \Vert_p = \bigg(\sum\limits_{k=1}^n |x_k|^p \bigg)^\frac 1p, \quad p \geqslant 1. \]

Норма Минковского превращается в

• евклидову норму при \(p=2\);

• манхэттенскую норму \(\Vert \boldsymbol x \Vert_1 = \sum\limits_{k=1}^n \vert x_k \vert\) при \(p=1\);

• максимальную норму $\(\Vert \boldsymbol x \Vert_\infty = \max \{\vert x_1 \vert, \ldots, \vert x_n \vert\}\)\( при \)p\to\infty$.

Упражнение. Пусть \(\boldsymbol x \in \mathbb R^n\). Докажите следующие неравенства:

1. \(\Vert \boldsymbol x \Vert_\infty \leqslant \Vert \boldsymbol x \Vert_1 \leqslant n\Vert \boldsymbol x \Vert_\infty\);

2. \(\Vert \boldsymbol x \Vert_\infty \leqslant \Vert \boldsymbol x \Vert_2 \leqslant \sqrt{n}\Vert \boldsymbol x \Vert_\infty\);

3. \(\Vert \boldsymbol x \Vert_2 \leqslant \Vert \boldsymbol x \Vert_1 \leqslant \sqrt{n}\Vert \boldsymbol x \Vert_2\).

Solution

Соотношения 1 и 2 немедленно следуют из неравенств

\[ \max\{a_1, \ldots, a_n\} \leqslant \sum\limits_{k=1}^n a_k \leqslant n\max\{a_1, \ldots, a_n\}, \]

справедливых для любых неотрицательных чисел \(a_1, \ldots, a_n\). Неравенство \(\Vert \boldsymbol x \Vert_2 \leqslant \Vert \boldsymbol x \Vert_1\) эквивалентно неравенству

\[ \sum\limits_{k=1}^n x_k^2 \leqslant \Big(\sum\limits_{k=1}^n \vert x_k\vert\Big)^2 = \sum\limits_{k=1}^n x_k^2 + \underbrace{2\sum\limits_{1\leqslant i < j\leqslant n} \vert x_i\vert \vert x_j\vert}_{\geqslant 0}, \]

которое, очевидно, выполнено. Наконец, последнее неравенство вытекает из неравенства Коши—Буняковского—Шварца.

\[ \Vert \boldsymbol x \Vert_1 = \sum\limits_{k=1}^n 1\cdot\vert x_k\vert \leqslant \sqrt{\sum\limits_{k=1}^n 1^2}\sqrt{\sum\limits_{k=1}^n \vert x_k\vert^2} = \sqrt n \Vert \boldsymbol x \Vert_2. \]

Упражнение. Докажите, что \(p\)-норма при \(1\leqslant p \leqslant \infty\) удовлетворяет следующим свойствам:

1. \(\Vert\boldsymbol x\Vert \geqslant 0\), \(\Vert\boldsymbol x\Vert = 0 \iff \boldsymbol x =\boldsymbol 0\);

2. \(\Vert\alpha \boldsymbol x \Vert = \vert\alpha\vert \Vert\boldsymbol x \Vert\) для всех \(\alpha \in \mathbb R\), \(\boldsymbol x \in \mathbb R^n\);

3. \(\Vert\boldsymbol x + \boldsymbol y\Vert \leqslant \Vert\boldsymbol x \Vert + \Vert\boldsymbol y \Vert\) для всех \(\boldsymbol x, \boldsymbol y \in \mathbb R^n\) (неравенство треугольника).

Solution

Первые два свойства легко проверяются напрямую. Свойство 3 для \(p=1\) и \(p=\infty\) следует из неравенства \(\vert a+b\vert \leqslant \vert a\vert + \vert b \vert\). Для остальных значений \(p\) неравенство треугольника эквивалентно неравенству Минковского{:target=”_blank”}.

Три свойства из последнего упражнения являются аксиомами нормы в \(\mathbb R^n\). Иначе говоря, всякая функция \(\Vert\cdot \Vert \colon \mathbb R^n \to [0, +\infty)\), удовлетворяющая этим трём свойством, по определению называется нормой. В частности, \(p\)-норма является нормой при \(1\leqslant p \leqslant \infty\). Отметим, что \(p\)-норма перестаёт быть нормой при \(p<1\), поскольку неравенство треугольника в таком случае не выполняется.

Вектор \(\boldsymbol x\) называется единичным, если его норма равна единице: \(\Vert \boldsymbol x\Vert = 1\). Единичным шаром в \(\mathbb R^n\) называется множество

\[ \{\boldsymbol x \in \mathbb R^n\colon \Vert \boldsymbol x \Vert \leqslant 1\}. \]

Для случая евклидовой нормы это действительно шар при \(n=3\) (круг при \(n=2\)). Единичные шары для \(p\)-нормы при различных значениях \(p\) изображены на рисунке ниже.

Расстояние между векторами \(\boldsymbol x\) и \(\boldsymbol y\) вычисляется по формуле \(\Vert \boldsymbol x - \boldsymbol y\Vert\). Норма здесь может быть любой, наиболее популярный выбор — опять же евклидова норма \(\Vert\boldsymbol x - \boldsymbol y\Vert_2\).

How to calculate norm in NumPy? Use np.linalg.norm

x = np.array([1, 2, -2])
np.linalg.norm(x)

3.0

To specify \(p\) use parameter ord:

print("1-norm =", np.linalg.norm(x, ord=1))
print("2-norm =", np.linalg.norm(x, ord=2))
print("10-norm =", np.linalg.norm(x, ord=10))
print("infinite norm =", np.linalg.norm(x, ord=np.inf))

1-norm = 5.0
2-norm = 3.0
10-norm = 2.143651567459133
infinite norm = 2.0

Inner product

Скалярным произведением векторов \(\boldsymbol x, \boldsymbol y \in \mathbb R^n\) называется величина

\[ \langle \boldsymbol x, \boldsymbol y \rangle = \sum\limits_{k=1}^n x_k y_k.\tag{1} \]

Альтернативное обозначение: \(\boldsymbol x^\top \boldsymbol y\) (объяснение этого обозначения см. в одной из следующих секций).

Скалярное произведение порождает евклидову норму в \(\mathbb R^n\):

\[ \sqrt{\langle \boldsymbol x, \boldsymbol x \rangle} = \Vert \boldsymbol x \Vert_2. \]

Упражнение. Докажите неравенство Коши—Буняковского—Шварца

\[ \bigg(\sum\limits_{k=1}^n x_k y_k\bigg)^2 \leqslant \sum\limits_{k=1}^n x_k^2 \sum\limits_{k=1}^n y_k^2, \]

Решение

Здесь{:target=”_blank”} можно найти 12 различных доказательств этого замечательного неравенства. Вот первое из них:

\[\begin{split} \begin{multline*} 0\leqslant \sum\limits_{i, j=1}^n (x_i y_j - x_j y_i)^2 = \\ =\sum\limits_{i=1}^n x_i^2 \sum\limits_{j=1}^n y_j^2 + \sum\limits_{i=1}^n y_i^2 \sum\limits_{j=1}^n x_j^2 - 2 \sum\limits_{i=1}^n x_i y_i\sum\limits_{j=1}^n x_j y_j = \\ =2\sum\limits_{i=1}^n x_i^2 \sum\limits_{j=1}^n y_j^2 - 2\bigg(\sum\limits_{i=1}^n x_i y_i\bigg)^2, \end{multline*} \end{split}\]

откуда и вытекает требуемое. Из приведённого рассуждения также следует, что неравенство Коши—Буняковского—Шварца обращается в равенство в следующих случаях:

• \(x_i = 0\) при всех \(i=1, \ldots, n\);

• \(y_i = 0\) при всех \(i=1, \ldots, n\);

• \(\frac{x_i}{y_i} = C\) при всех \(i=1, \ldots, n\).

С учётом введённых выше определений евклидовой нормы и скалярного произведения неравенство Коши—Буняковского—Шварца можно переписать в виде

\[ \vert\langle \boldsymbol x, \boldsymbol y \rangle\vert \leqslant \Vert \boldsymbol x \Vert \cdot \Vert \boldsymbol y \Vert. \]

Это неравенство обращается в равенство тогда и только тогда, когда векторы \(\boldsymbol x\) и \(\boldsymbol y\) коллинеарны.

Если скалярное произведение векторов \(\boldsymbol x\) и \(\boldsymbol y\) равно нулю, то они называются ортогональными. Угол \(\theta\) между двумя ненулевыми векторами \(\boldsymbol x\) и \(\boldsymbol y\) определяется из соотношения

\[ \cos \theta = \frac{\langle \boldsymbol x, \boldsymbol y \rangle}{\Vert \boldsymbol x\Vert \cdot \Vert \boldsymbol y\Vert}. \]

В силу неравенства Коши—Буняковского—Шварца эта дробь всегда находится в диапазоне от \(-1\) до \(1\), поэтому такое определение угла между векторами корректно. Если \(\langle \boldsymbol x, \boldsymbol y \rangle = 0\), то \(\cos\theta = 0\) и \(\theta = \frac \pi 2\). Таким образом, угол между ортогональными векторами равен \(90°\).

В анализе данных косинус угла между векторами часто берут в качестве меры их близости (cosine similarity): чем ближе \(\cos\theta\) к единице, тем более похожими считаются вектора. Похожая метрика косинусное расстояние (cosine distance) определяется по формуле \(1-\cos\theta\).

Отметим, что для вычисления скалярного произведения по формуле (1) требуется выполнить \(n\) умножений и \(n-1\) сложение. Если измерять трудоёмкость подсчёта скалярного произведения \(n\)-мерных векторов в количестве арифметических операций, то она составит \(O(n)\).

Dot product in NumPy

There are several way to calculate the inner product of two vectors in Python.

x = np.array([1, 2, 3])
y = np.array([1, -2, 2])
print(np.dot(x, y), x.dot(y), x @ y)

3 3 3