- PVSM.RU - https://www.pvsm.ru -
Доброго времени суток! Пора вновь вернуться к задачам оптимизации. На этот раз мы займемся линейной регрессией и разберемся, кто же такие коты — только пушистые домашние мерзавцы животные или еще и неплохой инструмент для решения прикладных задач.
За прошедшее время (а его прошло немало) я немного «причесал» репозиторий, написал более-менее несущие смысл ReadMe, а также провел реструктуризацию проектов. Что изменилось с момента прошлой статьи [1], и каково состояние проекта на данный момент?
Как я и обещал в первой работе, в начале статьи я буду обозначать круг задач, которые будут решаться, и затем останавливаться на каждой более подробно. Ссылки на репозиторий будут приведены в конце.
Итак, в этой работе мы поговорим:
Начнем с формулирования задачи регрессии.
Пусть имеется набор измерений, который удобно представить в виде матрицы:
т.е. каждое измерение представляется вектором из . Также имеется набор значений зависимой переменной
Будем работать с простым случаем, когда зависимая переменная является одномерной. Решая задачу регрессии, нужно построить модель, которая с учетом некоторой метрики качества (критерия эффективности) будет реализовывать связь между набором измерений и зависимой переменной, т.е. найти модель
где — вектор параметров модели, т.ч. . Очевидно, что задача аппроксимации и регрессии тесно связаны.
Таким образом, если вы экспертно зафиксировали форму желаемой модели, то вся задача сводится к определению значений вектора параметров . Следует отметить, что для машинного обучения действует следующий принцип: чем больше у модели степеней свободы (читай параметров), тем более вероятно, что используемая модель переобучится. В случае же если степеней свободы немного, то есть все шансы, что модель не будет достаточно точной.
В этом плане линейные модели являются, наверное, некоторым переходным звеном. Несмотря на кажущуюся простоту, для многих ситуаций они с достаточно высокой точностью решают задачу регрессии. Тем не менее, при сильной зашумленности данных линейные модели порой нуждаются в искусственном ограничении (регуляризации).
trait GeneralizedLinearModel {
def getWeights(): Vector[Real]
def apply(v: Vector[Real]): Real = getWeights().dot(v + bias)
def apply(vectors: Seq[Vector[Real]]): Seq[Real] = vectors.map(this.apply(_))
def convertToTransformation(): InhomogeneousTransformation[Vector[Real], Real] =
new InhomogeneousTransformation[Vector[Real], Real](v => this.apply(v))
}
object GeneralizedLinearModel {
val bias = Vector("bias" -> Real(1.0))
object Metrics {
def RSS(generalizedLinearModel: GeneralizedLinearModel, input: Seq[Vector[Real]], output: Seq[Real]): Real = {
val predictions = generalizedLinearModel(input)
predictions.zip(output)
.map { case (pred, real) => (pred - real) ^ 2.0 }
.reduce(_ + _) / input.length
}
}
}
В самом trait'е определены:
В одноименном объекте имеются
Как это принято, начнем с наиболее простой модели и будем ее по-тихоньку усложнять. Итак, в общем случае линейная регрессия задается следующей формулой:
из которой видно, что размерность вектора равна размерности вектора измерений плюс один. Нулевая компонента называется смещением (bias term или intercept term). По аналогии с простой функцией , где константа отвечает за смещение графика относительно оси абсцисс.
Таким образом, линейную модель можно выразить через скалярное произведение
Удобно поставить задачу поиска оптимального значения вектора параметров с помощью остаточной суммы квадратов (RSS, residual sum of squares)
При такой постановке задачи становится возможным найти аналитическое решение, которое выражается следующей формулой:
где матрица получается из матрицы путем добавления слева столбца, состоящего из единиц.
Как видно из приведенного выше описания, задача оптимизации уже поставлена. Так что в дальнейшем останется лишь применить к ней выбранный алгоритм оптимизации.
case class OrdinaryLeastSquaresRegression(w: Vector[Real]) extends GeneralizedLinearModel {
override def getWeights(): Vector[Real] = w
}
object OrdinaryLeastSquaresRegression {
class Task(input: Seq[Vector[Real]], output: Seq[Real]) extends General.Task {
def toOptimizationTask(searchArea: Map[String, (Double, Double)]): (Optimization.Real.Task, InhomogeneousTransformation[Vector[Real], OrdinaryLeastSquaresRegression]) = {
val vectorToRegressor =
new InhomogeneousTransformation[Vector[Real], OrdinaryLeastSquaresRegression]((w: Vector[Real]) => OrdinaryLeastSquaresRegression(w))
val task = new Optimization.Real.Task(
new Function[Real]((w: Vector[Real]) =>
GeneralizedLinearModel.Metrics.RSS(vectorToRegressor(w), input, output)), searchArea)
(task, vectorToRegressor)
}
}
}
В случае если необходимо по тем или иным причинам уменьшить степень вариативности модели без ее структурного изменения, можно использовать регуляризацию, которая накладывает ограничения на параметры модели.
Ridge regression (гребневая регрессия) использует L2 регуляризацию параметров модели:
где — L2 норма. Параметр отвечает за сжатие коэффициентов: с увеличением параметры модели стремятся к нулю. Наглядно это очень хорошо продемонстрировано на официальном сайте пакета scikit [2]:
Как и в случае с простой линейной регрессией для гребневой регрессии имеется возможность аналитически выразить решение:
где — единичная матрица порядка , в левом верхнем углу которой находится ноль.
class RidgeRegression(w: Vector[Real], alpha: Double) extends OrdinaryLeastSquaresRegression(w) { }
object RidgeRegression {
class Task(input: Seq[Vector[Real]], output: Seq[Real]) extends General.Task {
def toOptimizationTask(searchArea: Map[String, (Double, Double)], alpha: Double): (Optimization.Real.Task, InhomogeneousTransformation[Vector[Real], RidgeRegression]) = {
val vectorToRegressor =
new InhomogeneousTransformation[Vector[Real], RidgeRegression]((w: Vector[Real]) => new RidgeRegression(w, alpha))
val task = new Optimization.Real.Task(
new Function[Real]((w: Vector[Real]) =>
GeneralizedLinearModel.Metrics.RSS(vectorToRegressor(w), input, output) +
alpha * w.components.filterKeys(_ != "bias").values.map(_ ^ 2.0).reduce(_ + _)), searchArea)
(task, vectorToRegressor)
}
}
}
Для Lasso Regression постановка задачи похожая, разница заключается в том, что теперь используется L1 регуляризация параметров модели:
где — L1 норма
class LassoRegression(w: Vector[Real], alpha: Double) extends OrdinaryLeastSquaresRegression(w) { }
object LassoRegression {
class Task(input: Seq[Vector[Real]], output: Seq[Real]) extends General.Task {
def toOptimizationTask(searchArea: Map[String, (Double, Double)], alpha: Double): (Optimization.Real.Task, InhomogeneousTransformation[Vector[Real], LassoRegression]) = {
val vectorToRegressor =
new InhomogeneousTransformation[Vector[Real], LassoRegression]((w: Vector[Real]) => new LassoRegression(w, alpha))
val task = new Optimization.Real.Task(
new Function[Real]((w: Vector[Real]) =>
GeneralizedLinearModel.Metrics.RSS(vectorToRegressor(w), input, output) / (2.0 * input.length) +
alpha * w.components.filterKeys(_ != "bias").values.map(Algebra.abs(_)).reduce(_ + _)), searchArea)
(task, vectorToRegressor)
}
}
}
Таким образом, с точки зрения оптимизации, Ridge regression и Lasso Regression отличаются лишь способом постановки задачи минимизации.
Как уже стало ясно из названия, алгоритм имитирует поведение животных семейства кошачьих (в том числе и домашних кошек). Что Вы можете сказать о своем домашнем любимце? Он может отыгрывать роль милого лежебоки (хотя мы на самом деле знаем, какие коварные мысли роятся в его голове), может вообразить себя великим (но осторожным) исследователем, а может просто носиться по квартире за несуществующим (а точнее невидимым вам) соперником. Лежащих и недвижимых словно Великая Китайская стена котов мы оставим в покое, пусть себе отдыхают, а вот на последних двух действиях остановимся подробнее. Для любого алгоритма оптимизации хорошо иметь несколько стадий поиска: глобального, в ходе которого мы должны попасть в область притяжения локального экстремума (а в идеале — глобального), и уточняющего, в ходе которого мы должны придвинуться из окрестности экстремума ближе к его истинному расположению. Ничего не напоминает? В самом деле, коты, гоняющиеся за незримым врагом, — явные кандидаты на реализацию процедуры глобального поиска, а вот аккуратные исследователи помогут вам найти оптимальное место для отдыха. Эти две эвристики лежат в основе алгоритма Cat Swarm Optimization. Для полной картины остается представить, что у вас не один кот, а целая стая. Но так ведь даже лучше, верно?
Псевдокод алгоритма представлен ниже:
Шаг 1. Инициализировать популяцию из N котов.
Шаг 2. Определить приспособленность каждого кота на основе его позиции в исследуемом пространстве. Запомнить "лучшего" кота (в терминологии задачи минимизации, ему будет соответствовать наименьшее значение функции).
Шаг 3. Переместить котов в соответствии с их процедурой смещения (поиск или погоня).
Шаг 4. Заново присвоить котам режимы перемещения в соответствии с параметром MR.
Шаг 5. Проверить условие окончания работы. В случае его невыполнения перейти к шагу 2.
Если же постараться формализовать все идеи, то в математическом выражении мы имеем следующие тезисы:
class CatSwarmOptimization(numberOfCats: Int, MR: Double,
SMP: Int, SRD: Double, CDC: Int, SPC: Boolean,
velocityConstant: Double, velocityRatio: Double,
generator: DiscreteUniform with ContinuousUniform = Kaimere.Tools.Random.GoRN) extends Algorithm
Итак, что же представляют из себя режимы, в которых могут находиться коты? Тут все просто.
Во время режима поиска из текущего положения генерируются новые возможные положения . Новое положение выбирается выбирается по методу рулетки [3], где вероятность выборка -го положения определяется по формуле
Для задачи максимизации максимум в числителе следует заменить на минимум.
Теперь немного о том, как реализуется погоня. Чтобы не пугать хозяина, все-таки следует гоняться не за вымышленным врагом, а за вполне реальным — котом, который на данный момент нашел себе лучшее место (его позиция будет обозначаться ). Скорость кота меняется по следующему правилу:
где — равномерно распределенная случайная величина, а — константа скорости (та самая, которая отвечает за поворотливость). Новое положение кота рассчитывается следующим образом: .
case class Cat(location: Vector[Real], velocity: Vector[Real])(implicit generator: DiscreteUniform with ContinuousUniform) {
def getFromSeries[T](data: Seq[T], n: Int, withReturn: Boolean): Seq[T] =
withReturn match {
case true => Seq.fill(n)(generator.getUniform(0, data.size - 1)).map(x => data(x))
case false => data.sortBy(_ => generator.getUniform(0.0, 1.0)).take(n)
}
def seek(task: Task, SPC: Boolean, SMP: Int, CDC: Int, SRD: Double): Cat = {
val newLocations = (if (SPC) Seq(location) else Seq()) ++
Seq.fill(SMP - (if (SPC) 1 else 0))(location)
.map { loc =>
val ratio =
getFromSeries(task.searchArea.keys.toSeq, CDC, false)
.map { key => (key, generator.getUniform(1.0 - SRD, 1.0 + SRD)) }.toMap
(loc * ratio).constrain(task.searchArea)
}
val fitnessValues = newLocations.map(task(_)).map(_.value)
val newLocation =
if (fitnessValues.tail.forall(_ == fitnessValues.head)) newLocations(generator.getUniform(0, SMP - 1))
else {
val maxFitness = fitnessValues.max
val minFitness = fitnessValues.min
val probabilities = fitnessValues.map(v => (maxFitness - v) / (maxFitness - minFitness))
val roulette =
0.0 +: probabilities.tail
.foldLeft(Seq(probabilities.head)) { case (prob, curr) => (curr + prob.head) +: prob }
.reverse
val chosen = generator.getUniform(0.0, roulette.last)
val idChosen = roulette.sliding(2).indexWhere{ case Seq(a, b) => a <= chosen && chosen <= b}
newLocations(idChosen)
}
new Cat(newLocation, newLocation - this.location)
}
def updateVelocity(bestCat: Cat, velocityConstant: Double, maxVelocity: Map[String, Double]): Vector[Real] = {
val newVelocity = this.velocity + (bestCat.location - this.location) * velocityConstant * generator.getUniform(0.0, 1.0)
Vector(newVelocity.components
.map { case (key, value) =>
if (value.value > maxVelocity(key)) (value, Real(maxVelocity(key)))
if (value.value < -maxVelocity(key)) (value, Real(-maxVelocity(key)))
(key, value)
})
}
def trace(task: Task, bestCat: Cat, velocityConstant: Double, maxVelocity: Map[String, Double]): Cat = {
val newVelocity = this.updateVelocity(bestCat, velocityConstant, maxVelocity)
val newLocation = (location + newVelocity).constrain(task.searchArea)
new Cat(newLocation, newVelocity)
}
def move(mode: Int, task: Task, bestCat: Cat, SPC: Boolean, SMP: Int, CDC: Int, SRD: Double, velocityConstant: Double, maxVelocity: Map[String, Double]): Cat = mode match {
case 0 => seek(task, SPC, SMP, CDC, SRD)
case 1 => trace(task, bestCat, velocityConstant, maxVelocity)
}
}
Теперь, когда все основные моменты алгоритма перечислены, пора уже разобраться, смогут ли коты построить регрессию?
Сгенерируем [4] несколько тестовых наборов данных (в тетрадке также есть расчет с моделей регрессий с помощью scikit):
где — равномерно распределенная случайная величина.
Видно, что найденные значения достаточно близки к результатам, полученными с помощью scikit.
Таким образом, приведенная постановка задачи, несмотря на свою модельность и простоту, позволила познакомиться с метаэвристическим алгоритмом Cat Swarm Optimization. При разработке оптимизационных процедур зачастую полезно позаниматься наблюдением за окружающим миром, ведь, как известно, «природа знает лучше» [5].
Ссылки и литература
Автор: wol4aravio
Источник [11]
Сайт-источник PVSM.RU: https://www.pvsm.ru
Путь до страницы источника: https://www.pvsm.ru/programmirovanie/258329
Ссылки в тексте:
[1] прошлой статьи: https://habrahabr.ru/post/328198/
[2] официальном сайте пакета scikit: http://scikit-learn.org
[3] методу рулетки: https://en.wikipedia.org/wiki/Fitness_proportionate_selection
[4] Сгенерируем: https://github.com/wol4aravio/HabrahabrNotebooks/blob/Article_2
[5] «природа знает лучше»: http://fb.ru/article/238473/ekologicheskie-zakonyi-kommonera
[6] Код проекта: https://github.com/wol4aravio
[7] 1: https://habrahabr.ru/company/ods/blog/323890/
[8] 2: http://scikit-learn.org/stable/modules/linear_model.html
[9] Книжка по машинному обучению: https://books.google.ru/books?isbn=0387310738
[10] Cat Swarm Optimization: https://www.researchgate.net/publication/221419703_Cat_Swarm_Optimization
[11] Источник: https://habrahabr.ru/post/328760/
Нажмите здесь для печати.