Изменения

Перейти к: навигация, поиск

Вариации регрессии

3256 байт добавлено, 20:46, 3 марта 2019
Логическая регрессия
==Логическая регрессия==
'''Логическая регрессия''' (англ. ''logic regression'') {{---}} обобщенный метод регрессии, применяемый в основном в случае, когда независимые переменные имеют двоичную природу (при этом зависимая переменная не обязательно двоичная). Задачей логической регрессии является определение независимых переменных, которые могут быть выражены как результат вычисления [[Определение булевой функции |булевой функции]] от других независимых переменных. 
Обычно в методах регрессии не учитывается связь между переменными. Предполагается, что влияние каждой переменной на результат не зависит от значений других переменных. Однако это предположение зачастую неверно.
Пусть <tex>x_1, x_2, \dots, x_k</tex> {{---}} двоичные независимые переменные, и пусть <tex>y</tex> {{---}} зависимая переменная. Будем пытаться натренировать модели регрессии вида <tex>g(E(y)) = b_0 + b_1 L_1 + \dots + b_n L_n</tex>, где <tex>L_j</tex> {{---}} булева функция от переменных <tex>x_i</tex> (например <tex>L_j = (x_2 \lor \overline{x_4}) \land x_7</tex>).
Для каждого типа модели необходимо определить функцию, которая отражает качество рассматриваемой модели. Например, для линейной регрессии такой функцией может быть остаточная сумма квадратов. Целью метода логической регрессии является минимизация выбранной функции качества посредством настройки параметров <tex>b_j</tex> одновременно с булевыми выражениями <tex>L_j</tex>.
 
[[Файл: Logic_tree_moves.jpg|400px|thumb|Рис.3. Допустимые действия в процессе роста дерева.<br/>Элементы, появившиеся в результате применения операции, выделены черным фоном.]]
 
Может показаться не совсем понятным, как же применить регрессию к булевым выражениям. Рассмотрим в общих чертах алгоритм логической регрессии.
Логическая регрессия, как и другие методы регрессии, перебирает различные выражения в попытках минимизировать функцию потерь. Для <tex>k</tex> переменных можно составить <tex>2^{2^k}</tex> различных выражений. Нужно найти более эффективный метод для поиска наилучшего выражения, чем простой перебор всех вариантов.
Для каждого типа модели необходимо определить функциюЛюбое логическое выражение можно представить в виде дерева, которая отражает качество рассматриваемой моделигде в узлах расположены операции, а листья представляют собой переменные. Будем называть такие деревья '''логическими деревьями''' (англ. ''logic trees''). Будем называть '''соседями''' (англ. Например''neighbours'') логического дерева такие деревья, для линейной регрессии такой функцией может которые могут быть остаточная сумма квадратовполучены из него за один шаг. Допустимые шаги проиллюстрированы на рисунке 3. Рассмотрим самый простой алгоритм поиска наилучшего дерева {{---}} '''жадный поиск''' (англ. ''greedy search'').# В качестве стартового дерева выберем одну переменную, которая дает минимальное значение функции потерь среди всех остальных переменных. Целью метода логической регрессии является минимизация выбранной # Перебираем соседей текущего дерева и выбираем такое, что оно уменьшает значение функции качества посредством настройки параметров <tex>b_j</tex> одновременно потерь по сравнению с булевыми выражениями <tex>L_j</tex>текущим, а также дает наименьший результат среди остальных соседей.# Если такого дерева не существует, алгоритм завершается. Если оно все же есть, выбираем его в качестве текущего и повторяем второй шаг.
[[Файл: Logic_tree_moves.jpg|400px|thumb|Рис.3. Допустимые действия Этот алгоритм склонен к переобучению, а также в процессе роста некоторых ситуациях может остановиться преждевременно, так и не дойдя до наилучшего дерева.]]Существует также алгоритм под названием '''имитация отжига''' (''simulated annealing'') который показывает лучшие результаты, чем описанный жадный поиск.
==См. также==
276
правок

Навигация