Задачи

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

б) Покажите, что проекция вектора х на гиперплоскость задается выражением

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

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

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

4. Говорят, что множество выборок является попарно линейно разделяемым, если существуют с гиперплоскостей таких, что отделяет выборки, помеченные от выборок, помеченных Покажите, что множество попарно линейно разделяемых образов может не быть линейно разделяемым. (Указание: найдите такие конфигурации выборок, для которых границы области решений являются такими, как на рис. 5.26.)

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

в. Пусть — конечное множество линейно разделяемых выборок, а — вектор решения, если для всех i. Покажите, что вектор решения минимальной длины есть единичный вектор. (Указание: рассмотрите эффект усреднения двух векторов решения.)

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

где коэффициенты а - неотрицательны и сумма их равна 1. Заданы два множества векторов. Покажите, что либо они линейно разделяемы, либо их выпуклые оболочки пересекаются. (Указание: допустив справедливость обоих утверждений, рассмотрите классификацию точки пересечения выпуклых оболочек.)

8. Говорят, что классификатор является кусочно линейной машиной, если его разделяющие функции имеют вид

где

а) Укажите, каким образом кусочно линейная машина может быть описана как линейная для классификации подклассов образов.

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

9. Пусть d компонент х равны либо 0, либо 1. Допустим, что мы относим если число ненулевых компонент х нечетно, и к — в противном случае. (В теории переключения это называется функцией четности.)

а) Покажите, что такая дихотомия не является линейно разделяемой, если

б) Покажите, что данная задача может быть решена с помощью кусочно линейной машины с весовыми векторами (см. задачу 8). (Указание: рассмотрите векторы вида

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

При каком значении а число достигает минимального значения для

11. Опираясь на доказательство сходимости, приведенное в п. 5.5.2, попытайтесь изменить его для того, чтобы доказать сходимость такой процедуры коррекций: задавшись произвольным начальным весовым вектором корректируем в соответствии с выражением

тогда и только тогда, когда а у не достигает допуска b, где ограничено неравенствами Что происходит в случае отрицательного ?

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

13. Рассмотрим функцию критерия

где — множество выборок, для которых Пусть — единственная выборка в . Покажите, что а матрица вторых частных производных определяется выражением Используя этот результат, покажите, что если в выражение (8) подставить оптимальное значение то алгоритм градиентного спуска примет вид

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

15. Обобщите результаты п. 5.8.3 для того, чтобы показать, что вектор а, который минимизирует функцию критерия

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

16. Рассмотрим функцию критерия и байесовскую разделяющую функцию

а) Покажите, что

б) Используя тот факт, что условное среднее значение равно покажите, что вектор а, минимизирующий одновременно доставляет минимум функционалу

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

Приняв покажите, почему указанная последовательность коэффициентов удовлетворяет соотношениям

18. Задача линейного программирования, сформулированная в п. 5.10.2, включала в себя минимизацию единственной искусственной переменной t при ограничениях и 0. Покажите, что результирующий весовой вектор минимизирует функцию критерия

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