Середовище реалізації завдання - MATLAB.
Модель -регулярізованной лінійної регресії
формулювання методу
Розглядається задача відновлення регресії. Є навчальна вибірка _n, t_n \> _ ^ N "/>, де _n \ in \ mathbb ^ D" /> - вектор ознак для об'єкта, а "/> - його регресійне значення. Завдання полягає в прогнозуванні регресійного значення" /> для нового об'єкта, представленого своїм вектором ознак _ "/>.
У лінійної регресії прогнозування здійснюється за допомогою лінійної функції:
де \ in \ mathbb ^ D "/> - деякі ваги. Налаштування ваг здійснюється шляхом мінімізації наступного регуляризоване критерію:
Тут - задається користувачем параметр регуляризації. Використання -регулярізаціі дозволяє, по-перше, знизити ймовірність перенавчання алгоритму, а по-друге, отримати т.зв. розріджений рішення. У розрідженому вирішенні частина компонент оптимального вектора ваг "/> дорівнює нулю. Нульові ваги для деяких ознак рівносильні їх виключення з моделі (визнання їх неінформативними).
двоїста задача
Розглянемо отримання двоїстої задачі оптимізації для задачі (1). Для цього розглянемо еквівалентну постановку даного завдання у вигляді завдання умовної оптимізації:
Далі можна показати, що двоїстої до даної задачі опуклою оптимізації буде наступна:
Тут під || _ "/> розуміється.
гладка завдання
Завдання опуклою негладкою оптимізації (1) можна еквівалентно представити у вигляді завдання гладкою умовної мінімізації:
формулювання завдання
- Вивести двоїсту задачу оптимізації (2); записати, як за рішенням двоїстої задачі (2) можна отримати рішення прямої задачі (1);
- Для завдання (2) запропонувати формулу обчислення допустимої двоїстої точки "/> по заданій прямій точці" />, на її основі записати верхню оцінку на зазор між рішеннями прямої задачі (1) і двоїстої задачі (2);
- Вивести необхідні формули для вирішення гладкою завдання навчання (3) за допомогою методу бар'єрних функцій; запропонувати свій спосіб ефективного вирішення відповідної СЛАР, необхідні для цього формули вставити в звіт;
- Реалізувати метод бар'єрних функцій для розв'язання задачі (3); в якості критерію зупину використовувати отриману верхню оцінку на зазор;
- Вивести необхідні формули для розв'язування задачі (2) за допомогою прямо-двоїстого методу внутрішньої точки; запропонувати свій спосіб ефективного вирішення обуреної ККТ-системи, необхідні для цього формули вставити в звіт;
- Реалізувати прямо-двоїстий метод внутрішньої точки для завдання (2); в якості критерію зупину використовувати норму правій частині обуреної ККТ-системи;
- Реалізувати на вибір проксимальний або покоординатно метод для вирішення завдання навчання (1);
- Провести експериментальне порівняння трьох реалізованих методів (метод бар'єрів для завдання (1), прямо-двоїстий метод внутрішньої точки для завдання (2) і проксимальний / покоординатно метод для задачі (1)) на предмет швидкості роботи при 1) різних співвідношеннях між кількістю об'єктів і ознак в даних і 2) різних значеннях параметра точності;
- Написати звіт в форматі PDF з описом всіх проведених досліджень. Даний звіт повинен містити, зокрема, необхідні формули для всіх методів. Також у всіх наведених експериментах має бути зазначено кількість ітерацій, точність, параметри і час роботи методів.
Специфікація функцій, що реалізовуються
Навчання методом штрафних функцій
w = l1linreg_barrier (X, t, lambda, param_name1, param_value1.)