1 Введение

В данной области информатики изучается задача построения прогноза некого явления по неким наперед зафиксированным данным, которые по постановке считаются непосредственно связанными с прогнозируемым явлением. Метод построения прогноза основан на изучении “исторических” полных данных, состоящих как из самих данных, так и правильного результата (явления). С данными необязательно связано время, поэтому историческими данными могут быть просто некие прецеденты.

Последний пример может создать впечатление, что для прогноза могут быть использованы только данные связанные с котировками ценных бумаг. На самом деле, для прогноза может пригодится, как ни странно, и решение предыдущего примера. Суть в том, что есть такая вещь как Ла-Нинья/Эль-Ниньо, от которой многое чего зависит. Например, сила ливней и соответственно факт затопления шахт в Австралии. Когда они затоплены цены на уголь обычно уходят в космос. Исторические котировки угля конечно могут схожий результат проследить, но они не смогут предсказать очередное Эль-Ниньо.

Если последнею задачу чуть переформулировать, то это уже будет задачей машинного обучения.

1.1 Постановка задачи

Перейдем к математическому языку. Задано множество объектов $\Omega$ и множество значений $\Gamma$, а также искомое отображения $\gamma :\Omega \to \Gamma$. Следует сразу отметить неоднозначность выбора множеств $\Omega$ и $\Upsilon$ даже в зафиксированной и обговоренной задаче (на подобие ранее приведенных примеров). При их фиксации в виде конкретных множеств задача уже будет носить частный характер (т.е. выбор этих множество уже является неким этапом в решении задачи).

Отметим, что в общем случае на $\Omega$ никаких тождеств не задано и не выполнено. Например, в теории вероятности требуют выполнения соответствующих аксиом. В рассматриваемом случае никаких таких дополнительных требований нет. Последнее означает, что $\Omega$ есть суть множество элементов $\omega$.

Пусть ${\Omega }^l\subseteq \Omega$. По построению, для $\forall \omega \in {\Omega }^l$ можно вычислить значение $\gamma \left(\omega \right)$. Следовательно, по ${\Omega }^l$ можно построить множество пар

Тогда, задачу можно сформулировать следующим образом: необходимо по ${\Lambda }^l$ построить функцию $\tilde{\gamma }$ приближающую искомую функцию $\gamma$, т. е. для $\forall \omega \in \Omega$ вычислить приближение к $\gamma \left(\omega \right)$. Подчеркну, что саму $\gamma$ использовать для построения нельзя. Она может быть использована только для оценки итогового качества.

В точки зрения науки машинного обучения традиционно произносится следующее словоблудие (жаргоны): ${\Omega }^l$ – множество произвольно выбранных обучающих элементов $\omega \in \Omega$, где $l$ от слова learn (т.е. обучение). Процесс построения функции $\tilde{\gamma }$ называется обучением. Пара $\left(\omega ,\gamma \left(\omega \right)\right)$, где $\omega \in {\Omega }^l$ – суть прецедент, а множество пар ${\Lambda }^l$ – обучающая выборка, т. е. то, что нам фактически дано для обучения. Последнее предполагает возможность обобщения, т.е. вычисления значения отображения $\tilde{\gamma }$ в произвольной точке $\Omega$ (а не только на самом множестве ${\Omega }^l$).

С практической точки зрения, естественно, часто предполагается, что введенные множества конечны, а именно – ${\Omega }^l={\left\{{\omega }_i\right\}}_{i=1}^{i=l}$, ${\Lambda }^l={\left\{\left({\omega }_i,{\gamma }_i=\gamma \left({\omega }_i\right)\right)\right\}}_{i=1}^{i=l}$.

Векторное пространство Для начала рассмотрим крайний случай, а именно – наложим на множество $\Omega$ выполнение аксиом векторного пространства. Последнее означает, что на множестве $\Omega$ дополнительно (в общем случае никаких операций на $\Omega$ не заданы) задана две операции $+$ и $\ast$. Напомним аксиомы....

Тогда оно есть суть векторное пространства ${ℝ}^n$ размерности $n$.

Пусть также искомая функция $\gamma$ линейна (опять же в общем случае таких требований не накладывается). Тогда легко восстановить функцию по линейно независимым прецедентам (${\left\{e_i\right\}}_{i=1}^{i=n}$). Так, из линейной независимости ${\left\{e_i\right\}}_{i=1}^{i=n}$ следует, что для $\forall \omega \in \Omega ={ℝ}^n,x=\omega$ верно $x={\sum }_1^n{x}_i{e}_i$, следовательно

Таким образом значение на произвольном $x$ определяется значением на базисных элементах (прецедентах).

В общем случае это конечно не так, поэтому приблизимся к такому случаю в следующем подразделе.

1.2 Типы множеств

В общем случае про $\Omega$ ничего не известно, в частности, на нем не определены вычислительные операции (как это было в ранее рассмотренном примере векторного пространства). Но, ввиду того, что данный курс предполагает построение некой функции в смысле математики (а также тезиса, что „все есть число“), множества $\Omega$ и $\Gamma$ предполагают некую математическую доработку или, иначе, подкрутку.

Функция от одного аргумента По аналогии с случайными величинами в теории вероятности, пусть существуют функции ${\left\{{\phi }_j:\Omega \to \Psi \right\}}_{j=1}^{j=n}$. Фактически функция ${\phi }_j$ по сути соответствует искомой задаче, т.е. мы сами строим $n$ вспомогательных функций ${\left\{{\phi }_j\right\}}_{j=1}^{j=n}$ схожих функций на $\gamma$. Разница в том, что в отличии от $\gamma$ мы знаем устройство функций ${\phi }_j$. Смысл этих функций в том, чтобы представить искомую $\gamma$ через них.

Дабы это все имело смысл про $\Psi$ уже требуется, что оно является алгебраическим множеством, т. е. фактически множества наделенные операциями +, -, *, /, а иногда и порядковыми <, >. Наиболее традиционными являются числовые множества: $ℝ$, $\mathbb{Z}$, ${\mathbb{Z}}_2$, $\mathbb{N}$ и тому подобные. Разумеется, что в качестве такого множества может выступить и ${ℝ}^k$: $\acute{\phi }\to {ℝ}^k$. В последнем случае, если не обговорено иное, заменим такую функцию $\acute{\phi }$ на множество функций ${\left\{{\acute{\phi }}_j:\Omega \to ℝ\right\}}_{j=1}^{j=k}$, перенумеруем их и включим в общих список.

Для множества $\Gamma$ по аналогии строиться функция $\psi :\Gamma \to \Psi$, где от $\psi$ дополнительно требуют существование обратной функции. Если не обговорено обратного, всюду далее считаем, что $\Psi$ есть суть $ℝ$.

Тогда, фактически, задача поиска значения искомой функции $\gamma$ в $\omega$ будет заменена на приближение значения $\psi \left(\gamma \left(\omega \right)\right)$ по значениям ${\phi }_i\left(\omega \right)$.

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

Так как считается, что функции ${\phi }_i$ и $\psi$ задаются экспертом, то считается что они зафиксированы. Последнее означает, что их построение как бы не является предметом рассмотрения науки машинного обучения. Считается, что этих значений достаточно для решения поставленной задачи.

Ввиду введенных ограничений часть ранее введенных определений может быть переформулирована следующим образом. Произвольному $\omega \in \Omega$ можно сопоставить вектор-строку

называемый на жаргоне признаковым описанием объекта $\omega$. Никто не говорит, что появится смысл в сложении в признаковом пространстве.

Тогда функцию $\tilde{\gamma }$, которую мы ищем, можно представить в виде: $\tilde{\gamma }={\psi }^{-1}\left(\tilde{f}\left(\phi \right)\right)$, где, например,

Если зафиксировать функции ${\phi }_i$ и $\psi$, то первоначальная задача сводится к построению функции $\tilde{f}$, которая зависит от математически понятных величин.

Уравнение также можно переписать в виде $\psi \left(\tilde{\gamma }\right)=f\left(\phi \right).$ Пусть $y_i=\psi \left(\gamma \left({\omega }_i\right)\right)$, где $i=1,...,i=l.$

Можно задавать и неявной функцией, но зачем усложнять...

Отметим, что может сложиться следующая ситуация: $\exists {\omega }_a,{\omega }_b\in \Omega$, ${\omega }_a\ne {\omega }_b$ такие что $\phi \left({\omega }_a\right)=\phi \left({\omega }_b\right)$, т.е. признаковые описания могут совпадать у не совпадающих элементов. Иначе говоря, в общем случае, функция $\phi$ необратима (отметим требование обратимости $\psi$).

Более того, мы будем предполагать, что на самом деле каждая из $\phi$ не обязательно определена на всем множестве $\Omega$, т.е. может $\exists \omega \in \Omega$ такое, что значение на каких-то из $\phi$ не определено.

Тем самым по ${\Omega }^l$ можно построить числовую матрицу данных

и соответственно матрицу значений

Не все значения $Y$ могут существовать.

У нас есть матрица $X$ и вектор (значений) Y. Можно составить систему линейных уравнений: $X𝜃=Y,$ где $𝜃=\left({𝜃}_1,...,{𝜃}_n\right)$.

Задание. Написать программу которая решает заданную систему в среднеквадратичном смысле. Применить к поиску прямой проходящей через точки лежащие почти на прямой: берем множество точек равномерно распределенных на отрезке $\left[a,b\right]$, далее для каждой точки строи значение y, далее добавляем к каждой из точек y на нормальное распределение. Ищем прямую проходящую через эти точки наилучшим образом в среднеквадратичном смысле.

Задание. Все аналогично предыдущему случаю. Но вместо прямой рассмотреть параболу, окружность, эллипс.

Функция от двух аргументов По аналогии экспертом можно ввести функцию и от двух аргументов. Это будет что-то наподобие метрики, т.е. она будет вычислять расстояние между объектами. Тривиальный способ применить метрику в действительных векторных пространствах. $\rho \left({\omega }_0,{\omega }_1\right)=\parallel \phi \left({\omega }_0\right)-\phi \left({\omega }_1\right)\parallel .$ Таким образом такую метрику всегда можно задать, но лучше если её построит эксперт исходя из частных соображений об объектах в $\Omega$.

В некоторых из методов обучения мы применим данную функцию. Смысл в не в том, что отсутствует переход в векторное пространство. Функции с большей арности обычно не применяются.

Иерархия признаковых пространств Естественно, что к $X$ и $Y$ можно отнестись как к $\acute{\Omega }$ и $\acute{\Gamma }$. Например, в новом признаковом пространстве будет добавлено произведение двух каких-то признаков. Тогда, всю иерархию промежуточных признаковых пространств можно выкинуть.

1.3 Класс задачи

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

Область значения в большей степени определяет класс задачи. Если множество бесконечное, непрерывное, то это задача регрессии (есть понятие близости, можно ошибиться на чуть-чуть.). Если оно конечное, то это классификация/кластеризация (нет понятия близости. ошибиться чуть чуть нельзя.).

Физика... трение и притяжение...

Животные ... классовый вид...

Кредит...

Разные типы ошибок: аппроксимация какой-то кривой и проведение кривой приближающей данные.

1.4 Качество восстановления

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

В единственной точке Пусть у нас есть две функции кандидата $f_0$ и $f_1$ на приближение искомой функции. Нам нужно понять какая функция лучше приближает. Мы можем проверить какое эти функции дают значение в некой точке $x_0=\phi \left({\omega }_0\right),{\omega }_0\in \Omega$ и сравнить его с истинным $y_0=\psi \left(\gamma \left({\omega }_0\right)\right)$.

В рамках данного обсуждения введем функцию близости:

измеряющая схожесть между двумя значениями из $\Gamma$. Она также может быть задана и на $\Psi$

Будем считать что у нас есть полиморфизм. Также учтем, что зная одно можно построить другое. Так, $\forall {\psi }_0,{\psi }_1$ можно положить $d\left({\psi }_0,{\psi }_1\right)=d\left(\psi \left({\psi }_0\right),\psi \left({\psi }_1\right)\right).$ И наоборот, $\forall y_0,y_1$ можно положить $d\left(y_0,y_1\right)=d\left({\psi }^{-1}\left(y_0\right),{\psi }^{-1}\left(y_1\right)\right).$

Заметим, что это функция $d$ не тоже самое, что функция $\rho$ близости задаваемая в $\Omega$.

В качестве $d$ обычно рассматривают:

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

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

Традиционно сравнивают функции в среднем, но можно и экстремальные значения (максимум/минимум) проверить.

Интегральная оценка качества задается следующим образом. Сначала задается множество ${\Omega }^t\subseteq \Omega$ элементов на которых и будет оценена построенная функция $f$.

Замечание. Можно формулу объяснить (усложнить) и посредством вероятностного подхода. Так, появится плотность распределения в качестве множителя. Но мы пока не будет усложнять формулу таким образом.

Опять же из практических соображений обычно отмеченное множество конечно: ${\Omega }^t={\left\{{\omega }_i^t\right\}}_{i=1}^{i=l},{\omega }_i\in \Omega$.

тестовых Можно было бы и взять максимум/минимум.

Вопрос выбора тестового множества будет рассмотрен отдельно.

1.5 Обучение

Задается экспертом. Берется некое параметрическое множество функций $\left\{g:\Omega x\Theta \to \Upsilon \right\}$, т.е. функции вида $g_{𝜃}\left(\omega \right)=g\left(\omega ,𝜃\right)$. Суть обучения заключается в оптимальном выборе значения $𝜃$. Данное семейство задается экспертом и от выбора этого множества существенным образом зависит успех решения задачи.

Гиперпараметр настраивается тестовым множеством.

Обобщающая способность! Не должна быть памятью. Переобучение и недообучение.

Не всему можно обучиться: Что-то с данными: 0)Плохо выбраны признаки. 1)Недостаточно данных. 2)На уровне $x_i$ и $y_i$ много шума. 3)Неоднозначный ответ.

Что-то с методов обучения. Он не подходит для данной задачи.