Вопросы к экзамену

Вопросы к экзамену по курсу«Математические основы теории прогнозирования» 2011Вопросы по части Ветрова Д.П.1. Различные постановки задач машинного обучения (классификация, регрессия,кластеризация, идентификация, прогнозирование, поиск закономерностей). Основныепроблемы в теории машинного обучения: переобучение, некорректность данных, малыйобъем обучающей информации.2.

Метод максимального правдоподобия. Его достоинства и недостатки. Нормальноераспределение (одномерное и многомерное), его основные свойства.3. Решение задач условной оптимизации. Правило множителей Лагранжа. Двойственнаязадача. Выпуклый вариант теоремы Куна-Таккера.4. Задача восстановления линейной регрессии. Метод наименьших квадратов. Решениенесовместных СЛАУ.5. Задача восстановления линейной регрессии. Вероятностная формулировка методанаименьших квадратов.6.

Логистическая регрессия. ВероятностнаяИтеративный метод наименьших квадратов.постановка.Регуляризацияобучения.7. Метод опорных векторов. Прямая задача оптимизации, ее свойства.8. Метод опорных векторов. Двойственная задачи оптимизации. Ядровой переход.9. Скрытые марковские модели. Обучение СММ с учителем.10. Алгоритм динамического программирования и его применение в скрытых марковскихмоделях.11. ЕМ-алгоритм и его применение для задачи разделения гауссовской смеси.12. Проблема уменьшения размерности в описании данных. Формулировка метода главныхкомпонент через критерий минимизации ошибки проектирования.13. Формулировка метода главных компонент через критерий максимизации разбросав данных.

Решение задачи идентификации. Выбор размерности редуцированногопространства.14. Метод главных компонент в ситуации, когда число признаков превышает число объектов.Ядровой метод главных компонент.1Вопросы по части Журавлева Ю.И.1. В алгоритмах вычисления оценок объекты задаются наборами значений n числовыхпризнаков. В таблице обучения 2 непересекающихся класса K1 = {S1 , . . . , Sm } и K2 =0{S10 , . . . , Sm}. Опорными являются все подмножества из k элементов, k < n.

Функцияблизости определяется параметрами ε1 , . . . , εn и равна 1 тогда и только тогда, когдавыполнены все соответствующие неравенства. Веса всех признаков и всех объектов равны1. При вычислении Γj (S), j = 1, 2 учитывается только близость с коэффициентом 1 кобъектам из своего класса. Написать формулы для Γ1 (S) и Γ2 (S).2. В алгоритмах вычисления оценок объекты задаются наборами значений n числовыхпризнаков. В таблице обучения 2 непересекающихся класса K1 = {S1 , .

. . , Sm } и K2 ={S10 , . . . , Sl0 }. Характеристические векторы опорных множеств образуют конъюнкцию x1 ·· · · · xr · x̄r+1 · · · · · x̄t , t < n. Функция близости определяется параметрами ε1 , . . . , εn иравна 1 тогда и только тогда, когда выполнены все соответствующие неравенства. Весавсех признаков и всех объектов равны 1. При вычислении Γj (S), j = 1, 2 учитываетсяс коэффициентом 1 только отсутствие близости к объектам чужого класса. Написатьформулы для Γ1 (S) и Γ2 (S).3.

Даны два объекта S1 = (a1 , . . . , an ) и S2 = (b1 , . . . , bn ). Метрики в множествах значенийпризнаков ρ1 , . . . , ρn . Параметры, определяющие близость: ε1 , . . . , εn . Неравенство t:ρt (at , bt ) ≤ εt . k – целочисленный параметр. Пусть M = (q1 , .

. . , ql ), l > k. Функцияблизости N (S1 , S2 , M ) = 1 тогда и только тогда, когда из неравенств ρq1 (aq1 , bq1 ) ≤εq1 , . . . , ρql (aql , bql ) ≤ εql не выполнено не более k. Для скольких множеств M , состоящихне менее, чем из k + 1 элемента, функция близости равна 1?4. Дана таблица обученияS1 = (1, 1, 0, 1, 1, 0, . . . , 1, 1, 0, 1, 1, 0)S2 = (0, 0, 1, 0, 0, 1, . .

. , 0, 0, 1, 0, 0, 1)S3 = (0, 0, 1, 1, 1, 0, . . . , 0, 0, 1, 1, 1, 0)S4 = (1, 1, 0, 0, 0, 1, . . . , 1, 1, 0, 0, 0, 1)¾K1 ,¾K2 ,Распознаваемый объектS = (0, 0, 1, 0, 0, 1, 1, 1, 0, 1, 1, 0, . . . , 0, 0, 1, 0, 0, 1, 1, 1, 0, 1, 1, 0).В какой класс будет отнесен объект S тестовым алгоритмом, если все тесты равноценныи совпадение хотя бы с одной строкой тупикового теста дает классу один голос?5. Дана таблица обучения c 3m признаками:S1 = (1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0, .

. . , 1, 1, 1, 0, 0, 0)S2 = (0, 0, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, . . . , 0, 0, 0, 1, 1, 1)S3 = (0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, . . . , 0, 0, 0, 0, 0, 0)S4 = (1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, . . . , 1, 1, 1, 1, 1, 1)В алгоритме вычисления оценок:(a) {Ω}A = {(1, 2, 3), (4, 5, 6), . . .

, (3m − 2, 3m − 1, 3m)}.2¾K1 ,¾K2 ,(b) Функция близости задается параметрами ε1 , . . . , ε2n и равна 1 тогда и только тогда,когда все 3 соответствующих неравенства выполнены.(c) wi = 1, i = 1, . . . , 2n. Веса объектов w1 , . . . , w4 не заданы.(d) Значения параметров x00 , x11 , x01 , x10 не заданы.(e) Решающее правило Γj (S) > 2, S ∈ Kj , Γj (S) < 1, S ∈/ Kj .Можно ли подобрать значения параметров w1 , . . .

, w4 , x00 , x10 , x01 , x11 таким образом,чтобы объект (0, 0, . . . , 0) относился к классу K2 и не относился к классу K1 , а объект(1, 1, . . . , 1) относился к классу K1 и не относился к классу K2 ?6. Пусть Si = (a1 , . . . , an ) – объект из таблицы обучения, S = (b1 , . . . , bn ) – распознаваемыйобъект. ρ1 , .

. . , ρn – метрики для признаков. Функция близости определяется параметрамиε1 , . . . , εn , q и равна 1 тогда и только тогда, когда из соответствующих неравенств невыполнено не более q. Для скольких подножеств, содержащих признак j, функцияблизости равна 0, если(a) совокупность опорных множеств состоит из всех k элементных подмножеств, n > k >q (сравниваются объекты Si и S),(b) совокупность опорных множеств состоит из всех непустых подмножеств мощностине меньшей 2q + 1?7.

Пусть таблица обучения и ее информационная матрица имеют видS1S2S3S4= (1, 0, 0, 1, 1, 0, 0, 1, . . . , 1, 0, 0, 1)= (0, 1, 1, 0, 0, 1, 1, 0, . . . , 0, 1, 1, 0)= (1, 0, 1, 0, 1, 0, 1, 0, . . . , 1, 0, 1, 0)= (0, 1, 0, 1, 0, 1, 0, 1, . . . , 0, 1, 0, 1)K11 1 00K200 1 1Контрольная матрицаS10 = (1, 1, 1, . . . , 1, 1)S20 = (0, 0, 0, . .

. , 0, 0)µK110K2¶01Найти алгоритмы вычисления оценок, отмечающие единицы информационной матрицыконтроля, и построить корректный для контрольной матрицы алгоритм в алгебраическомзамыкании.8. В материале обучения представлены объекты двух непересекающихся классов K1 , K2 .Объекты – бинарные векторы размерности n. В K1 включены все объекты, содержащиеm единиц и n − m нулей, в K2 – все объекты, содержащие l единиц и n − l нулей,m > 1, m > l, m < n. Рассматриваются алгоритмы вычисления оценок, у которых{Ω}A состоит из всех k элементных подмножеств множества {1, . .

. , n}, функция близостиопределяется параметрами εi = 0, i = 1, . . . , n и равна 1 тогда и только тогда, когдавыполнены все соответствующие неравенства, wi = 1, ∀i, x11 = 1, x00 = x01 = x10 = 0,wi = 1, Si ∈ K1 . Найти значения весов объектов из класса K2 так, чтобы объект (1, 1, . . . , 1)получил большую оценку за класс K2 .39. Объекты из класса K1 образуют Хеммингов шар радиуса r1 с центром в точке (0, . .

. , 0),объекты класса K2 образуют Хеммингов шар радиуса r2 с центром в точке (1, . . . , 1).Объект S состоит из q единиц и n − q нулей. Рассматриваются все опорные множества изk элементов. Функция близости определяется параметрами ε1 = · · · = εn = 0. При какихусловиях объект S будет близок к классу K1 по большему числу подмножеств (числослучаев, когда функция близости равна 1, суммируемых по всем опорным подмножествами всем элементам из обучающей выборки, принадлежащим соответствующему классу)?10. Пусть заданы параметры ε1 , .

. . , εn и для двух объектов S = (a1 , . . . , an ), S 0 = (b1 , . . . , bn ) изn неравенств ρ1 (a1 , b1 ) ≤ ε1 , . . . , ρn (an , bn ) ≤ εn выполнено m неравенств. Рассмотрим всеподмножества номеров координат, составленные не менее, чем из k элементов, содержащиекоординату с фиксированным номером i. Функция близости равна 1, если не выполненоне более t неравенств, t < k. Найти число указанных выше подмножеств, для которыхфункция близости в этом случае равна 1.11. Дана таблица обучения2kz}|{ z2n−2k}|{S1 = (1, 1, . . . , 1, 1, 0, 0, .

. . , 0)S2 = (0, 0, . . . , 0, 0, 1, 1, . . . , 1)S3 = (1, 1, . . . , 1, 1, 1, 1, . . . , 1)S4 = (0, 0, . . . , 0, 0, 0, 0, . . . , 0)¾K1 ,¾K2 ,В алгоритме вычисления оценок:(a) {Ω}A – все непустые подмножества из 4-х элементов.(b) Функция близости задается параметрами ε1 = · · · = ε2n = 0 и равна 1 тогда и толькотогда, когда все 4 соответствующих неравенства выполнены.(c) Веса объектов wi = 1, i = 1, .

. . , 4. Веса признаков w2k = 1, w2k−1 = 2, k = 1, . . . , n.(d) x11 = 2, x00 = 1, x01 = x10 = −1.Найти оценки за классы K1 , K2 для объектовS10 = (1, 0, 1, 0, . . . , 1, 0),S20 = (0, 1, 0, 1, . . . , 0, 1).12. Пусть таблица обучения с 2k признаками и ее информационная матрица имеют видkS1S2S3S4====kz }| { z }| {(1, 1, . . . , 1, 1, . . . , 1)(0, 0, .

. . , 0, 0, . . . , 0)(1, 1, . . . , 1, 0, . . . , 0)(0, 0, . . . , 0, 1, . . . , 1)K11 1 00K200 1 1Контрольная матрицаS10S20= (1, 0, 1, 0, . . . , 1, 0)= (0, 1, 0, 1, . . . , 0, 1)В алгоритме вычисления оценок:4µK110K2¶01(a) {Ω}A – все опорные множества из 4-х элементов.(b) Функция близости определяется параметрами ε1 = · · · = εn = 0 и равна 1 тогда итолько тогда, когда все соответствующие неравенства выполнены.(c) w1 = · · · = w2k = 1, x11 = 1, x10 = x01 = x00 = 0.Найти значения весов объектов, при которых оператор алгоритма отмечает обе единицыв информационной матрице контрольной выборки.13.

Доказать критерий поглощения. Рассмотрим включениеNK ⊆m[NKi ,i=1где K, Ki – элементарные конъюнкции, NK , NKi – интервалы (множество единиц¡¢σсоответствующей конъюнкции). Пусть дано преобразование π : xi → xj ij , ji –перестановка, σij ∈ {0, 1}. Доказать, что условие выше выполнено тогда и только тогда,когдаm[Nπ(K) ⊆Nπ(Ki ) .i=1Используя критерий поглощения, упростить выражениеx1 x̄2 ∨ x̄1 x2 ∨ x1 x̄3 ∨ x̄1 x3 ∨ x2 x̄3 ∨ x̄2 x3 .14. Доказать теорему о построении корректного алгоритма, если все единичные координатыконтрольной матрицы были отмечены операторами вычисления оценок B1 , . .

. , BK .Построить оператор, отмечающий единичные элементы матрицы1 0 00 0 1  ,0 1 0если операторы B1 , B2 , B3 построили матрицы1 0.4 0.41 1.50.5 1.5 1  , 1.5 1.50.4 111.5 15оценок1.51.5 1.5 1.51  , 1.4 0.4 1.5 .0.41.5 1.5 1.7.