# Билеты 05.13.17 «Теоретические основы информатики» vol.1

## 1. Классификация случайных процессов. Марковские случайные процессы и их свойства.

[**Случа́йный проце́сс**](https://ru.wikipedia.org/wiki/Случайный_процесс) (вероятностный процесс, случайная функция, стохастический процесс) в теории вероятностей — семейство случайных величин, индексированных некоторым параметром, чаще всего играющим роль времени или координаты.

### Определение

Пусть $\displaystyle (E,{\mathfrak {B}})$ - измеримое пространство, $T$ множество значений параметра $t$. Функция $\displaystyle \xi =\xi (t)$ параметра $t \in T$, значениями которой являются случайные величины $\displaystyle \xi (t)=\xi (\omega ,t)$ на пространстве элементарных событий $\displaystyle (\Omega ,{\mathfrak {A}},\mathbb {P} )$ в фазовом пространстве $\displaystyle (E,{\mathfrak {B}})$, называется случайным процессом в этом фазовом пространстве.

### Основные сведения

1. Всевозможные совместные распределения вероятностей значений ${\displaystyle \xi (t_{1}),...,\xi (t_{n}),t_{1},...,t_{n}\in T}$: ${\displaystyle P_{t_{1}},...,_{t_{n}}(B_{1},...B_{n})=P\left\{\xi (t_{1})\in B_{1},...,\xi (t_{n})\in B_{n}\right\}(B_{1},...B_{n}\in {\mathfrak {B}}})$ называются **конечномерными распределениями вероятностей** случайного процесса $\xi =\xi (t)$.
2. **Ковариационная функция**. Пусть ${\displaystyle \xi =\xi (t)}$ действительный или комплексный случайный процесс на множестве ${\displaystyle T}$, имеющий вторые моменты: ${\displaystyle E|\xi (t)|^{2}<\infty }$. Значения случайного процесса ${\displaystyle \xi =\xi (t)}$ можно рассматривать как элементы [гильбертова пространства](https://ru.wikipedia.org/wiki/Гильбертово_пространство) $\displaystyle L^{2}(\Omega)$ — пространства всех случайных величин ${\displaystyle \eta}$, ${\displaystyle E|\eta (t)|^{2}<\infty }$, со скалярным произведением ${\displaystyle ({\eta }_{1},{\eta }_{2})=E{\eta }_{1}{\overline {\eta }}_{2}}$.

Важнейшими характеристиками такого случайного процесса ${\displaystyle \xi (t)}$ являются его **математическое ожидание** ${\displaystyle A(t)=E\xi (t)=(\xi (t),1)}$ и ковариационная функция ${\displaystyle B(s,t)=E{\xi (s)}{\overline {\xi (t)}}=(\xi (s),\xi (t))}$.
Вместо ковариационной функции может применятся **корреляционная функция** ${\displaystyle B(s,t)=E{\xi (s)}{\overline {\xi (t)}}-A(s){\overline {A(t)}}}$, являющуюся ковариационной функцией процесса ${\displaystyle \xi (t)-A(t)}$ с нулевым математическим ожиданием.
При равенстве аргументов (${\displaystyle s=t}$) корреляционная функция равна **дисперсии** случайного процесса:
${\displaystyle B(s,s)=E(\xi (s)-A(s))({\overline {\xi (s)-A(s)}})=D(s)}$.

### Классификация

* Случайный процесс ${X(t)}$ называется **процессом дискретным во времени**, если система, в которой он протекает, меняет свои состояния только в моменты времени $\displaystyle \;t_{1},t_{2},\ldots$, число которых конечно или счётно. Случайный процесс называется **процессом с непрерывным временем**, если переход из состояния в состояние может происходить в любой момент времени.
* Случайный процесс называется **процессом с непрерывными состояниями**, если значением случайного процесса является непрерывная случайная величина. Случайный процесс называется **случайным процессом с дискретными состояниями**, если значением случайного процесса является дискретная случайная величина:
* Случайный процесс называется **стационарным**, если все многомерные законы распределения зависят только от взаимного расположения моментов времени $\displaystyle \;t_{1},t_{2},\ldots ,t_{n}$, но не от самих значений этих величин. Другими словами, случайный процесс называется стационарным, если его вероятностные закономерности неизменны во времени. В противном случае, он называется **нестационарным**.
* Случайная функция называется **стационарной в широком смысле**, если её математическое ожидание и дисперсия постоянны, а АКФ (автокорреляционная функция) зависит только от разности моментов времени, для которых взяты ординаты случайной функции. Понятие ввёл А. Я. Хинчин.
* Случайный процесс называется **процессом со стационарными приращениями определённого порядка**, если вероятностные закономерности такого приращения неизменны во времени. Такие процессы были рассмотрены Ягломом.
* Если ординаты случайной функции подчиняются нормальному закону распределения, то и сама функция называется **нормальной**.
* Случайные функции, закон распределения ординат которых в будущий момент времени полностью определяется значением ординаты процесса в настоящий момент времени и не зависит от значений ординат процесса в предыдущие моменты времени, называются [**марковскими**](https://ru.wikipedia.org/wiki/Марковский_процесс).
* Случайный процесс называется **процессом с независимыми приращениями**, если для любого набора ${\displaystyle t_{1},t_{2},\ldots ,t_{n}}$, где ${\displaystyle n>2}$, а ${\displaystyle t_{1}<t_{2}<\ldots <t_{n}}$, случайные величины ${\displaystyle (X_{t_{2}}-X_{t_{1}})}$, ${\displaystyle (X_{t_{3}}-X_{t_{2}})}$, ${\displaystyle \ldots }$, ${\displaystyle (X_{t_{n}}-X_{t_{n-1}})}$ независимы в совокупности.
* Если при определении моментных функций стационарного случайного процесса операцию усреднения по статистическому ансамблю можно заменить усреднением по времени, то такой стационарный случайный процесс называется **эргодическим**.
* Среди случайных процессов выделяют [импульсные случайные процессы](https://ru.wikipedia.org/wiki/Импульсный_случайный_процесс).

### Марковский случайный процесс

**Ма́рковский проце́сс** — случайный процесс, эволюция которого после любого заданного значения временно́го параметра ${\displaystyle t}$ не зависит от эволюции, предшествовавшей ${\displaystyle t}$, при условии, что значение процесса в этот момент фиксировано («будущее» процесса не зависит от «прошлого» при известном «настоящем»).

**Процесс Маркова** — модель авторегрессии первого порядка AR(1): ${\displaystyle X_{t}=c+\alpha X_{t-1}+\varepsilon _{t}}$.

**Марковская цепь** — частный случай марковского процесса, когда пространство его состояний дискретно (т.е. не более чем счетно).

**Пример марковского процесса**
Рассмотрим простой пример марковского случайного процесса. По оси абсцисс случайным образом перемещается точка. В момент времени ноль точка находится в начале координат и остается там в течение одной секунды. Через секунду бросается монета — если выпал герб, то точка X перемещается на одну единицу длины вправо, если решка — влево. Через секунду снова бросается монета и производится такое же случайное перемещение, и так далее. Процесс изменения положения точки («блуждания») представляет собой случайный процесс с дискретным временем (t=0, 1, 2, …) и счетным множеством состояний. Такой случайный процесс является марковским, так как следующее состояние точки зависит только от настоящего (текущего) состояния и не зависит от прошлых состояний (неважно, каким путём и за какое время точка попала в текущую координату).

**На русской вики нет свойств марковского процесса, на английской вики только свойства [марковской цепи](https://en.wikipedia.org/wiki/Markov_chain#Properties). Мб стоит добавить.**

---

## 2. Анализ свойств и задачи оптимизации процессов обработки информации в вычислительных системах и комплексах.

---

## 3. Аналитические и статистические методы исследования характеристик процессов.

[*Источник*](https://studme.org/98107/informatika/analiticheskie_statisticheskie_metody)

### Аналитические методы

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

Эта особенность аналитических представлений условно иллюстрируется символическим образом, т.е. преобразованием сложной системы посредством некоторого оператора Ф[x] в точку, обладающую каким-то поведением, описываемым строгими соотношениями, нередко имеющими силу закона.

Основу понятийного (терминологического) аппарата этих представлений составляют понятия классической математики (*величина, формула, функция, уравнение, система уравнений, логарифм, дифференциал, интеграл и т.д.*). Аналитические представления имеют многовековую историю развития.

На базе аналитических представлений возникли и развиваются математические теории различной сложности – от аппарата классического математического анализа до новых разделов современной математики (*математическое программирование, теория игр и т.п.*).

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

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

### Статистические методы

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

Статистические отображения системы в общем случае (по аналогии с аналитическими) представляются символическим образом, как бы в виде "размытой" точки (размытой области) в n-мерном пространстве, в которую переводит учитываемые в модели свойства системы оператор Ф[x]. Границы области заданы с некоторой вероятностью *р* ("размыты") и движение точки описывается некоторой случайной функцией.

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

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

### Суть:

**Аналитические методы** - описание реальностии через законы и уравнения.
**Статистические методы** - описание реальности через случайные велицины и статистические закономерности.

---

## :Question: 4. Методы и средства кодирования информации в виде данных. Проектирование моделей данных.

### Определения
**Код** - набор условных обозначений для представления информации.

**Кодирование** - процесс представления информации в виде кода: представление символов одного алфавита символами другого; переход от одной формы представления информации к другой, более удобной для хранения, передачи или обработки.

## :Question: 5. Системы управления базами данных. Языки манипулирования данными, языки запросов.

**Cистемы управления базами данных (СУБД)** - программные комплексы, предназначенные для ведения баз данных.

**База данных** - TODO.

https://files.nazaryev.ru/ifmo/fourth-year/databases/Exam/4.pdf

---

## :Question: 6. Семантические сети. Фреймы - системно-структурное описание предметной области. Продукционные системы представления знаний. Канонические системы Поста. Редукционные системы.

### Семанти́ческая сеть

[**Семанти́ческая сеть**](https://ru.wikipedia.org/wiki/Семантическая_сеть) — информационная модель предметной области, имеет вид ориентированного графа. Вершины графа соответствуют объектам предметной области, а дуги (рёбра) задают отношения между ними. Объектами могут быть: понятия, события, свойства, процессы. Таким образом, семантическая сеть — это один из способов представления знаний.

### Фрейм

[**Фрейм**](https://ru.wikipedia.org/wiki/Фрейм_(инженерия_знаний)) (англ. frame — «каркас» или «рамка») — способ представления знаний в искусственном интеллекте, представляющий собой схему действий в реальной ситуации. Первоначально термин «фрейм» ввёл Марвин Минский в 70-е годы XX века[1] для обозначения структуры знаний для восприятия пространственных сцен. Фрейм — это модель абстрактного образа, минимально возможное описание сущности какого-либо объекта, явления, события, ситуации, процесса.

**Структура фрейма**
Фрейм отличает наличие определённой структуры. Фрейм состоит из имени и отдельных единиц, называемых **слотами**. Он имеет однородную структуру:

ИМЯ ФРЕЙМА
 Имя 1-го слота: значение 1-го слота
 Имя 2-го слота: значение 2-го слота
 ………………………………
 Имя N-го слота: значение N-го слота

В качестве значения слота может выступать имя другого фрейма. Таким образом фреймы объединяются в сеть. Свойства фреймов наследуются сверху вниз, то есть от вышестоящих к нижестоящим через так называемые АКО-связи (от англ. A Kind Of — «разновидность»). Слот с именем АКО указывает на имя фрейма более высокого уровня иерархии.

Помимо конкретного значения в слоте могут храниться процедуры и правила, которые вызываются при необходимости вычисления этого значения. Среди них выделяют процедуры-демоны и процедуры-слуги. Первые запускаются автоматически при выполнении некоторого условия, а вторые активизируются только по специальному запросу. Если, например, фрейм, описывающий человека, включает слоты ДАТА РОЖДЕНИЯ и ВОЗРАСТ и в первом из них находится некоторое значение, то во втором слоте может стоять имя процедуры-демона, вычисляющей возраст по дате рождения и текущей дате и активизирующейся при каждом изменении текущей даты.

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

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

О системах программирования, основанных на фреймах, говорят, что они являются объектно-ориентированными. Каждый фрейм соответствует некоторому объекту предметной области, а слоты содержат описывающие этот объект данные, то есть в слотах находятся значения признаков объектов. Фрейм может быть представлен в виде списка свойств, а если использовать средства базы данных, то в виде записи.

### Продукционная модель представления знаний

[**Продукционная модель знания**](https://ru.wikipedia.org/wiki/Продукционная_модель_представления_знаний) — модель, основанная на правилах, позволяет представить знание в виде предложений типа «Если (условие), то (действие)».

Продукционная модель — фрагменты Семантической сети, основанные на временных отношениях между состояниями объектов.

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

Продукционная модель часто дополняется определённым порядком, вводимым на множестве продукций, что упрощает механизм логического вывода. Порядок может выражаться в том, что отдельная следующая по порядку продукция может применяться только после попыток применения предшествующих ей продукций. Примерно похожее влияние на продукционную модель может оказать использование приоритетов продукций, означающее, что в первую очередь должна применяться продукция, имеющая наивысший приоритет.

Рост противоречивости продукционной модели может быть ограничен путём введения механизмов исключений и возвратов. Механизм исключений означает, что вводятся специальные правила-исключения. Их отличает большая конкретность в сравнении с обобщёнными правилами. При наличии исключения основное правило не применяется. Механизм возвратов же означает, что логический вывод может продолжаться в том случае, если на каком-то этапе вывод привёл к противоречию. Просто необходимо отказаться от одного из принятых ранее утверждений и осуществить возврат к предыдущему состоянию.нформации в качестве результатов информационного поиска.

### Канонические системы Поста

[**Каноническая система Поста**](https://en.wikipedia.org/wiki/Post_canonical_system), созданная Эмилем Постом, представляет собой систему манипулирования строками, которая начинается с конечного числа строк и многократно преобразует их, применяя конечное множество заданных правил определенной формы, таким образом генерируя формальный язык. Сегодня они в основном имеют историческое значение, потому что каждая Постканоническая система может быть сведена к системе перезаписи строк ([semi-Thue](https://en.wikipedia.org/wiki/String_rewriting_system)), что является более простой формулировкой. Оба формализма являются [полными по Тьюрингу](https://en.wikipedia.org/wiki/Turing_completeness).

**Определение**
Канонической системой Поста является тройка $\displaystyle (A,I,R)$, где

$A$ -- это конечный алфавит, и конечные (возможно, пустые) строки на $A$ называются словами.
$I$ -- это конечный набор начальных слов.
$R$ -- это конечный набор правил преобразования строк (называемых производственными правилами)

**Пример**

Alphabet: {[, ]}
Initial word: []
Production rules: 
(1)       $ → [$]
(2)       $ → $$
(3)       $1$2 → $1[]$2

Derivation of a few words in the language of well-formed bracket expressions:

       []             initial word
       [][]           by (2)
       [[][]]         by (1)
       [[][]][[][]]   by (2)
       [[][]][][[][]] by (3)
       ...

### Редукционные вычислительные системы

[**Редукционные вычислительные системы**](http://www.nsc.ru/win/elbib/data/show_page.dhtml?77+875) - системы, в которых вычисления инициируются на основе запроса на данные. В основе данной организации лежит представление вычислительного процесса в виде графа. Вершины графа обрабатываются снизу вверх, так как вершина запускается лишь когда требуется ее результат. Данный процесс называется редукцией графа, что и обусловило название системы редукционной.

В редукционной ВС вычисления производятся по запросу на результат операции. Предположим, что вычисляется выражение $a = (b+1)×c-d/c$. В случае потоковых моделей процесс начинается с самых внутренних операций, а именно с параллельного вычисления $(b+1)$ и $d/c$. Затем выполняется операция умножения $(b+1)×c$ и, наконец, самая внешняя операция - вычитание. Такой род вычислений часто называют энергичными вычислениями (*eager evaluation*).

При вычислениях, управляемых запросами, все начинается с запроса на результат $a$, который включает в себя запрос на вычисление выражений $(b+1)×c$ и $d/c$, а те, в свою очередь, формируют запрос на вычисление $b+1$, то есть на операцию самого внутреннего уровня. Результат возвращается в порядке, обратном поступлению запросов. Отсюда название ленивые вычисления (*lazy evaluation*), поскольку операции выполняются только тогда, когда их результат требуется другой операции. Редукционные вычисления естественно согласуются с концепцией функционального программирования, упрощающей распараллеливание программ.

Известны два типа моделей редукционных систем: **строчная** и **графовая**, отличающиеся тем, что именно передается в операцию (функцию) - скопированные значения данных или же только указатели мест хранения данных.

В **строчной** редукционной модели каждая запросившая вершина получает отдельную копию выражения для собственной оценки. Длинное строковое выражение рекурсивным образом сокращается (редуцируется) до единственного значения. Каждый шаг редукции содержит операцию, сопровождаемую ссылкой на требуемые входные операнды. Операция приостанавливается, пока оцениваются входные параметры. Программа редукции состоит из распознавания редексов с последующей заменой их вычисленными значениями. Таким образом, вся программа в конечном итоге редуцируется до результата.

В **графовой** редукционной модели выражение представлено как ориентированный граф. Граф сокращается по результатам оценки ветвей и подграфов. В зависимости от запросов возможно параллельное оценивание и редукция различных частей графа или подграфов. Запросившему узлу, который управляет всеми ссылками на граф, возвращается указатель на результат редукции. «Обход» графа и изменение ссылок продолжаются, пока не будет получено значение результата, копия которого возвращается запросившей команде.

---

## 7. Классификационные системы: иерархические классификации, фасетные классификации, алфавитно-предметные классификации. Тезаурусные методы представления знаний.

### Классификация

Отношение между объектом и множеством, обозначающим, что объект принадлежит этому множеству, называется **отношением классификации (ISA)**. Говорят, что множество (класс) классифицирует свои экземпляры. (пример: *«Шарик является собакой» = Шарик является объектом типа собака*). Иногда это отношение именуют также MemberOf, InstanceOf или подобным образом. Связь ISA предполагает, что свойства объекта наследуются от множества. Обратное к ISA отношение используется для обозначения примеров, поэтому так и называется — «Example», или по-русски «Пример». **Иерархические** отношения образуют древовидную структуру.

### Фасетная классификация

[**Фасетная классификация**](https://ru.wikipedia.org/wiki/Фасетная_классификация) (классификация двоеточием, классификация Ранганатана) — это совокупность нескольких независимых классификаций, осуществляемых одновременно по различным основаниям, в которой:

* понятия представлены в виде пересечения ряда признаков;
* классификационные индексы синтезируются посредством комбинирования фасетных признаков в соответствии с фасетной формулой.

Говоря языком теории множеств, фасетная классификация — множество, элементами которого являются множества.

**Пример:**

Классификация фильмов:

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

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

### Алфавитно-предметные классификации

[**Алфавитно-предметные**](https://studopedia.ru/6_11438_alfavitno-predmetnie-klassifikatsii.html) классификации, также как и фасетные, основываются на предварительном составлении перечня основных категорий и классов предметов, встречающихся в конкретной предметной области.

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

**Пример:** фрагмент предметных рубрик:

Очистные работы – Учет

Очистные сооружения

Очистные сооружения – Гидробиология

Очистные сооружения – Железобетонные конструкции – Защита от коррозии

Очистные сооружения – Иловые площадки – Проектирование

...

### Тезаурус

[**Теза́урус**](https://ru.wikipedia.org/wiki/Тезаурус) (от греч. θησαυρός «сокровище»), в общем смысле — специальная терминология, более строго и предметно — словарь, собрание сведений, корпус или свод, полномерно охватывающие понятия, определения и термины специальной области знаний или сферы деятельности, что должно способствовать правильной лексической, корпоративной коммуникации (пониманию в общении и взаимодействии лиц, связанных одной дисциплиной или профессией); в современной лингвистике — особая разновидность словарей, в которых указаны семантические отношения (синонимы, антонимы, паронимы, гипонимы, гиперонимы и т. п.) между лексическими единицами. Тезаурусы являются одним из действенных инструментов для описания отдельных предметных областей.

**Тезаурусные методы представления знаний**
[*Источник*](https://www.it-claim.ru/Library/Books/Semantics_IT/gl1_1/glava1_1.htm)
Формализацию знаний путем именования предметов и отношений между ними словами-понятиями естественного языка называют тезаурусным описанием, а результаты такого описания — тезаурусами.

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

В связи с тем, что тезаурус представляет собой систему связанных между собой понятий, являющихся образами предметной области реального мира, его можно назвать *“понятийной картиной мира”*. Если считать, что в самом общем случае любое слово естественного языка может быть соотнесено (связано отношением) с любым другим словом, то тезаурус можно назвать *“языковой картиной мира”*.

Информационная технология тезаурусного описания в общем случае включает процедуры формирования списков слов-понятий (слов-отношений) и группировки их в парадигматические классы.

**Не помешают примеры!**

---

## 8. Основные методы распознавания образов.

### Формальная постановка задачи

[Полезная книга](https://books.ifmo.ru/file/pdf/1798.pdf)

[**Распознавание образов**](https://ru.wikipedia.org/wiki/Теория_распознавания_образов) — это отнесение исходных данных к определенному классу с помощью выделения существенных признаков, характеризующих эти данные, из общей массы несущественных данных.

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

### В целом, можно выделить следующие методы распознавания образов:
[Источник](https://ru.bmstu.wiki/Распознавание_образов)
* **Метод перебора.** В этом случае производится сравнение с базой данных, где для каждого вида объектов представлены всевозможные модификации отображения. Например, для оптического распознавания образов можно применить метод перебора вида объекта под различными углами, масштабами, смещениями, деформациями и т. д. Для букв нужно перебирать шрифт, свойства шрифта и т. д. В случае распознавания звуковых образов, соответственно, происходит сравнение с некоторыми известными шаблонами (например, слово, произнесенное несколькими людьми).
* Второй подход - производится **более глубокий анализ характеристик образа.** В случае оптического распознавания это может быть определение различных геометрических характеристик. Звуковой образец в этом случае подвергается частотному, амплитудному анализу и т. д.
* Следующий метод - **использование искусственных нейронных сетей** (ИНС). Этот метод требует либо большого количества примеров задачи распознавания при обучении, либо специальной структуры нейронной сети, учитывающей специфику данной задачи. Тем не менее, его отличает более высокая эффективность и производительность.
* **Экспертный метод**, основанный на знаниях о распознаваемом объекте.

### Примеры задач распознавания образов:

* pаспознавание букв;
* pаспознавание штрих-кодов;
* pаспознавание автомобильных номеров;
* pаспознавание лиц и других биометрических данных;
* pаспознавание изображений;
* pаспознавание речи.

---

## 9. Предварительная обработка данных в задачах анализа: нормализация, стандартизация, обработка пропущенных значений. Способы получения репрезентативных выборок.

**Предварительная обработка данных** является важным шагом в процессе интеллектуального анализа данных. Фраза «мусор на входе -- мусор на выходе» применима, в частности, и для проектов интеллектуального анализа данных и машинного обучения.

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

### Нормализация

Нормализация данных используется для стандартизации диапазона значений независимых переменных или признаков данных (сведение к интервалам $[0, 1]$ или $[-1, +1]$).

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

Будучи разными по физическому смыслу, данные сильно различаются между собой по абсолютным величинам. Работа аналитических моделей машинного обучения с такими показателями может оказаться некорректной: дисбаланс между значениями признаков может вызвать неустойчивость работы модели, ухудшить результаты обучения и замедлить процесс моделирования. Например популярный метод ближайших соседей, часто используемый в задачах классификации и кластеризации, чувствителен к диапазону изменений входных переменных.

Наиболее популярна **минмакс нормализация**, задаваемая соотношением:
$$
X_{norm} = \frac{X - X_{min}}{X_{max} - X_{min}}
$$

### Стандартизация

В процессе стандартизации происходит формирование стандартизированных шкал. Стандартизация позволяет устранить возможное влияние отклонений по какому-либо признаку. Стандартизация приводит все исходные значения набора данных, независимо от их начальных распределений и единиц измерения, к набору значений из распределения с нулевым средним и стандартным отклонением, равным 1. В результате формируется так называемая стандартизированная шкала, которая определяет место каждого значения в наборе данных, измеряя его отклонение от среднего в единицах стандартного отклонения. Значения стандартизированной шкалы определяются следующим образом:
$$
z_i = \frac{x_i - \overline{x}}{\sigma_x}
$$

### Обработка пропущенных значений
Часто в данных, с которыми необходимо работать, присутствуют пропуски, при этом доступны следующие варианты: игнорировать, отбросить или же заполнить пропущенные значения. Заполнение пропусков зачастую и вполне обоснованно кажется более предпочтительным решением. Однако это не всегда так. Неудачный выбор метода заполнения пропусков может не только не улучшить, но и сильно ухудшить результаты.

Наиболее популярные методы заполнения пропущенных значений:
* заполнение пропусков нулями;
* заполнение медианой;
* заполнение средним арифметическим значением;
* введение индикаторных переменных и тому подобное.

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

**[Тут](https://loginom.ru/blog/missing) есть больше, но не думаю, что это нужно.**

### Способы получения репрезентативных выборок

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

[Источник](https://studopedia.ru/9_165355_est-neskolko-metodov-formirovaniya-reprezentativnoy-viborki.html)
1. **Простая случайная выборка** каждому элементу популяции соответствует заданная и одинаковая вероятность отбора.
2. **Систематическая выборка** заключатся в том, что выборка формируется путем выбора случайным образом начальной точки затем последовательно отбора каждого i-элемента схемы выборки. Частота отбора элементов, i, называется интервалом выборки. Он вычисляется путем деления размера популяции N на размер выборки n и округления полученного значения до ближайшего целого. Элементы популяции, используемые при систематической выборке, обычно определенным образом организованы.
3. **Стратифицированная выборка** представляет собой процесс выборки, состоящий их двух этапов. Во-первых, популяция делится на подгруппы, называемые стратами. Каждый элемент популяции должен быть отнесен к одной и только одной страте, и ни один из элементов не должен быть пропущен. Во-вторых, элементы из каждой страты должны быть отобраны случайным образом. Идеальным вариантом является использование метода простой случайной выборки для отбора элементов в каждой страте.
4. **Кластерная выборка** целевую популяцию сначала делят на взаимно исключающие и совокупно исчерпывающие субпопоуляции, по-другому – кластеры. Затем с помощью вероятностного метода выборки, такого как простая случайная выборка, формируется произвольная выборка из кластеров. **В чем разница со стратифицированной?**

Также для репрезентативности выборки важен ее размер. Больше -- лучше.

---

## :question: 10. Задачи классификации: общая постановка, виды, обзор методов решения, возможные приложения.

### Определение

[**Задача классифика́ции**](https://ru.wikipedia.org/wiki/Задача_классификации) — задача, в которой имеется множество *объектов* (ситуаций), разделённых некоторым образом на *классы*. Задано конечное множество объектов, для которых известно, к каким классам они относятся. Это множество называется *выборкой*. Классовая принадлежность остальных объектов неизвестна. Требуется построить алгоритм, способный *классифицировать* (см. ниже) произвольный объект из исходного множества.

**Классифици́ровать объект** — значит, указать номер (или наименование) класса, к которому относится данный объект.

### Математическая постановка задачи

$X$ — **множество объектов** (входное множество)
$Y$ — **множество ответов (классов)** (выходное множество)

$\exists \; y(x): X \to Y$ — неизвестная **целевая функция** (зависимость).

Дана **обучающая выборка** $T^m$, состоящая из **тренировочного множества** $\{x_1, x_2,\ \ldots,\ x_m\} \subset X$, для которого указаны **известные значения** функции $y_i = y(x_i)$.

Необходимо найти **функцию выбора решения** $a(x): X \to Y$, которая аппроксимирует $y(x)$ на $X$.

### Описание объектов

**Признак** (атрибут) объекта — отображение $f(x): X \to D_f$.

Каждый объект обучающей выборки $x_i \in X$ имеет некоторый набор признаков $\left(f_1(x_i),\ \ldots,\ f_n(x_i)\right)$, который называют **признаковым описанием** объекта. Признаковые описания допустимо отождествлять с самими объектами.

Множество $D = D_{f_1} \times \ldots \times D_{f_n}$ называется **признаковым пространством**.

Данные обычно представлены как **матрица объектов–признаков**:

$F = \lVert f_j(x_i) \rVert = \begin{pmatrix}
f_1(x_1) & \ldots & f_n(x_1) \\
\ldots & \ldots & \ldots \\
f_1(x_m) & \ldots & f_n(x_m)
\end{pmatrix}$

**Типы признаков**
- Бинарные: $D_f = \{0, 1\}$
- Категориальные: $D_f$ — конечное множество
- Упорядоченные: $D_f$ — конечное упорядоченное множество
- Численные: $D_f = \mathbb{R}$

### Виды задач классификации
- Бинарная: $Y = \{-1, +1\}$
- Непересекающиеся классы (multi-class): $Y = \{1,\ \ldots,\ M\}$
- Пересекающиеся классы (multi-label): $Y = \{0, 1\}^M$

### Выбор алгоритма

**Модель алгоритмов** — параметрическое семейство функций $A = \{f(x, \theta)\ |\ \theta \in \Theta\}$, в рамках которого ищется функция, приближающая целевую зависимость. Здесь $\Theta$ — множество допустимых значений параметра $\theta$ некоторой зафиксированной функции $f: X \times \Theta \to Y$.

Пример: **линейная модель** с вектором параметров $\theta = (\theta_1,\ \ldots,\ \theta_n), \Theta = \mathbb{R}^n$

**Метод обучения** — отображение $\mu: (X \times Y)^m \to A$, которое по обучающей выборке данных $T^m = \{(x_i, y_i)\}$ строит алгоритм $a \in A$, восстанавливающий неизвестную зависимость ответов от объектов.

Два шага:
1. **Обучение**: с помощью метода $\mu$ по обучающей выборке $T^m$ построить алгоритм $a = \mu(T^m)$
2. **Тестирование**: применить $a$ к новым объектам $x_j$ и проверить "качество" ответов $a(x_j)$.

### Обзор методов решения
* Основанные на построении решающего правила.
Например, **дерево решений** -- наиболее интуитивно понятный подход, заключающийся в построении на основе обучающей выборки решающего правила в виде дерева из конструкций "если ..., то ...". Тут же рандом форест.
* Основанные на апроксимации вероятности принадлежности объекта к тому или иному классу.
Например, **логистическая регрессия** -- применяется для прогнозирования вероятности принадлежности объекта классу 0 или 1.
Делается предположение о том, что вероятность наступления события $y=1$ равна: $$\mathbb {P} \{y=1\mid x\}=f(z),$$ где ${z=\theta ^{T}x}$, $x$ и $\theta$ — векторы-столбцы значений независимых переменных ${1,x_{1},\dots ,x_{n}}$ и параметров (коэффициентов регрессии) -- вещественных чисел $\theta _{0},...,\theta _{n}$, соответственно, а $f(z)$ — так называемая логистическая функция:$$f(z)={\frac {1}{1+e^{{-z}}}}.$$
Для подбора параметров обычно используется метод максимального правдоподобия, согласно которому выбираются параметры $\theta$ , максимизирующие значение логарифма функции правдоподобия на обучающей выборке:
$$\ln L(\theta )=\sum _{i=1}^{m}\log \mathbb {P} \{y=y^{(i)}\mid x=x^{(i)}\}=\sum _{i=1}^{m}y^{(i)}\ln f(\theta ^{T}x^{(i)})+(1-y^{(i)})\ln(1-f(\theta ^{T}x^{(i)})),$$ Для максимизации этой функции может быть применён, например, метод градиентного спуска. Тут же классификаторы на нейросетях.

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

### Возможные приложения ([см. у Воронцова ](http://www.machinelearning.ru/wiki/images/6/6d/Voron-ML-1.pdf#subsubsection.1.2.1))
- Медицинская диагностика;
- Кредитный скоринг;
- Предсказание ухода клиентов (Сhurn prediction).

---
## 11. Языки и модели человеко-машинного взаимодействия.

## 12. Методы и модели распознавания и понимания речи.

### Скрытые марковские модели

### DTW

### Нейронные сети

---

## 13. Методы синтеза речи и изображений.

### [Синтез речи](https://habr.com/ru/company/tinkoff/blog/474782/)

Эту задачу сегодня решают двумя подходами:

* **Unit selection**, или **конкатенативный (компилятивный) подход**. Он основан на склейке фрагментов записанного аудио. С конца 90-х долгое время он считался де-факто стандартом для разработки движков синтеза речи. Например, голос, звучащий по методу unit selection, можно было встретить в Siri.
* **Параметрический синтез речи**, суть которого состоит в построении вероятностной модели, предсказывающей акустические свойства аудиосигнала для данного текста.

**Unit selection**

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

Весь процесс генерации состоит из двух этапов: NLP frontend, отвечающий за извлечение лингвистического представления текста, и backend, который вычисляет функцию штрафа юнитов для заданных лингвистических признаков.

В NLP frontend входят:
* Задача нормализации текста — перевод всех небуквенных символов (цифр, знаков процентов, валют и так далее) в их словесное представление. Например, “5 %” должно быть переведено в “пять процентов”.
* Извлечение лингвистических признаков из нормализованного текста: фонемное представление, ударения, части речи и так далее.

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

Штраф, оцениваемый backend-подсистемой, — это сумма target cost, или соответствия акустического представления юнита для конкретной фонемы, и concatenation cost, то есть уместности соединения двух соседних юнитов. Для оценки штраф функций можно использовать правила или уже обученную акустическую модель параметрического синтеза. Выбор наиболее оптимальной последовательности юнитов с точки зрения выше определенных штрафов происходит с помощью алгоритма [Витерби](https://ru.wikipedia.org/wiki/Алгоритм_Витерби).

**Достоинства** подхода unit selection:
* Естественность звучания.
* Высокая скорость генерации.
* Небольшой размер моделей — это позволяет использовать синтез прямо на мобильном устройстве.

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

**Параметрический синтез речи**

В основе параметрического подхода лежит идея о построении вероятностной модели, оценивающей распределение акустических признаков заданного текста.
Процесс генерации речи в параметрическом синтезе можно разделить на четыре этапа:
1. NLP frontend — такая же стадия предобработки данных, как и в подходе unit selection, результат которой — большое количество контекстно-зависимых лингвистических признаков.
2. Duration model, предсказывающая длительность фонем.
3. Акустическая модель, восстанавливающая распределение акустических признаков по лингвистическим. В акустические признаки входят значения фундаментальной частоты, спектральное представление сигнала и так далее.
4. Вокодер, переводящий акустические признаки в звуковую волну.

Для обучения duration и акустической моделей можно использовать [скрытые марковские модели](https://ru.wikipedia.org/wiki/Скрытая_марковская_модель), глубокие нейронные сети или их рекуррентные разновидности. Традиционный [вокодер](https://ru.wikipedia.org/wiki/Вокодер) -- это алгоритм, основанный на source-filter модели, которая предполагает, что речь -- это результат применения линейного фильтра шума к первоначальному сигналу.

Общее качество речи классических параметрических методов оказывается достаточно низким из-за большого количества независимых предположений об устройстве процесса генерации звука. Однако с приходом технологий глубокого обучения стало возможным обучать end-to-end модели, которые напрямую предсказывают акустические признаки по буквам. Например, нейронные сети Tacotron и Tacotron 2 принимают на вход последовательность букв и возвращают мел-спектрограмму с помощью алгоритма seq2seq. Таким образом шаги 1—3 классического подхода заменяются одной нейросетью.

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

**Достоинства** параметрического синтеза:
* Естественное и плавное звучание при использовании end-to-end подхода.
* Большее разнообразие в интонациях.
* Использование меньшего объема данных по сравнению с моделями unit selection.

**Недостатки**:
* Низкая скорость работы по сравнению с unit selection.
* Большая вычислительная сложность.

### Синтез изображений

Наиболе популярные методы:

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


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

[**Вариационный автоэнкодер (VAE)**](https://neurohive.io/ru/osnovy-data-science/variacionnyj-avtojenkoder-vae/) имеет одно уникальное свойство, которое отличает его от стандартного автоэнкодера. Его энкодер выдаёт не один вектор размера $n$, а два вектора размера $n$ – вектор средних значений $\mu$ и вектор стандартных отклонений $\sigma$.


Вариационные автоэнкодеры формируют параметры вектора длины $n$ из случайных величин $X_i$, причем $i$-е элементы векторов $\mu$ и $\sigma$ являются средним и стандартным отклонением $i$-й случайной величины $X_i$. Вместе эти величины образуют $n$-мерный случайный вектор, который посылается на декодер для восстановления данных. Эта так называемая стохастическая генерация означает, что даже для одинаковых входных данных результат кодирования будет разным вследствие случайности выбора вектора кодирования

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

**Генеративно-состязательные сети (GAN)**
GAN состоит из двух сетей:
* Генератор, способный генерировать изображения по входному вектору шума.
* Дискриминатор, который различает настоящую картину и "поддельную" (сгенерированную генератором).


Процесс обучения GAN выглядит следующим образом:
1. Берется n семплов из датасета и m семплов от генератора.
2. Фиксируем веса генератора и делаем апдейт параметрам дискриминатора. Это обычная задача классификации. Только необходимости тренировать дискриминатор до сходимости у нас нет. А даже больше зачастую это еще и мешает.
3. Фиксируем веса дискриминатора и делаем апдейт весам генератора, так чтобы дискриминатор начинал думать что наши семплы из датасета а не от генератора.
4. Повторяем 1-3, пока дискриминатор и генератор не придут в равновесие (т.е ни один ни другой не может «обмануть» другого).

**Авторегрессионные модели**
Авторегрессионные модели, такие как [PixelRNN](https://arxiv.org/abs/1601.06759), учат сеть моделировать условное распределение каждого отдельного пикселя с учетом предыдущих пикселей (по направлению влево и вверх). Этот процесс аналогичен включению пикселей изображения в многослойную рекуррентную сеть, но рекуррентные нейрсети (RNN) работают с изображением не в одном направлении, а в двух — по горизонтали и по вертикали. PixelRNNs отличаются довольно простым и стабильным процессом обучения.

---
## 14. Методы и алгоритмы анализа текста, извлечения данных из текстов на естественном языке. Тематическое моделирование.

See: https://hackmd.io/@Ft40NUWlSTyVND99rGGlzA/S1Mp8TSZv/edit

*Релевантное из билетов прошлых лет* [https://yadi.sk/d/71ODtdt74E3abg](https://yadi.sk/d/71ODtdt74E3abg)