Week 4, Logistic Regression

Курс Scalable Machine Learning. Hadoop, Apache Spark, Python, ML -- вот это всё.

Продолжаю конспектировать пройденный курс. В прошлый раз было описание лабораторки Lab 3. Продолжим.

Неделя 4: Логистическая регрессия;
предсказание кликов по рекламным банерам. В смысле, щелкнет посетитель по банеру или нет.

Logistic Regression and Click-through Rate Prediction.

Topics: Online advertising, linear classification, logistic regression, working with probabilistic predictions, categorical data and one-hot-encoding, feature hashing for dimensionality reduction.

Онлайн реклама как задача для large-scale ML комплекса.

Характеристики задачи таковы:

– миллиарды показов банеров миллионам людей

– менее 1% захода по рекламе

– легко собрать много labeled data

Основные действующие лица:

– паблишеры, показывают рекламу и берет деньги с рекламодателей

– рекламодатели, платят за рекламу и ждут привлечения покупателей

– сводня, прослойка между паблишером и рекламодателем, решает задачу, какой именно банер показать конкретному пользователю на конкретном сайте.

Как показатель успеха (за что платит рекламодатель) часто принимается клик по банеру.

The most common metric for success

is clickthrough rate prediction.

And this is what we'll be focusing on

В итоге, сводня должна постоянно решать (в режиме реального времени) задачу:

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

This problem involves estimating a conditional probability,

or the probability of a click event

occurring given a set of predictive features

Данных много, но

However, the data is high-dimensional, sparse,

and skewed.

Additionally, only a small fraction of these ads

actually get clicked on by users,

and thus we have a heavily biased label training set.

In summary, the goal of the clickthrough rate prediction

problem is to use large amounts of data

to estimate the conditional probability that a user will

click on an ad, given features about the user, the ad,

and the publisher.

С задачей разобрались. Теперь посмотрим на инструмент её решения.

LINEAR CLASSIFICATION AND LOGISTIC REGRESSION

In this segment, we'll talk about linear classification

and relate it to the problem of linear regression.

We'll also introduce logistic regression,

which is a particular type of linear classification model.

Click-through rate prediction is another example (классификации, после примера с электропочтой – спам/не спам).

Here, our observations are (user, ad, publisher) triples.

Our labels are not-click and click.

And given a set of labeled observations,

we want to predict whether a new (user ad publisher) triple

will result in a click.

Точнее, оценка нужна не в виде кликнет/не кликнет а в виде вероятность(кликнет) в диапазоне 0 до 1.

В качестве модели будем рассматривать одну из простейших моделей линейной классификации.

Для начала вспомним линейную регрессию.

In linear regression, our key assumption

is that there's a linear mapping between the features

and the label.

Обратите внимание на доп. коэффициент w0 и как, добавив 1 к фичам, мы записали сумму произведений в матричном виде.

Почему линейное уравнение?

– это просто

– часто неплохо работает

– можно произвольно усложнять добавляя в уравнение фичи высших порядков

Осталось придумать, как сделать классификатор на линейном уравнении.

Нам нужен бинарный ответ: щелкнет/не щелкнет.

To achieve this goal, we can't directly

use the linear regression model since linear regression

predictions are real values rather than class predictions.

Ответ заключается в слове threshold

What this rule says is that a w transpose x is positive,

then our prediction y hat is 1.

And a w transpose x is negative, our prediction is negative 1.

And when w transpose x equals 0, we

can arbitrarily choose the prediction

to be 1 or negative 1.

Another way to say this is that w transpose x equals 0

is our decision boundary.

То есть, линия, рисуемая по полученному уравнению, это граница между да и нет.

This decision boundary is defined by the equation w transpose dot x equals 0.

ОК, глядя на знак результата, мы получаем ответ да/нет.

Возникает следующий вопрос: как оценить точность результата?

В линейной регрессии мы использовали среднеквадратичное отклонение – чем больше разница между лейблом и вычисленным результатом, тем больше ошибка/штраф.

Как быть с бинарной классификацией?

Допустим, так: угадал – штраф 0; не угадал – штраф 1. Тоже бинарненько.

Тогда можно сделать так: определим z как произведение лабели y на вычисленное значение wT * x

И определим штрафную функцию как 1 если z < 0 и 0 если z >= 0.

Теперь, когда с моделью и ее оценкой мы определились, можно подумать о том, как тренировать модель.

Суть тренировки в том, чтобы подобрать такой вектор параметров w, который дает минимальную ошибку (сумму значений штрафной функции) на тренировочном наборе данных x, y.

Задача оптимизации.

Но тут есть грабли: штрафная функция не convex

Unfortunately, this is not a convex optimization problem

as a 0-1 loss is not a convex function.

And thus, this is a hard problem to solve.

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

But all hope isn't lost, because instead of using the 0-1 loss

in our optimization problem, we can use a surrogate loss that

is convex and also provides a good approximation to 0-1 loss

For instance, the hinge loss is used to define the SVM model.

The exponential loss is used to describe the Adaboost model.

And the logistic loss is used to define the logistic regression

model.

In particular, we'll focus on logistic regression

Мы сосредоточимся на функции логистической регрессии, хотя SVM выглядит более обещающе.

Как результат применения convex функции, мы можем использовать стандартный метод оптимизации: gradient descent.

И, для борьбы с оверфиттингом, добавляем регуляризацию:

Finally, similar to ridge regression,

we can use a regularized version of logistic regression.

In this regularized version, we're

trading off between two terms.

The first is the log loss on the training data.

And the second is the model complexity.

we introduce a user specified hyper parameter, lambda,

to determine the trade-off between these two terms

В общем-то, это всё, что вам необходимо знать про логистическую регрессию.

В следующий раз продолжим конспектировать материалы 4-ой недели. Будет интерпретация логистической регрессии с точки зрения вероятности.

original post http://vasnake.blogspot.com/2015/11/week-4-logistic-regression.html