3  L3 // Математика для анализа данных

3.1 Дискретная математика

3.1.1 Алгебра логики

Логика исследует закономерности мышления, но делает это отлично от того, как этим занимается, например, психология. Формальная логика абстрагируется от связей мышления с какими-либо сторонами сознания и сосредотачивается на логической непротиворечивости и последовательности мышления. Таким образом, формальная логика — это наука об общих структурах правильного мышления в его языковой форме (Зегет (1985)).

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

3.1.1.1 Высказывания

Логика как наука имеет дело, прежде всего, с высказываваниями. Высказывание отражает определённую объективную1 связь между предметами. Высказывание истинно, если в нём содержится адеквантное отражение этой связи — в ином случае высказывание ложно. В общем случае высказывание существует с форме повествовательного предложения.

Например, высказывание «Земля вращается вокруг Солнца» отражает объективное отношение, поэтому оно истинно, а высказывание «страницы этой книги зелёного цвета» не адекватно отражает существующее положение дел, поэтому оно ложно.

Прежде всего, нас будут интересовать атомарные высказывания. Это элементарные высказывания, которые невозможно разделить на составляющие — более мелкие высказывания. Например, «четыре — это целое число» — это атомарное высказывание.

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

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

3.1.1.2 Логические операции

С атомарными высказываниями можно выполнять различные логические операции.

3.1.1.2.1 Инверсия

Самая простая операция — инверсия, или отрицание. Оно обозначается с помощью оператора \(\neg\). Это унарная операция, то есть она применяется к одной переменной. При отрицании значение истинности высказывания изменяется на противоположное, поэтому мы можнм составить следующую таблицу истинности для отрицания:

\(p\) \(\neg p\)
истина ложь
ложь истина

В данном случае с помощью переменной \(p\) обозначено некоторые атомарное высказывание.

Особо стоит отметить, что при отрицании отрицается всё высказывание целиком, а не какой-то отдельный его элемент. То есть формально правильным вариантом отрицания высказывания «все лебеди белые» будет следующий — «неверно, что все лебеди белые».

Графически инверсия отображается так:

Логическое отрицание

Из атомарных высказываний можно составлять сложные высказывания при помощи логических операторов. Например, высказывание «если четыре делится на два, то четыре — чётное число» является сложным, посколько состоит из двух атомарных — «четыре делится на два» и «четыре — чётное число» — соединённых союзом «если…, то…».

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

3.1.1.2.2 Конъюнкция

Конъюнкция (логическое умножение, логические И) представляет собой такое высказывание, которое наиболее точно передается следующей конструкцией естественного языка — «как \(p\), так и \(q\)».

\(p\) и \(q\) в данном случае пропозициональные переменные, которые заменяют конкретные высказывания. Конъюнкция истинна тогда и только тогда, когда обе пропозициональные переменные, входящие в её состав, имеют значении истинности «истина». В любом ином случае конъюнкция ложна.

Конъюнкция обозначается символом \(\wedge\) и имеет следующую таблицу истинности:

\(p\) \(q\) \(p \wedge q\)
истина истина истина
истина ложь ложь
ложь истина ложь
ложь ложь ложь

Графически конъюнкция отображается так:

Конъюнкция (логическое И)
3.1.1.2.3 Дизъюнкция

Дизъюнкция (логическое сложение, логические ИЛИ) представляет собой такое высказывание, которое наиболее точно передается следующей конструкцией естественного языка — «или \(p\), или \(q\), или и то и другое», поэтому дизъюнкция истинна тогда, когда хотя бы одна пропозициональная переменная, входящая в её состав, имеет значении истинности «истина». В случае, если оба высказывания ложны, дизъюнкция будет ложна.

Дизъюнкция обозначается символом \(\vee\) и имеет следующую таблицу истинности:

\(p\) \(q\) \(p \vee q\)
истина истина истина
истина ложь истина
ложь истина истина
ложь ложь ложь

Графически дизъюнкция отображается так:

Дизъюнкция (логическое ИЛИ)
3.1.1.2.4 Разделительная дизъюнкция

Разделительная дизъюнкция (исключающее ИЛИ) — это такое высказывание, которое наиболее полно описывается следующим выражением естественного языка — «либо \(p\), либо \(q\)». На её графическом представлении хорошо видно, чем она отличается от обычной дизъюнкции — она исключает ту часть пространства, где верны оба высказывания:

Разделительная дизъюнкция (исключающее ИЛИ)

Для обозначения разделительно дизъюнкции есть много различных операторов, но мы будем записывать её так — \(p \,\text{XOR}\,q\). По иллюстрации можно восстановить таблицу истинности для этого оператора:

\(p\) \(q\) \(p \,\text{XOR}\,q\)
истина истина ложь
истина ложь истина
ложь истина истина
ложь ложь ложь

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

3.1.1.3 Условные высказывания

3.1.1.3.1 Импликация

Сложное высказывание, описываемое конструкцией естественного языка «если \(p\), то \(q\)» в формальной логике носит название импликации. Она отражает следование одного утверждения из другого и обозначается следующим образом — \(p \rightarrow q\). Высказывание \(p\) называется антецедентом имликации, а \(q\) — консеквентом импликации.

Импликация имеет следующую таблицу истиности:

\(p\) \(q\) \(p \rightarrow q\)
истина истина истина
истина ложь ложь
ложь истина истина
ложь ложь истина

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

Импликацию утвержает то же самое, что и следующее сложное высказывание — \(\neg (p \wedge \neg q)\). Отсюда можно получить графическое изображение импликации:

Импликация \(p \rightarrow q\)
3.1.1.3.2 Репликация

Репликация похожа на импликацию, но действует как бы в обратном направлении, что отражено в её обозначении — \(p \leftarrow q\). Эта конструкция читается как «\(p\) реплицирует \(q\)» и является эквивалентом естественноязыкового «только если \(p\), то \(q\)». Соответствующим образом изменяется и таблица истиности:

\(p\) \(q\) \(p \leftarrow q\)
истина истина истина
истина ложь истина
ложь истина ложь
ложь ложь истина

Идея здесь в том, что если мы получили в результате истину, то лжи в начале быть не могло. Графическое изображение репликации выглядит так:

Репликация \(p \leftarrow q\)
3.1.1.3.3 Эквиваленция

Если мы соединим с помощью конъюнкции импликацию и репликацию, то есть запишем вот такое высказывание — \((p \rightarrow q) \wedge (p \leftarrow q)\) — то получим эквиваленцию. По своей сути она является логическим отражением языковой конструкции «\(q\) только тогда, когда \(p\)», поэтому она обозначается вот так — \(p \leftrightarrow q\) — и её таблица истинности выглядит соответствующим образом:

\(p\) \(q\) \(p \leftrightarrow q\)
истина истина истина
истина ложь ложь
ложь истина ложь
ложь ложь истина

Из неё выводится графическое представление эквиваленции:

Эквиваленция \(p \leftrightarrow q\)

3.1.2 Элементы теории множеств

На базе теории множеств стоит вся современная математика. Мы ознакомимся только c некоторыми концепциями этого раздела математики, но вообще полезно с ним познакомиться гораздо глубже.

3.1.2.1 Множество

Понятие множества неопределимо. По крайней мере силами самой теории множеств. Но мы будем понимать под множеством совокупность, или набор, некоторых (в общем случае любых) объектов. Это могут быть числа, буквы, точки и любые другие объекты. Объекты, входящие в состав множества, называются элементами этого множества.

Множества обозначают заглавными латинскими буквами (например, \(A\)), а его элементs — прописными латинскими буквами (например, \(a_1\), \(a_2\) и т.д.).

Множества удобно изображать кружочками. Примерно так:

Множество \(А\), содержащее элементы \(a_1\), \(a_2\), \(a_3\), \(a_4\), \(a_5\)

Если элемент входит в данное множество, то мы говорим, что этот элемент принадлежит данному множеству, и записываем это следующим образом:

\[ a_i \in A \]

Символ \(\in\) читается как «принадлежит».

Если мы хотим задать множество через перечисление элементов, то можно это сделать с помощью фигурных скобок вот так:

\[ B = \{ 0,1,2,3,4,5 \} \]

В данном случае множество \(B\) содержит 6 элементов — числа от нуля до пяти.

Приведём примеры множеств.

  • Множество букв русского алфавита: \(L = \{ а, б, в, г, д, \dots, э, ю, я \}\)
  • Множество всех натуральных чисел4: \(\mathbb{N}= \{ 0, 1, 2, 3, \dots \}\)
  • Множество всех целых чисел: \(\mathbb{Z}= \{0, 1, -1, 2, -2, 3, -3, \dots \}\)

Также из числовых множеств мы можем вспомнить рациональные числа \(\mathbb{Q}\), действительные (вещественные) числа \(\mathbb{R}\) и комплексные числа \(\mathbb{C}\).

Мы можем взять и рассмотреть не все элементы какого-то множества, а какую-то их часть. Например, взять элементы \(a_1\) и \(a_2\) и объединить их в множество поменьше.

Множество \(А_1\), состоящее из элементов \(a_1\) и \(a_2\), является подмножеством множества \(A\)

Мы получим множество \(A_1 = \{a_1, a_2\}\), которое является подмножеством множества \(A\). Иначе говоря, множество \(A_1\) включается во множество \(A\):

\[ A_1 \subset A \]

В частности, множество натуральных чисел включается во множество целых \(\mathbb{N}\subset \mathbb{Z}\). А если продолжить эту цепочку, то можно получить следующую иерархию числовых множеств:

\[ \mathbb{N}\subset \mathbb{Z}\subset \mathbb{Q}\subset \mathbb{R}\subset \mathbb{C} \]

Тривиальными подмножествами любого множества является пустое множество \(\varnothing\) и само это множество. Пусть \(M\) — любое множество. Тогда можно записать два справедливых утверждения:

\[ \varnothing \subset M \]

\[ M \subset M \]

3.1.2.2 Операции над множествами

3.1.2.2.1 Объединение

Над множествами можно производить определённые операции. Во-первых, множества можно складывать, или объединять:

\[ A + B = A \cup B = \{ x : x \in A \vee x \in B \} \]

Тогда в новом множестве окажутся все элементы обоих исходных множеств.

Объединение множеств \(A\) и \(B\)
3.1.2.2.2 Пересечение

Во-вторых, множества можно умножать, или находить их пересечение:

\[ A \cdot B = A \cap B = \{ x : x \in A \wedge x \in B \} \]

Тогда в новом множестве окажутся те элементы, которые принадлежат обоим множествам сразу.

Пересечение множеств \(A\) и \(B\)
3.1.2.2.3 Разность множеств

В-третьих, можно искать разность множеств:

\[ A ∖ B = \{ x : x \in A \wedge x \notin B \} \]

Разность множеств \(A\) и \(B\)

В частности, если мы будем искать разность между универсумом \(U\) — множеством, которое содержит вообще все возможные элементы — и множеством \(A\), мы получим дополнение множества \(A\):

\[ U ∖ A = A^c = \bar A = \{ x : x \notin A \} \]

Дополнение множества \(A\)
3.1.2.2.4 Симметрическая разность

А ещё можно вычитать множества друг из друга, то есть искать их симметрическую разность:

\[ A \, \Delta \, B = ( A ∖ B ) \cup ( B ∖ A ) = \{ x : x \in A \text{XOR} \x \in B \} \]

Симметрическая разность множеств \(A\) и \(B\)
3.1.2.2.5 Декартово произведение

Ну, и самое красивое — декартово произведение двух множеств. Пусть у нас есть два множества \(A\) и \(B\). Тогда их декартово произведение представляет собой множество всех возможных упорядоченных пар \((a,b), a \in A, b \in B\).

\[ A \times B = \{ (a,b) : a \in A, b \in B \} \]

Декартово произведение множеств \(A\) и \(B\)

Упорядоченность подразумевает, что если мы будем перемножать \(A \times B\), то будут получаться пары \((a,b)\), а если \(B \times A\), то пары \((b,a)\).

К слову, вспомните координатную плоскость — это ни что иное, как декартово произведение двух координатных прямых: \(\mathbb{R}\times \mathbb{R}= \mathbb{R}^2 = \{ (x, y) : x \in \mathbb{R}, y \in \mathbb{R}\}\).

3.1.2.3 Отображения

Мы можем сопоставлять элементы много множества элементам другого. Тогда мы получим отображение. Например, мы можем взять множество букв латинского алфавита и сопоставить каждому элменту этого множества число, которое будет отображать позицию буквы в алфавите. Пусть у нас есть множество букв латинского алфавита \(L\):

\[ L = \{ \text{a}, \text{b}, \text{c}, \text{d},\dots, \text{x}, \text{y}, \text{z} \} \]

и множество натуральных чисел от 1 до 26 \(N\):

\[ N = \{ 1,2,3, \dots,24,25,26 \} \]

Тогда мы можем задать такое отображение \(F\)

\[ F : L \rightarrow N, \]

где каждой букве будет соответствовать её порядковый номер в алфавите.

Мы обозначили отображение буквой \(F\), которой в математике часто обозначают функции — это не случайно. Не вдаваясь в детали, можно сказать, что термины «отображение» и «функция» — синонимы. Ведь по сути что делает [математическая] функция? Сопоставляет между собой значения числовых множеств. То есть отображает одно числовое множество в другое. Множество \(L\) в примере выше будет областью определения функции (domain), а множество \(N\) — множеством её значений (range)3.

Например, простая функция \(y = x\), \(x \in \mathbb{R}\), \(y \in \mathbb{R}\) отображает множество вещественных чисел в само себя — \(F : \mathbb{R}\rightarrow \mathbb{R}\). Функция модуля \(y = |x|\) отображает множество вещественных чисел во множество положительных вещественных чисел — \(F : \mathbb{R}\rightarrow \mathbb{R}_{+}\). И так далее.

В случае с буквами мы могли бы задать функцию \(f(l) = n\), \(l \in L\), \(n \in N\) которая возвращала бы следующие результаты:

\[ f(\text{a}) = 1, \quad f(\text{b}) = 2, \quad f(\text{z}) = 26 \]

Отображение \(F : L \rightarrow N\)

3.1.2.4 Мощность множества

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

Во-первых, множества могут быть конечными и бесконечными.

  • Если множество конечно, то его мощность равна количеству его элементов.
    • Например, множество очков, которое может выпать на стандартном игральном кубике — это \(S_1 = \{1,2,3,4,5,6\}\). Его мощность равна 6 — \(|M| = 6\).
    • Множество значений пятибалльной шкалы Ликерта — это \(S_2 = \{1, 2, 3, 4, 5\}\). Его мощность равна 5 — \(|S_2| = 5\).
  • Если множество бесконечно, то надо понять, насколько оно бесконечно.

Бесконечности бывают разного размера. В детали мы погружать не будем, однако отметим, что есть два вида бесконечностей.

  • Если можно построить отображение, в котором каждом элементу некоторого множества \(S\) будет сопоставлено единственное натуральное число4, то такое множество называется счётным.
    • Это значит, что элементов во множестве \(S\) бесконечное количество — так как количество натуральных чисел бесконечно — однако при неограниченном количестве времени их все-таки можно пересчитать.
    • Мощность такого множетсва обозначается \(\aleph_0\), то есть \(|\mathbb{N}| = \aleph_0\).
  • Если количество элементов множества больше количества натуральных чисел, то такое множество обладает **мощностью континуума* \(\aleph_1\).
    • Это множество будет равномощно множеству вещественных чисел \(\mathbb{R}\).

Возможно, это звучит весьма контринтуитивно — как одна бесконечность может быть больше другой? — однако это так: вещественных чисел больше, чем натуральных.

3.1.3 Элементы комбинаторики

3.1.3.1 Перестановки

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

Подойдём к вопросу технически: возьмем и начнём расставлять. На первое место мы можем поставить любую из пяти книг, то есть вариантов заполнить первое место на полке — пять штук. Когда первое место заполнено, то вариантов заполнить второе место остаётся четыре. Всего возможных вариантов заполнения первых двух мест получается \(5 \times 4\).

Заполняем далее: на третье место претендуют три оставшиеся книги, то есть вариантов, которыми мы можем расставить три книги — \(5 \times 4 \times 3\).

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

\[ 5 \times 4 \times 3 \times 2 \times 1 = 5! \]

Мы получили формулу числа перестановок из \(n\) элементов:

\[ P_n = n! \]

То есть любые \(n\) объектов можно расставить на \(n\) мест \(n!\) способами.

3.1.3.2 Размещения

3.1.3.2.1 Без повторений

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

Всего перестановок из пяти книг \(5!\), однако в силу того, что на полку умещаются только три первые книги из каждой перестановки, отличных друг от друга вариантов теперь будет меньше. Во сколько раз? В число раз, равно количеству перестановок из тех книг, которые на полку не помещаются. В нашем случае — \((5 - 3)!\).

То есть мы можем заполнить нашу полку \(\dfrac{5!}{(5-3)!}\) способами.

Мы получили формулу для подсчета числа размещений (без повторений) из \(n\) элементов по \(k\) местам:

\[ A_n^k = \frac{n!}{(n-k)!} \]

3.1.3.2.2 С повторениями

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

Теперь у нас неограниченное количество копий каждой из книг, поэтому при размещении трех из пяти книг на полке все три могут оказаться одной и той же, или две одинаковые, а одна отличается и т.д. Суть — книги могут повторяться.

Поскольку теперь, независимо от того, сколько книг мы уже поставили, у нас все равно осталось столько же, то есть 5 — ведь есть копии, каждый раз мы будем выбирать из пяти книг. Таких выборов нам нужно будет сделать три, так как три места на полке. Итого, заполнить нашу полку мы сможем \(5^3\) способами.

Мы получили формулу для подсчета числа размещений с повторениями из \(n\) элементов по \(k\) местам:

\[ \overline{A_n^k} = n^k \]

3.1.3.3 Сочетания

3.1.3.3.1 Без повторений

А теперь задача такова: нам не важно в каком порядке будут стоять книги на полке — нам нужно просто поставить три какие-то книги. Сколько возможно вариантов выбрать три книги из пяти?

Так как мы теперь не учитываем порядок книг, то возможных вариантов будет в \(3!\) раз меньше, чем число размещений. Почему? Так как все перестановки этих трёх книг для нас теперь идентичны. Итого, всего вариантов выбрать три книги из пяти \(\dfrac{5!}{3!(5-3)!}\).

Мы получили формулу для подсчета числа сочетаний из \(n\) элементов по \(k\):

\[ С_n^k = \frac{n!}{k!(n-k)!} \]

Последняя формула на пригодится далее при обсуждении схемы испытаний Бернулли.

3.1.3.3.2 С повторениями

Вновь для полноты картины посмотрим на случай с повторениями. У нас вновь есть неограниченное количество копий каждой книги, однако порядок выставления на полку нам не важен — как и было в сочетаниях. Количество сочетаний в этом случае будет равно

\[ \overline{С_n^k} = \frac{(n+k-1)!}{k!(n-1)!} \]

3.2 Элементы математического анализа

Из всего матана нам надо уловить два основных концепта — производную и интеграл. Эти и займёмся, захватив попутно немного пределов.

3.2.1 Последовательности

Числовая последовательность — это последовательность чисел [внезапно]. В общем случае — любых. Она обозначается \((x_n)^\infty_{n=1}\), где \(x_n\) — это некоторый элемент последовательности, а верхний и нижний индексы обозначают границы изменения индекса n. Например, \(\langle 1,-1,1,-1,\dots \rangle\) — это числовая последовательность, которую можно обозначить \(\big( (-1)^n \big)^\infty_{n=1}\).

Последовательность возникает на некотором множестве чисел. Если на таком множестве определено отношение порядка, то есть элементы этого множества можно сравнивать на «больше-меньше-равно», то можно сформировать монотонную последовательность. Это такая последовательность, которая не возрастает — то есть стоит на месте или убывает — или не убывает — то есть стоит на месте или возрастает. Более того, если существует такой объект (число), к которому элементы последовательности приближаются с ростом номер, то он является…

3.2.2 Предел последовательности

…пределом этой последовательности.

Разберемся на примере. Пусть у нас есть вот такая простенькая последовательность:

\[ \Big( \frac{1}{n} \Big)^{\infty}_{n=1} = \Big \langle 1, \frac{1}{2}, \frac{1}{3}, \dots \Big \rangle \]

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

Формально число \(a\) называется пределом последовательности \(\{x_n\}\), если для любого положительного числа \(\varepsilon\) существует номер \(N_\varepsilon\), такой что для любого \(n > N_\varepsilon\), выполняется равенство \(|x_n - a| < \varepsilon\), или на математическом:

\[ \lim_{n \rightarrow \infty} x_n = a \Leftrightarrow \forall \varepsilon > 0 \exists N_\varepsilon \in \mathbb{N}: n \geq N_\varepsilon, |x_n - a| < \varepsilon \]

То есть, в случае нашей последовательности мы можем отсутупить на сколь угодно малое число \(\varepsilon\) от нуля, и, начиная с какого-то номера, все элементы нашей последовательности окажутся в интервале \((\varepsilon, 0)\). Поэтому \(\lim_{n \rightarrow 0} \frac{1}{n} = 0\).

3.2.3 Функции

Функции (они же отображения, как мы выяснили выше) устанавливают соответствие между элементами двух множеств. Чаще всего мы имеет дело с числовыми функциями, то есть такими, которые ставят одни числа в соответствие другим. У любой функции есть область определения (множество \(X\)) и область значений (множество \(Y\)). Сама же функция представляет собой множество упорядоченных пар

\[ (x,y) \in X \times Y, \] таких что

  1. пары существуют для всех элементов \(X\), и
  2. если первые элементы пар равны, то равны и их вторые элементы.

Примерами функций могут быть \(y = x^2\), \(y = kx + b\), \(y = |x|\) и другие.

Примеры функций

3.2.3.1 Дискретные и непрерывные функции

В зависимости от того, какова область определение функции, то есть множество \(X\), функции могут быть дискретными и непрерывными. Например, если функция определена на множестве целых чисел \(\mathbb{Z}\), то она будет дискретная, так как между, например, \(1\) и \(2\) будет пусто.

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

Если функция определена на множестве \(\mathbb{R}\), то она будет непрерывной. Например, функция \(f(x) = x^2\) является непрерывной, как ифункции \(f(x) = \sqrt{x}\) и \(f(x) = \ln(x)\). Если функция непрерывная, то она дифференцируема5.

3.2.4 Производная

А раз они дифференцируемы, то мы можем взять производную!

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

Давайте издалека. Как нам узнать, куда двигается функция в данной точке?

Пусть дана функция \(f(x) = 2x^3 + 3x^2-4x+6\).

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

Шагнём на некоторую дистанцию \(\Delta x\) вправо (по направлению оси \(x\)). Назовём эту дистанцию приращением аргумента. В точке \(x_0 + \Delta x\) фунция будет иметь какое-то значение \(y_0 + \Delta y\), где \(\Delta y\) — приращение функции.

Наша функция движется из точки \((x_0,y_0)\) в точку \((x_0 + \Delta x, y_0 + \Delta y)\). Имеем следующий треугольник — приблизим картинку:

Нас интересует угол \(alpha\) — именно он задает скорость и направление изменения функции. Если мы узнаем, каков угол \(\alpha\) — а точнее \(\tan \alpha\), потому что так проще — то узнаем, куда движется функция.

\[ \tan \alpha = \frac{\Delta y}{\Delta x} \]

Ну, хорошо. Но мы шагали достаточно далеко от точки, которая нас интесует. Если мы будем постепенно уменьшать шаг, то получим последовательность

\[ \langle \tan \alpha_1, \tan \alpha_2, \tan \alpha_3, ... \rangle \]

У этой последовательности есть предел, и если мы его рассчитаем, то как раз и получим значение производной в данной точке.

\[ f'(x_0) = \lim_{\Delta x \rightarrow 0} \frac{\Delta f_(x)}{\Delta x} = \frac{df}{dx}(x_0) \]

Очень маленькое приращение обозначается \(dx\) (или \(df\) , если это приращение функции). Вот мы и получили производную.

Можно построить график производной. Это тоже будет функция.

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

3.2.5 Частная производная

Мы хорошо знакомы с функциями одной переменной, где некий \(y\) зависит от некоего \(x\) и более ни от чего не зависит. Однако в общем случае никто нам не может помешать задать следующую функцию:

\[ f(x, y) = 2x^2 + y^3 \]

Теперь у нас две переменные — \(x\) и \(y\) — и от них обоих зависит значение функции. Это даже можно изобразить:

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

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

Рассмотрим на примере нашей функции \(f(x, y) = 2x^2 + y^3\). Пусть мы хотим взять производную по \(x\). Тогда мы предполагаем следующее:

\[ y = \text{const}\Rightarrow y^3 = \text{const}= c \]

Фцнкция примет следующий вид:

\[ f(x, y) = 2x^2 + c, \]

а производная по \(x\) будет вычисляться следующим образом:

\[ \frac{\partial f(x, y)}{\partial x} = (2x^2 + c)' = (2x^2)' = 4x \]

\(\frac{\partial f(x, y)}{\partial x}\) — это обозначение частной производной, аналогично тому, как мы обозначали производную через \(\frac{dy}{dx}\).

Аналогично можно найти частную производную по \(y\):

\[ x = \text{const}\Rightarrow 2x^2 = \text{const}= c \]

\[ \frac{\partial f(x, y)}{\partial y} = (c + y^3)' = (y^3)' = 3x^2 \]

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

3.2.6 Интеграл

Интеграл — штука мощная, но нам он понадобится только с одной стороны. Нам надо будет искать площадь под кривой. Этим и займемся.

Пусть у нас есть функция \(y = \sqrt{x}\). Нам надо найти площадь под её графиком на отрезке от \(0\) до \(3\).

Мы можем разбить этот отрезок на части размером \(\Delta x\), а саму площадь на соответствующие прямоугольники. Это нам позволит оценить площадь. На рисунке ниже \(\Delta x = 0.25\).

Получается, площадь можно оценить, сложив площади всех прямоугольников:

\[ S \approx \sum_{i=1}^n y_i \Delta x \]

Ясно, что чем более узкими прямоугольники у нас будут, тем точнее мы будем знать площадь. Ниже представлены рисунки для случая \(\Delta x = 0.1\) и \(\Delta x = 0.05\).

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

\[ \lim_{\Delta x \rightarrow 0} \sum_{i = 1}^n y_i \Delta x = \int_a^b \sqrt{x}\,dx \]

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

\[ \int_0^3 \sqrt{x} \, dx \approx 3.46 \]

А раз есть определённый интеграл, значит есть и неопределённый. Рассмотрим следующую визуализацию:

Построение неопределенного интеграла

Мы смотрим, как изменяется площадь под графиком некоторой функции \(f(x)\) по мере нашего движения по оси \(x\) (нижний график), и строим график, по оси \(y\) которого расположена площадь под исходным графиком, левее данного \(x\). Этот график и отображает неопределенный интеграл, второе название которого первообразная. Неопределённый интеграл (первообразная) — это такая функция \(F(x)\), производная которой \(F'(x)\) равняется \(f(x)\), то есть исходной функции. Таким образом, справедливо равенство

\[ F'(x) = f(x) \]

А также справедливо соответствие между определённым и неопредленным интегралом:

\[ \int_a^b f(x) dx = F(b) - F(a) \]

3.3 Элементы линейной алгебры

«Увы, невозможно объяснить, что такое матрица. Ты должен увидеть это сам.» Морфеус (Матрица, 1999)

3.3.1 Системы линейных уравнений

Линейная алгебра занимается решением систем линейных уравнений. Да в общем-то и все. В самом общем виде система линейных уравнений выглядит так:

\[ \cases{ a_{11}x_1 + a_{12}x_2 + \cdots + a_{1m}x_m = b_1 \\ a_{21}x_1 + a_{22}x_2 + \cdots + a_{2m}x_m = b_2 \\ \cdots \\ a_{n1}x_1 + a_{n2}x_2 + \cdots + a_{nm}x_m = b_n \\ } \]

В данном случае это система из \(n\) уравнений с \(m\) неизвесными. Хотя такая запись математически предельно верна, выглядит она достаточно громоздко, и ею весьма трудно пользоваться. Поэтому обычно системы линейных уравнений записывают в матричном виде:

\[ \mathbf{A}\mathbf{x} = \mathbf{b} \]

Согласитесь, читать такое значительно проще. Здесь \(\mathbf{A}\) — это матрица коэффициентов системы, \(\mathbf{x}\) — вектор неизвестных, а \(\mathbf{b}\) — вектор свободных членов системы. Внутри они устроены вот так:

\[ \mathbf{A} = \pmatrix{ a_{11} & a_{12} & \cdots & a_{1m} \\ a_{21} & a_{22} & \cdots & a_{2m} \\ \vdots & \vdots & \ddots & \vdots \\ a_{n1} & a_{n2} & \cdots & a_{nm} } \quad \mathbf{x} = \pmatrix{x_1 \\ x_2 \\ \vdots \\ x_m} \quad \mathbf{b} = \pmatrix{b_1 \\ b_2 \\ \vdots \\ b_n} \]

Разберемся с этими структурами подробнее.

3.3.2 Векторы

Как мы уже знаем, вектор — это набор чисел. В зависимости от того, как он расположен, он может быть вектором-строкой (\(\mathbf{r}\)) или вектором-столбцом (\(\mathbf{c}\)):

\[ \mathbf{r} = \pmatrix{r_1 & r_2 & r_3 & \dots & r_n} \] \[ \mathbf{c} = \pmatrix{c_1 \\ c_2 \\ c_3 \\ \vdots \\ c_m} \]

Геометрически элементы вектора (числа) являются его координатами в некотором \(n\)-мерном пространстве. О переходе от вектора как направленного отрезка к вектору как набору чисел мы говорили в первой лекции.

Посмотрим, что можно делать с векторами на примере векторов \(\mathbf{v}\) и \(\mathbf{w}\), в которых есть по \(n\) элементов.

\[ \mathbf{v} = \pmatrix{v_1 & v_2 & v_3 & \dots & v_n} \]

\[ \mathbf{w} = \pmatrix{w_1 & w_2 & w_3 & \dots & w_n} \]

3.3.2.1 Сложение векторов

Векторы одинакоых размерностей можно складывать друг с другом:

\[ \mathbf{v} + \mathbf{w} = \pmatrix{v_1 + w_1 & v_2 + w_2 & v_3 + w_3 & \dots & v_n + w_n} \]

3.3.2.2 Умножение вектора на число

Вектор можно умножать на произвольное вещественное число:

\[ \alpha \cdot \mathbf{v} = \pmatrix{\alpha \cdot v_1 & \alpha \cdot v_2 & \alpha \cdot v_3 & \dots & \alpha \cdot v_n}, \quad \forall \alpha \in \mathbb{R} \]

3.3.2.3 Скалярное произведение векторов

Векторы одинаковых размерностей можно скаларярно умножить друг с другом. Скаларное произведение векторов определено как сумма произведений их соответствующих координат:

\[ \mathbf{v} \cdot \mathbf{w} = v_1 w_1 + v_2 w_2 + v_3 w_3 + \dots + v_n w_n \]

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

3.3.3 Матрицы

Как мы уже знаем, матрица — это двумерный массив чисел. Своего рода табличка. Соответственно, в матрице есть строки и столбцы. Это значит, что одну и ту же матрицу можно записать по-разному. Например, матрицу \(\mathbf{A}\), с которой мы встречались выше, можно записать:

  1. указав все элементы:

\[ \mathbf{A} = \pmatrix{ a_{11} & a_{12} & \cdots & a_{1m} \\ a_{21} & a_{22} & \cdots & a_{2m} \\ \vdots & \vdots & \ddots & \vdots \\ a_{n1} & a_{n2} & \cdots & a_{nm} } \]

  1. задав её через векторы-столбцы:

\[ \mathbf{A} = \pmatrix{ \mathbf{a_1} & \mathbf{a_2} & \cdots & \mathbf{a_m} \\ } \]

  1. задав её через векторы-строки:

\[ \mathbf{A} = \pmatrix{ \mathbf{a_1} \\ \mathbf{a_2} \\ \cdots \\ \mathbf{a_n} } \]

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

Матрица характеризуется, прежде всего, размером. В размере сначала указывается количество строк, затем — количество столбцов. Рассматриваемая нами матрица \(\mathbf{A}\) имеет размер \(n \times m\), что можно записать как \(\mathbf{A}_{n \times m}\).

  • Если количество строк и столбцов в матрице совпадает, она называется квадратной.
  • В матрице есть главная диагональ — слева сверху вправо вниз — и побочная диагональ — справа сверху влево вниз.
  • Квадратная матрица, все элементы которой, кроме стоящий на главной диагонали, равны нулю, называется диагональной матрицей.
  • Есть две замечательные матрицы: единичная \(\mathbf{I}\) (или \(\mathbf{E}\)) и нулевая \(\mathbf{O}\).

\[ \mathbf{I} = \mathbf{E} = \pmatrix{ 1 & 0 & \dots & 0 \\ 0 & 1 & \dots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \dots & 1 \\ } \quad \mathbf{O} = \pmatrix{ 0 & 0 & \dots & 0 \\ 0 & 0 & \dots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \dots & 0 \\ } \]

3.3.3.1 Сложение матриц

Две матрицы одинакового размера можно складывать друг с другом:

\[ \mathbf{A}_{n \times m} + \mathbf{B}_{n \times m} = \pmatrix { a_{11} + b_{11} & a_{12} + b_{12} & \dots & a_{1m} + b_{1m} \\ a_{21} + b_{21} & a_{22} + b_{22} & \dots & a_{2m} + b_{2m} \\ \vdots & \vdots & \ddots & \vdots \\ a_{n1} + b_{n1} & a_{n2} + b_{n2} & \dots & a_{nm} + b_{nm} \\ } \]

Свойства сложения матриц:

  1. Коммутативность: \(\mathbf{A} + \mathbf{B} = \mathbf{B} + \mathbf{A}\)
  2. Ассоциативность: \((\mathbf{A} + \mathbf{B}) + \mathbf{C} = \mathbf{A} + (\mathbf{B} + \mathbf{C})\)
  3. Существование нулевого элемента: \(\mathbf{A} + \mathbf{O} = \mathbf{A}\)
  4. Существование противоположного элемента: \(\mathbf{A} + (-\mathbf{A}) = \mathbf{O}\)

3.3.3.2 Умножение матрицы на число

Любую матрицу можно умножить на вещественное число:

\[ \alpha \cdot \mathbf{A} = \pmatrix{ \alpha \cdot a_{11} & \alpha \cdot a_{12} & \alpha \cdot \cdots & a_{1m} \\ \alpha \cdot a_{21} & \alpha \cdot a_{22} & \cdots & \alpha \cdot a_{2m} \\ \vdots & \vdots & \ddots & \vdots \\ \alpha \cdot a_{n1} & \alpha \cdot a_{n2} & \cdots & \alpha \cdot a_{nm} } \quad \forall \alpha \in \mathbb{R} \]

3.3.3.3 Матричное умножение

Штош, приступим.

  • Матрицы можно матрично перемножить друг с другом, если у них совпадают внутренние размерности.
  • Результатом перемножения \(\mathbf{A}_{n \times k} \times \mathbf{B}_{k \times m}\) является матрица \(\mathbf{C}_{n \times m}\).
  • Элемент \(c_{ij}\) матрицы \(\mathbf{C}\) равен скалярному произведению \(i\)-го вектора-строки матрицы \(\mathbf{A}\) и \(j\)-го вектора-столбца матрицы \(\mathbf{B}\).

Визуально:

Принцип матричного умножения

Теперь попробуем это расписать. Пусть есть две матрицы \(\mathbf{A}_{n \times k} \times \mathbf{B}_{k \times m}\), которые выглядят следующим образом:

\[ \mathbf{A} = \pmatrix{\mathbf{a}_1 \\ \mathbf{a}_2 \\ \vdots \\ \mathbf{a}_n} = \pmatrix{ a_{11} & a_{12} & \dots & a_{1k} \\ a_{21} & a_{22} & \dots & a_{2k} \\ \vdots & \vdots & \ddots & \vdots \\ a_{n1} & a_{n2} & \dots & a_{nk} } \]

\[ \mathbf{B} = \pmatrix{\mathbf{b}_1 & \mathbf{b}_2 & \dots & \mathbf{b}_n} = \pmatrix{ b_{11} & b_{12} & \dots & b_{1m} \\ b_{21} & b_{22} & \dots & b_{2m} \\ \vdots & \vdots & \ddots & \vdots \\ b_{k1} & b_{k2} & \dots & b_{km} } \]

\[ \mathbf{A} \times \mathbf{B} = \pmatrix{ \mathbf{a}_1 \cdot \mathbf{b}_1 & \mathbf{a}_1 \cdot \mathbf{b}_2 & \dots & \mathbf{a}_1 \cdot \mathbf{b}_m \\ \mathbf{a}_2 \cdot \mathbf{b}_1 & \mathbf{a}_2 \cdot \mathbf{b}_2 & \dots & \mathbf{a}_2 \cdot \mathbf{b}_m \\ \vdots & \vdots & \ddots & \vdots \\ \mathbf{a}_n \cdot \mathbf{b}_1 & \mathbf{a}_n \cdot \mathbf{b}_2 & \dots & \mathbf{a}_n \cdot \mathbf{b}_m \\ } = \]

\[ = \pmatrix{ (a_{11}b_{11} + a_{12}b_{21} + \dots + a_{1k}b_{k1}) & (a_{11}b_{12} + a_{12}b_{22} + \dots + a_{1k}b_{k2}) & \dots & (a_{11}b_{1m} + a_{12}b_{2m} + \dots + a_{1k}b_{km}) \\ (a_{21}b_{11} + a_{22}b_{21} + \dots + a_{2k}b_{k1}) & (a_{21}b_{12} + a_{12}b_{22} + \dots + a_{2k}b_{k2}) & \dots & (a_{21}b_{1m} + a_{22}b_{2m} + \dots + a_{2k}b_{km}) \\ \vdots & \vdots & \ddots & \vdots \\ (a_{n1}b_{11} + a_{n2}b_{21} + \dots + a_{nk}b_{k1}) & (a_{n1}b_{12} + a_{n2}b_{22} + \dots + a_{nk}b_{k2}) & \dots & (a_{n1}b_{1m} + a_{n2}b_{2m} + \dots + a_{nk}b_{km}) \\ } = \]

\[ = \pmatrix{ c_{11} & c_{12} & \dots & c_{1m} \\ c_{21} & c_{22} & \dots & c_{2m} \\ \vdots & \vdots & \ddots & \vdots \\ c_{n1} & c_{n2} & \dots & c_{nm} } = \mathbf{C} \]

\[ c_{ij} = \sum_{t=1}^k a_{it}b_{tj} \]

Свойства матричного умножения:

  1. Ассоциативность: \(\mathbf{A}(\mathbf{B}\mathbf{C}) = (\mathbf{A}\mathbf{B})\mathbf{C}\) и \(\alpha(\mathbf{A}\mathbf{B}) = (\alpha\mathbf{A})\mathbf{B} = \mathbf{A}(\alpha\mathbf{B})\)
  2. Дистрибутивность: \(\mathbf{A}(\mathbf{B} + \mathbf{C}) = \mathbf{A}\mathbf{B} + \mathbf{B}\mathbf{C}\) и \((\mathbf{A} + \mathbf{B})\mathbf{C} = \mathbf{A}\mathbf{C} + \mathbf{B}\mathbf{C}\)
  3. Отсутствие коммутативности: в общем случае \(\mathbf{A}\mathbf{B} \neq \mathbf{B}\mathbf{A}\)
  4. Умножение на единичный элемент: \(\mathbf{I}\mathbf{A} = \mathbf{A}\), \(\mathbf{A}\mathbf{I} = \mathbf{A}\)
  5. Умножение на нулевой элемент: \(\mathbf{O}\mathbf{A} = \mathbf{O}\), \(\mathbf{A}\mathbf{O} = \mathbf{O}\)
  6. Умножение на обратный элемент — выполняется только для некоторых квадратных матриц (см. ниже): \(\mathbf{A}\mathbf{A}^{-1} = \mathbf{A}^{-1}\mathbf{A} = \mathbf{I}\)

3.3.3.4 Транспонирование матрицы

Это очень простая операция — строки и столбы матрицы меняются местами:

\[ \mathbf{A} = \pmatrix{\mathbf{a}_1 & \mathbf{a}_2 & \dots & \mathbf{a}_n} = \pmatrix{ a_{11} & a_{12} & \dots & a_{1k} \\ a_{21} & a_{22} & \dots & a_{2k} \\ \vdots & \vdots & \ddots & \vdots \\ a_{n1} & a_{n2} & \dots & a_{nk} } \]

\[ \mathbf{A}^T = \pmatrix{\mathbf{a}_1 \\ \mathbf{a}_2 \\ \vdots \\ \mathbf{a}_n} = \pmatrix{ a_{11} & a_{21} & \dots & a_{n1} \\ a_{12} & a_{22} & \dots & a_{n2} \\ \vdots & \vdots & \ddots & \vdots \\ a_{1k} & a_{2k} & \dots & a_{nk} } \]

Если размер исходной матрицы был \(n \times k\), то размер транспонированной матрицы будет \(k \times n\).

3.3.3.5 Определитель и обратная матрица

Определитель (детерминант) матрицы \(\det \mathbf{A}\), \(|\mathbf{A}|\), \(\Delta A\) — это величина, которая может быть вычислена и поставлена в соответствие квадратной матрице. Он «определяет» свойства матрицы, в том числе одно из ключевых — её обратимость.

Вычисление детерминанта матрицы в общем случае является достаточно сложной задачей и требует введения дополнительных определений, поэтому ограничимся интерпретацией его значений:

  • Если матрица не является квадратной, то детерминант не определен.
  • Если детерминант матрицы не равен нулю, то:
    • система линейных уравнений, задаваемая данной матрицей имеет единственное решение
    • для данной матрицы существует обратная матрица, обладающая следующим свойством — \(\mathbf{A}\mathbf{A}^{-1} = \mathbf{I}\).
  • Если детерминан матрицы равен нулю, то система линейных уравнений имеет несколько решений.
    • Одной из причин может быть линейная зависимость между столбцами или строками матрицы — то есть ситуация, при который один из столбцов (одна из строк) линейной выражается через другой (другую).

3.3.3.6 След матрицы

След матрицы — это сумма элементов главной диагонали (квадратной) матрицы.

\[ \text{tr}(\mathbf{A}) = \sum_i a_{ii} \]

  1. Обсуждение критериев объективности мы оставим за рамками этого курса и постулируем, что мы их как-то хотя бы интуитивно пониманием. Для некоторой концептуальной рамки обозначим следующее: мы говорим об объективной связи между предметами, если (1) определённым предметам (или индивидам) присущи определённые признаки и если (2) определённым признакам свойственны определённые признаки (Зегет (1985)).↩︎

  2. Есть в другие подходы к определению истинности высказываний — таковы различные виды многозначной логики. Но они не-необходимы нам для целей курса, поэтому оставим их за бортом.↩︎

  3. В общем случае множеством значений может быть какое-либо подмножество этого множества. Так, мы вполне можем написать, что \(F: L \rightarrow \mathbb{N}\) — это будет корректное утверждение. Однако множество значений функции теперь является подмножеством множества натуральных чисел.↩︎

  4. Такое отображение называется биекцией.↩︎

  5. Хотя и не все. Непрерывность является необходимым, но недостаточным условием для дифференцируемости.↩︎