2011 Контрольная работа Комментарии к контрольной работе (Сенько)

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

. , L}. Например, для изображений лиц людей классы могут быть связаны спигментацией волос: «шатен», «брюнет», «русый» и т.д. При этом предполагается,что 1) для каждого класса в наличии имеется значительная выборка данных дляобучения и 2) распознаваемые объекты обязательно принадлежат к одному из классов,которые были представлены в обучающей выборке.

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

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

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

При этом функцияпрогноза этой величины по значениям признаков объекта (функция регрессии) не обязанабыть непрерывной функцией.3. Много ошибок было допущено при решении задачи на поиск нормального псевдорешениясистемы линейных уравнений. Пусть дана система линейных уравнений в матричном виде:Ax = b.(1)Здесь матрица A не обязана быть квадратной. Решением системы (1) называетсявектор x: Ax = b. Решение системы не всегда существует. В том случае, когдарешения нет, рассматривают т.н. псевдорешение. Псевдорешением системы (1) называетсявектор xps = arg minx ∥Ax − b∥2 . Псевдорешение системы всегда существует, номожет быть не единственным.

В последнем случае рассматривают также нормальное(0.0175,0.0702)2.52+1-x1.51.15x+xx1=12=20.51-2x2=10-0.5-1-3-2(a)-1012(b)Рис. 1: Иллюстрация псевдорешения и нормального псевдорешения. В случае (a) —псевдорешение единственно, в случае (b) псевдорешений бесконечно много (красная линия) инормальное псевдорешение соответствует основанию перпендикуляра к прямой псевдорешений.псевдорешение — псевдорешение с минимальной нормой). Обозначим через Xps множествовсех псевдорешений системы (1).

Тогда нормальным псевдорешением системы (1)называется вектор xps.norm : ∥xps.norm ∥ = arg minx∈Xps ∥x∥.Рассмотрим методы поиска псевдорешений и нормальных псевдорешений. Легко показать(подробнее см. лекции), что множество псевдорешений Xps системы (1) совпадает смножеством решений системыAT Ax = AT b.(2)В том случае, если матрица AT A является вырожденной, то псевдорешений бесконечномного, и имеет смысл искать нормальное псевдорешение. Для этого можно найти общеерешение системы (2) (ненулевое частное решение плюс линейная комбинация векторовбазиса ядра матрицы AT A), а затем найти среди общих решений решение с минимальнойнормой. Другой способ поиска нормального псевдорешения:xps.norm = lim (AT A + λI)−1 AT b.λ→0+Матрица AT A + λI всегда невырождена для ∀λ > 0.Рассмотрим ситуацию, когда матрица A имеет размер 3 × 2, т.е.

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

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

Например, при восстановлении линейной регрессии полученная функциярегрессии должна проходить максимально близко ко всем точкам выборки (см. рис. 2a).Картинка, показанная на рис. 2b, говорит о том, что функция регрессии восстановленаневерно.34433221100-1-1-2-2-3-3-2-101234-3-3-2-10(a)1234(b)Рис. 2: Пример восстановления линейной регрессии по 4 точкам. В случае (а) регрессиявосстановлена верно, в случае (b) — неверно.Аналогично, при восстановлении оптимальной гиперплоскости проектирования в методеглавных компонент данная гиперплоскость должна проходить через центр масс выборкитак, чтобы точки выборки были максимально близки к данной гиперплоскости. На рис. 3показан пример корректного восстановления такой гиперплоскости (синей звездочкойобозначен центр масс выборки).6543210-1-2-3-3-2-1012345678Рис. 3: Пример корректного восстановления оптимальной гиперплоскости в методе главныхкомпонент.5.

В тестовом варианте в задаче на условную оптимизацию было только одно условие. Ввариантах контрольной работы условий было несколько, что привело к тому, что многиеневерно записали функцию Лагранжа и, как следствие, эквивалентную безусловнуюзадачу оптимизации. Кроме того, даже записав верную безусловную задачу оптимизации,многие побоялись приступить к ее решению ввиду нелинейности полученной системы.Поэтому здесь разбирается полное решение одной из предложенных задач на условнуюоптимизацию.Рассмотрим следующую задачу условной оптимизации:x1 x2 x3 → min,2x1 x2 + x2 x3 = 12,2x1 − x2 = 8.Запишем функцию ЛагранжаL(x1 , x2 , x3 , λ1 , λ2 ) = x1 x2 x3 + λ1 (2x1 x2 + x2 x3 − 12) + λ2 (2x1 − x2 − 8).Заметим, что в функции Лагранжа вводится свой коэффициент лагранжа λi для каждогоусловия. Приравнивая к нулю производные функции Лагранжа по x1 , x2 , x3 и добавляяограничения из исходной задачи, получаем эквивалентную исходной задаче безусловнуюзадачу оптимизации:∂L= x2 x3 + 2λ1 x2 + 2λ2 = 0,∂x1∂L= x1 x3 + λ1 (2x1 + x3 ) − λ2 = 0,∂x2∂L= x1 x2 + λ1 x2 = 0,∂x32x1 x2 + x2 x3 = 12,2x1 − x2 = 8.(3)(4)(5)(6)(7)Условие (5) эквивалентно тому, что либо x2 = 0, либо x1 = −λ1 .

Условие x2 = 0противоречит условию (6). Подставляя x1 = −λ1 в уравнение (4), получаем:−λ1 x3 + λ1 (−2λ1 + x3 ) − λ2 = −2λ21 − λ2 = 0 ⇒ λ2 = −2λ21 .Подставляя условия x1 = −λ1 и λ2 = −2λ21 в уравнения (3),(6),(7), получаем следующуюсистему уравнений:x2 x3 + 2λ1 x2 − 4λ21 = 0,− 2λ1 x2 + x2 x3 = 12,− 2λ1 − x2 = 8.Вычитая из первого уравнения второе, и выражая из третьего уравнения x2 через λ1 ,получаем следующее квадратное уравнение:3λ21 + 8λ1 − 3 = 0.Решая данное уравнение и переходя к решениям для x1 , x2 , x3 , получаем два решения,подозрительных на минимум исходной задачи:x1 = 3, x2 = −2, x3 = −12;12628x1 = − , x 2 = − , x 3 = − .3339Вычисляем значение целевой функции в обеих полученных точках и выбираем решение,доставляющее минимум целевой функции:fmin = −5612628, x 1 = − , x2 = − , x 3 = − .2733396.

Часто допускались ошибки при выписывании функции правдоподобия. Пусть вероятностьисхода i равна qi ∏и исход i наступил ровно Ni раз. Тогда функция правдоподобиязаписывается как i qiNi . При подсчете комбинаторных вероятностей многие забывалиучитывать число сочетаний Cnk . Например, вероятность решить от двух до трех задач из6 при вероятности решения каждой задачи q составляет C62 q 2 (1 − q)4 + C63 q 3 (1 − q)3 .7. При решении задач на поиск нормального псевдорешения и построения линейнойрегрессии в процессе вычислений обратной матрицы многие допускали ошибки.

Избежатьэтих ошибок можно с помощью простого мнемонического правила обращения матрицы2 × 2:[][]1d −ba b−1.A=,A =c dad − bc −c aТаким образом, при обращении матрицы 2×2 с точностью до определителя диагональныеэлементы меняются местами, а внедиагональные элементы меняют знаки..