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

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

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

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

Задание. В данной задаче вам необходимо восстановить зависимости между значением текущего состояния игры и возможным размером выигрыша игрока. Для восстановления зависимостей необходимо применить метод полиномиальной регрессии, более точный, чем линейная регрессия. Согласно методу, необходимо построить полином p-го порядка, который делит множество точек так, что сумма квадратов расстояний от этих точек до кривой полинома – минимальна.

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

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

Как и в случае линейной регрессии, считаем, что для заданного множества из m пар вещественных чисел (x_i, y_i), i=1,..,m, значений требуется

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

Как и в случае линейной регрессии, считаем, что для заданного множества из m пар вещественных чисел (x_i, y_i), i=1,..,m, значений требуется построить зависимость между свободной (x_i) и зависимой переменной (y_i). Считаем также, что эта зависимость описывается регрессионной моделью y_i = f(w,x_i)+\epsilon_i , где \epsilon_i – некоторая случайная величина.

Определим модель зависимости y от x как полином степени p:

Здесь w = (w_0, w_1,..., w_p) – вектор параметров регрессионной модели, которые вычисляются с помощью метода наименьших квадратов.

Согласно методу наименьших квадратов, искомый вектор параметров w = (w_0, w_1,..., w_p)^T есть решение нормального уравнения w=(A^TA)^{-1}A^Ty где y — вектор, состоящий из значений зависимой переменной, y=(y_1,...,y_m). Матрица имеет вид

Зависимая переменная восстанавливается по полученным весам и заданным значениям свободной переменной y_i^{*}=w_0+w_1 x_i + w_2 x_i ^2 + ... + w_p x_i^p.

Для оценки качества модели используется критерий суммы квадратов регрессионных остатков, SSE — Sum of Squared Errors:

=================================== In English ===================================

For each subject to protection there are threats. If for someone it is important not to allow penetration through the protected perimeter, for another – to exclude information leakages about business secrets of the organization, then for developers of adaptive commercial computer games (which play not on interest) there can be relevant a task to minimize losses from a successful game any of participants.

Speaking differently if to provide an opportunity to control the player's profile, full detailed statistics, the professional biography, the characteristic of a game manner, participation in teams, matches, awards and other, then preliminary estimate of his results of yet not played games and planning of tactics of counteraction to such player by means of adaptive algorithms of a game is possible. It is obvious that the conversation goes about the advancing counteraction when reaction of system of protection begins prior to irreversible realization of threat. And for this purpose not only existence of the techniques allowing to find in due time threat to security, but also application of algorithms capable to make the analysis of a situation and to reveal prerequisites for possible realization of threat and assessment of damage is necessary.

To assess the possible damage, based on the collected characteristics, a regression model is constructed that reflects the dependence of the possible damage on the values of the features of the threat.

Task. In this task you need to restore dependences between value of current state of a game and the possible size of a prize of the player. It is necessary to apply to restoration of dependences a method of polynomial regression, more exact, than linear regression. According to a method, it is necessary to construct a polynom of an order of p which divides a set of points so that the sum of squares of distances from these points to a polynom curve is minimum.

The possible prize (value on a vertical axis) is calculated as value of the constructed polynom, at the point of the game state feature (values on a horizontal axis).

Polynomial regression, as well as the linear regression — a method of restitution of dependence between two variables. Its difference from the linear regression in higher precision, a type of model of dependence and a matrix of A.

As well as in case of the linear regression, we consider that for the given set from m of couples of real numbers (x_i, y_i), i=1,..,m, values is required to construct dependence between free (x_i) and an effect variable (y_i). We consider also that this dependence is described by the regression y_i = f(w,x_i)+\epsilon_i where \epsilon_i– some random value.

Let's define model of dependence of y from x as p degree polynom:

Here w = (w_0, w_1,..., w_p) – a vector of parameters of regression model which are calculated by means of a method of least squares.

According to a method of least squares, required vector of parameters w = (w_0, w_1,..., w_p)^T is the solution of a normal equation of w=(A^TA)^{-1}A^Ty where y — the vector consisting of values of an effect variable, y=(y_1,...,y_m).. The matrix has an appearance

The effect variable is restored on the received weights and the preset values of the unrestricted variable of y_i^{*}=w_0+w_1 x_i + w_2 x_i ^2 + ... + w_p x_i^p

For evaluation test of model is used criterion of the sum of squares of regression oddments, SSE — Sum of Squared Errors:

В первой строке натуральное число P – степень полинома, 1\leq P \leq 3.

Во второй строке натуральное число M – количество точек (x, y), 1 \leq M \leq 100000.

Далее идут в M строк, каждая из которых состоит из двух вещественных чисел разделенных пробелами.

In the first line a natural number P is the polynom degree, 1\leq P \leq 3.

In the second line a natural number of M is the quantity of points (x,  y), (x, y), 1 \leq M \leq 100000.

Further go to M lines, each of which consists of two real numbers separated by spaces.

В первой строке – значение w_0, округленное до десятых

Во второй строке – значение w_1, округленное до десятых

В (P+1)-й строке – значение w_p, округленное до десятых

В последней строке – значение SSE, округленное до десятых

In the first line – the w_0 value rounded to the tenth. In the second line – the w_1 value rounded to the tenth. In the line (P+1) – the wp value rounded to the tenth. In the last line - the value of SSE, rounded to tenths.