Разработка алгоритмов ранговой регрессии для кредитного скоринга (отчет)

Материал из MachineLearning.

(Различия между версиями)

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

Версия 11:56, 9 февраля 2010

Введение в проект

Описание проекта

Цель проекта

Разработка алгоритмов ранговой регрессии для кредитного скоринга

Обоснование проекта

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

Описание данных

Данные представляют собой матрицу объекты-признаки $\|X\|_{i = 1..N}^{j = 1..M}$ и столбец ответов $\|Y\|_{i = 1..N}$ . Признаки принимают действительные значения, ответы - натуральные из промежутка $[0 \dots K-1]$ .

Критерии качества

Требования к проекту

Выполнимость проекта

Используемые методы

SVM, Логистическая регрессия

Постановка задачи

Описание алгоритмов

Полная стратегия обучения или Full Fixed Margin approach (FFM)

Предположим, что есть некоторая функция $f: x\to R$ , причем ее значения известны только по сравнению с набором порогов $h_1 < \ldots < h_k$ . Объект x попадает в класс $k$ если $h_{k-1} \leq f(x) < h_k$ . Таким образом задача сводится к оценке функции $\hat{f}(x)$ и порогов $\hat{h}_k$ . Оцениваемую функцию положим линейной $\hat{f}(x) = a^Tx$ . Тогда классификатор будет иметь вид:
$\begin{cases} a^Tx < \hat{h}_1 & \to y(x) = 0 \\ \hat{h}_1 \leq a^Tx < \hat{h}_2 & \to y(x) = 1 \\ \dots \\ \hat{h}_{K-1} \leq a^Tx < \hat{h}_K & \to y(x) = K \end{cases}$

Mетод является обобщением svm на случай нескольких упорядоченных рангов. В этом подходе обучение рангового классификатора сводится к решению следующей оптимизационной задачи:
$\begin{cases} a^Ta + C\sum_{i = 1}^N \sum_{j = 1}^M \delta_i^j \to \min_{a, h^j, \delta_i^j} \\ a^Tx_i - h_j \leq -1 + \delta_i^j, i: y_i < i \\ a^Tx_i - h_j \geq -1 + \delta_i^j, i: y_i >= i \end{cases}$
Вместо вышеуказанной оптимизационной задачи удобнее решать двойственную к ней:
$\begin{cases} \sum_{i = 1}^N \sum_{j = 1}^M \lambda_i^j - \frac{1}{2}\sum_{i = 1}^N \sum_{p = 1}^N \sum_{q = 1}^M\sum_{j = 1}^M g_i^j g_p^q x_i^Tx_p \lambda_i^j \lambda_p^q \to \max \\ \sum_{i=1}^N g_i^j\lambda_i^j = 0, 0\leq\lambda_i^j\leq \frac{C}{2}, i:y_i = j, j = 1..M \end{cases}$
$\textrm{g_i^j = } \begin{cases} 1 & y_i \geq j \\ -1 & y_i < j \end{cases}$
Зная оптимальные значения множителей Лагранжа, оптимальные значения параметров оценивадтся по следующим формулам:
$a = \sum_{i = 1}^N (\sum_{j = 1}^M g_i^j\lambda_i^j)x_i$ , если множество $I = \{i: 0 < \lambda_i^j < \frac{C}{2}\}$ не пусто, то $h_j = \frac{\sum_I a^Tx_i - \sum_Ig_i^j}{|I|}$ , иначе:
$\textrm{$h_j$ = } \begin{cases} \dot{h_j} = \max\{\max_{i: \lambda_i = 0, g_i = -1}(a^Tx_i + 1), \max_{i: \lambda_i = C/2, g_i = 1}(a^Tx_i - 1)\}, & \sum_{i: \lambda_i^j = C/2} g_i^j > 0 \\ \ddot{h_j} = \min\{\min_{i: \lambda_i = C/2, g_i = -1}(a^Tx_i + 1), \min_{i: \lambda_i = 0, g_i = 1}(a^Tx_i - 1)\}, & \sum_{i: \lambda_i^j = C/2} g_i^j < 0 \\ h_j \in [\dot{h_j}, \ddot{h_j}], & \sum_{i: \lambda_i^j = C/2} g_i^j = 0 \end{cases}$

Логистическая ранговая регрессия

Предположим, что множество $X\bigotimes Y$ является вероятностным пространством. Вероятность получения данных прецедентов при условии их независимости: $p(X, Y | a, h) = \prod_{i = 1}^Np(x_i, y_i | a, h)$ . Предположим, что плотность распределения векторов признаков объектов, при неизвестном ранге, равномерна, и не зависит от параметров гиперплоскостей, т.е.: $p(x) = p(x | a, h) = const$ , методом наибольшего правдоподобия:
$(a, h_1, \dots, h_K) = \arg\max \prod_{i = 1}^N p(x_i, y_i | a, h) = \arg\max \prod_{i = 1}^N p(y_i |x_i, a, h)p(x_i | a, h) = \arg\max \prod_{i = 1}^N p(y = y_i |x_i, a, h).$
Пусть так же $p(y \geq |x_i, a, h) = \frac{1}{1+exp[-(a^Tx - h_j)]}$ . При таких предположениях решение задачи сводиться к решению оптимизационной задачи:
$\sum_{i: y_i = 0} \ln[1 - p(x_i | y \geq 1, a, h_1)] + \sum_{j=1}^{K-1} \sum_{i: y_i = j} \ln[p(x_i | y \geq j, a, h_j) - p(x_i | y \geq j+1, a, h_{j+1})] + \sum_{i: y_i = K} \ln[p(x_i | y \geq K, a, h_K)] \ra \max_{a, h_1, \ldots, h_K}$

Обзор литературы

Базовые предположения

Математическое описание

Варианты или модификации

<math>Вставьте сюда формулу</math>

Описание системы

Ссылка на файл system.docs
Ссылка на файлы системы

Отчет о вычислительных экспериментах

Визуальный анализ работы алгоритма

Сопоставительный анализ работы алгоритмов

Алгоритмы проверялись на задаче wine classification с репозитория UCI.
размер обучения - 500
размер контроля - 1000
количество классов - 6

метод	Ошибок на обучении не более чем в 1 ранг, %	Ошибок на обучении не более чем в 2 ранга, %	Ошибок на обучении не более чем в 3 ранга, %	Ошибок на обучении не более чем в 4 ранга, %	Ошибок на контроле не более чем в 1 ранг, %	Ошибок на контроле не более чем в 2 ранга, %	Ошибок на контроле не более чем в 3 ранга, %	Ошибок на контроле не более чем в 4 ранга, %	Время работы, сек
FFM	89.8	49.0	12.6	1.8	87.7	47.9	11.6	1.9	7017
Логистическая регрессия	89.4	51.2	3.2	0.2	85.9	44.7	4.4	0.8	0.71

Анализ зависимости работы алгоритма от параметров

Отчет о полученных результатах

Список литературы

Воронцов К.В. Лекции по линейным алгоритмам классификации
Куракин А.В. Байесовский принцип обучения в задаче восстановления ранговой модели данных
Mottl V., Tatarchuk A., Kurakin A. Support vector machines for ranking learning: the full and the truncated fixed margin strategies. International Conference on Machine Learning and Cybernatics, Hong Kong, China, 2007
Логистическая регрессия

Данная статья является непроверенным учебным заданием.

Студент: Участник:Кирилл Павлов

Преподаватель: Участник:В.В. Стрижов

Срок: 15 декабря 2009

До указанного срока статья не должна редактироваться другими участниками проекта MachineLearning.ru. По его окончании любой участник вправе исправить данную статью по своему усмотрению и удалить данное предупреждение, выводимое с помощью шаблона {{Задание}}.

См. также методические указания по использованию Ресурса MachineLearning.ru в учебном процессе.

Источник — «http://machinelearning.ru/wiki/index.php?title=%D0%A0%D0%B0%D0%B7%D1%80%D0%B0%D0%B1%D0%BE%D1%82%D0%BA%D0%B0_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D0%BE%D0%B2_%D1%80%D0%B0%D0%BD%D0%B3%D0%BE%D0%B2%D0%BE%D0%B9_%D1%80%D0%B5%D0%B3%D1%80%D0%B5%D1%81%D1%81%D0%B8%D0%B8_%D0%B4%D0%BB%D1%8F_%D0%BA%D1%80%D0%B5%D0%B4%D0%B8%D1%82%D0%BD%D0%BE%D0%B3%D0%BE_%D1%81%D0%BA%D0%BE%D1%80%D0%B8%D0%BD%D0%B3%D0%B0_%28%D0%BE%D1%82%D1%87%D0%B5%D1%82%29»

Категория: Непроверенные учебные задания

@@ Строка 146: / Строка 146: @@
 == Список литературы ==
+* Воронцов К.В. Лекции по линейным алгоритмам классификации
+* Куракин А.В. Байесовский принцип обучения в задаче восстановления ранговой модели данных
+* Mottl V., Tatarchuk A., Kurakin A. Support vector machines for ranking learning: the full and the truncated fixed margin strategies.  International Conference on Machine Learning and Cybernatics, Hong Kong, China, 2007
+* [[Логистическая регрессия]]
 {{Задание|Кирилл Павлов|В.В. Стрижов|15 декабря 2009}}
 __NOTOC__