- PVSM.RU - https://www.pvsm.ru -
Доброго времени суток!
В свое время, будучи студентом младших курсов, я начал заниматься научно-исследовательской работой в области теории оптимизации и синтеза оптимальных нелинейных динамических систем. Примерно в то же время появилось желание популяризировать данную область, делиться своими наработками и мыслями с людьми. Подтверждением этому служит пара-тройка моих детских незрелых статей на Хабре. Тем не менее, на тот момент эта идея оказалась для меня непосильной. Возможно ввиду моей занятости, неопытности, неумения работать с критикой и советами или чего-то еще. Можно до бесконечности пытаться найти причину, но ситуацию это не изменит: я забросил эту идею на полку, где она благополучно лежала и пылилась до этого момента.
Закончив специалитет и готовясь к защите кандидатской диссертации, я задался вполне логичным вопросом: «а что же дальше?» Имея за плечами опыт как обычной работы, так и исследовательской, я вновь вернулся к той самой идее, которая, казалось бы, должна была утонуть под толщей пыли. Но вернулся я к этой идее в более осознанной форме.
Я решил заняться разработкой программного обеспечения, связанного с той отраслью, которой занимаюсь уже на протяжении 8 лет, и моими личными академическими пристрастиями, которые включают в себя методы оптимизации и машинное обучение.
Ну что ж, всем заинтересовавшимся:
Занимаясь реализацией программного обеспечения для своего диплома (и впоследствии диссертации), я подходил к этому вопросу «в лоб»: меня не волновало, насколько создаваемая система будет гибкой, как легко она будет модифицируема. Желание получить результат здесь и сейчас вкупе с неопытностью приводили к тому, что код постоянно приходилось переписывать, что, конечно же, не влияло положительно на профессиональное развитие. Уже сейчас я понимаю, что, как бы ни хотелось, нельзя сломя голову бросаться решать задачу. Надо вникнуть в ее суть, оценить имеющиеся знания, понять, чего недостает, сопоставить понятия предметной области классам, интерфейсам и абстракциям. Словом, нужно осознать имеющиеся резервы и грамотно подойти к проектированию архитектуры программного приложения.
Как вы уже догадались, эта статья будет посвящена разработке и описанию первых элементов будущего приложения.
На Хабре есть большое количество статей, посвященных методологиям разработки ПО. Например, в этой [1] достаточно понятно описаны основные подходы. Остановимся подробнее на каждом из них:
Я буду стараться придерживаться концепций модели «Agile». На каждую итерацию разработки будет предлагаться определенный набор целей и задач, которые будут подробнее освещаться в статьях.
Итак, на данный момент имеется следующая формулировка общей задачи: разрабатываемое программное обеспечение, должно реализовывать различные алгоритмы оптимизации (как и классические аналитические, так и современные эвристические) и машинного обучения (алгоритмы классификации, кластеризации, редукции размерности пространства, регрессии). Итоговой финальной целью является разработка методик применения данных алгоритмов в области синтеза оптимального управления и создания торговых стратегий на финансовых рынках. В качестве основного языка для разработки был выбран Scala.
Итак, в этой работе я расскажу:
Вследствие того что большую часть своей исследовательской практики я посвятил решениям задачи оптимизации, мне будет удобней оперировать именно с этой точки зрения.
Обычно под решением задачи оптимизации, как бы это банально и косноязычно ни звучало, понимается поиск некоторого «оптимального» (с точки зрения условий задачи) объекта. Понятия «оптимальности» варьируются от одной предметной области к другой. Например, в задаче поиска минимума функции требуется найти точку, которой соответствует наименьшее значение целевой функции, в задача мета-оптимизации требуется определить параметры алгоритма, при которых он дает наиболее точный результат/наиболее быстро отрабатывает/дает наиболее стабильный результат, в задаче синтеза оптимального управления требуется синтезировать контроллер, позволяющий перевести объект в терминальное состояние за наименьшее время и т.д. Уверен, что каждый специалист сможет продолжить это список задачами, связанными с его профессиональной сферой.
В математике, особое внимание уделяется задаче нелинейного программирования [2], к которой можно свести большое количество других прикладных задач. В общем случае, для постановки задачи нелинейного программирования требуется задать:
Таким образом, суть данной задачи можно описать следующим образом: требуется найти в области поиска вектор, обеспечивающий минимальное/максимальное значение целевой функции.
Существует огромное количество алгоритмов решения этой задачи. Условно их можно разделить на две группы:
В принципе, эвристические алгоритмы можно воспринимать как способ направленного перебора. В этой группе вы можете обнаружить достаточно известные генетические алгоритмы [4], алгоритм симуляции отжига [5], различные популяционные [6] алгоритмы. Большое количество алгоритмов объясняется достаточно просто: нет универсального алгоритма, который был бы хорош одновременно для всех типов задач. Кто-то лучше справляется с выпуклыми функциями, другой направлен на работу с функциями, обладающими овражной структурой линий уровня, третий специализируется на многоэкстремальных функциях. Как и в жизни — у всего есть своя специализация.
На основе приведенных ранее рассуждений мне кажется, что проще всего работать с двумя понятиями: преобразование и алгоритм. На них и остановимся подробнее.
Вследствие того что почти любую процедуру/функцию/алгоритм можно рассматривать как некоторое преобразование, будем оперировать с этим объектом как с одним из базовых.
Предлагается следующая иерархия между различными типами преобразований:
Остановимся на элементах поподробнее:
class InhomogeneousTransformation[A, B](transform: A => B) extends Serializable {
def apply(a: A): B = transform(a)
def *[C](f: InhomogeneousTransformation[B, C]) =
new InhomogeneousTransformation[A, C](x => f(transform(x)))
}
Видно, что он содержит всего два метода, один из которых реализует процедуру составления композиции [7] нескольких преобразований (только в не совсем привычном порядке). Это в дальнейшем понадобится для создания более сложных преобразований из простых.
class HomogeneousTransformation[A](transform: A => A)
extends InhomogeneousTransformation[A, A](transform) { }
Здесь два параметра типа были свернуты в один.
class VectorFunction[A <: Algebra[A]]
(transform: Vector[A] => Vector[A])(implicit converter: Double => A)
extends HomogeneousTransformation[Vector[A]](transform) { }
Налицо измененная параметризация обобщенного класса. Теперь данный параметр определяет то, из объектов какого класса будет состоять преобразуемый вектор. Следует отметить ограничение, накладываемое на класс, что определяется данным кодом "[A <: Algebra[A]]". Ограничение выражается в следующем: объекты, из которых составляется вектор, должны поддерживать основные арифметические операции и их можно использовать как аргумент привычных элементарных функций (показательных, тригонометрических и т.п.). Подробный код можно будет посмотреть на исходниках, которые выложены на github'e (ссылка будет в конце работы).
class Function[A <: Algebra[A]]
(transform: Vector[A] => A)(implicit converter: Double => A)
extends VectorFunction[A](x => Vector("result" -> transform(x))) {
def calculate(v: Vector[A]): A = transform(v)
}
object Function {
implicit def createFromInhomogeneousTransformation[A <: Algebra[A]]
(transformation: InhomogeneousTransformation[Vector[A], A])(implicit converter: Double => A) =
new Function[A](x => transformation(x))
}
class Metric[A](transform: A => Real)
extends InhomogeneousTransformation[A, Real](transform) { }
object Metric {
implicit def createFromInhomogeneousTransformation[A](transformation: InhomogeneousTransformation[A, Real]) =
new Metric[A](x => transformation(x))
implicit def toFunction
(metric: Metric[Vector[Real]])(implicit converter: Double => Real): Function[Real] =
new Function[Real](x => metric(x))
}
Приведенные абстракции, на первый взгляд, охватывают основные типы преобразований, который могут понадобится для дальнейших формулировок задач.
Я думаю, что естественным будет определить алгоритм как набор трех операций: инициализация, итеративная часть и терминация. На вход алгоритма подается некоторое задание (Task). В ходе инициализации происходит генерация начального состояния (State) алгоритма, которое модифицируется в ходе повторения итеративной части. В конце с помощью процедуры терминации из последнего состояния алгоритма создается объект, соответствующий типу R выходного параметра алгоритма.
trait GeneralAlgorithm[T <: GeneralTask, S <: GeneralState, R] {
def initializeRandomly(task: T): S
def initializeFromSeed(task: T, seed: S): S
final def initialize(task: T, state: Option[S]): S = {
state match {
case None => initializeRandomly(task)
case Some(seed) => initializeFromSeed(task, seed)
}
}
def iterate(task: T, state: S): S
def terminate(task: T, state: S): R
def prepareFolder(log: Option[String]): Unit = {
if (log.isDefined) {
val temp = new File(log.get)
if (!temp.exists() || !temp.isDirectory())
temp.mkdir()
else {
if (temp.exists() && temp.isDirectory()) {
def prepare(file: File): Unit =
if (file.isDirectory()) {
file.listFiles.foreach(prepare)
file.delete()
}
else file.delete()
prepare(temp)
}
}
}
}
def logState(log: Option[String], state: S, fileId: Int): Unit = {
log match {
case Some(fileName) => {
val writer = new ObjectOutputStream(new FileOutputStream(s"${fileName}/${fileId}.st"))
writer.writeObject(state)
writer.close()
}
case None => ()
}
}
final def work(task: T, terminationRule: S => Boolean, seed: Option[S] = None, log: Option[String] = None): R = {
prepareFolder(log)
var currentState = initialize(task, seed)
var id = 0
logState(log, currentState, id)
val startTime = System.nanoTime()
while (!terminationRule(currentState)) {
currentState = iterate(task, currentState)
id = id + 1
currentState.id = id
currentState.timestamp = 1e-9 * (System.nanoTime() - startTime)
logState(log, currentState, id)
}
terminate(task, currentState)
}
}
Таким образом, для создания конкретного алгоритма, необходимо будет переопределить три описанные ранее процедуры.
case class OptimizationTask[A <: Algebra[A]](f: Function[A], searchArea: Map[String, (Double, Double)]) extends GeneralTask {
def apply(v: Vector[A]): A = f.calculate(v)
}
Обычно состояния (State) у алгоритмов оптимизации имеют одну из следующих форм: одноточечную (когда в ходе работы анализируется и модифицируется один вектор) или популяционная/многоточечная (когда в ходе работы анализируются и модифицируются несколько векторов).
abstract class OptimizationState[A <: Algebra[A]] extends GeneralState {
def getCurrentBest(optimizationTask: OptimizationTask[A])(implicit cmp: Ordering[A]): Vector[A]
}
class MultiPointOptimizationState[A <: Algebra[A]](points: Seq[Vector[A]]) extends OptimizationState[A] {
override def toString: String = {
s"ID: ${id}n" +
s"Timestamp: ${timestamp}n" +
points.zipWithIndex.map{ case (point, id) => s"# ${id}n${point}n"}.mkString("n")
}
override def getCurrentBest(optimizationTask: OptimizationTask[A])(implicit cmp: Ordering[A]): Vector[A] =
points.minBy(point => optimizationTask(point))
def apply(id: Int): Vector[A] = points(id)
def size: Int = points.size
}
class OnePointOptimizationState[A <: Algebra[A]](point: Vector[A]) extends MultiPointOptimizationState(points = Seq(point)) {
override def getCurrentBest(optimizationTask: OptimizationTask[A])(implicit cmp: Ordering[A]): Vector[A] = point
def apply(): Vector[A] = point
}
Таким образом, оптимизационный алгоритм описывается следующим кодом:
abstract class OptimizationAlgorithm[A <: Algebra[A], S <: OptimizationState[A]]
extends GeneralAlgorithm[OptimizationTask[A], S, Vector[A]] { }
Что ж, первые два пункта обещанной программы освещены, пора переходить к третьему.
Оба алгоритма хорошо описаны в различных источниках, поэтому я думаю, что у читателей не составит труда разобраться с ними. Вместо этого я проведу параллели к описанным ранее абстракциям.
class Task(val vectors: Seq[Vector[Real]], val numberOfCentroids: Int) extends GeneralTask {
def apply(id: Int): Vector[Real] = vectors(id)
def size: Int = vectors.size
def toOptimizationTask(): (OptimizationTask[Real], InhomogeneousTransformation[Vector[Real], kCentroidsClusterization]) = {
val varNames = vectors.head.components.keys.toSeq
val values = vectors.flatMap(_.components.toSeq)
val searchAreaPerName =
varNames.map { name =>
val accordingValues =
values
.filter(_._1 == name)
.map(_._2.value)
(name, (accordingValues.min, accordingValues.max))
}
val totalSearchArea =
Range(0, numberOfCentroids)
.flatMap { centroidId =>
searchAreaPerName
.map { case (varName, area) => (s"${varName}_${centroidId}", area) }
}.toMap
val varNamesForCentroids =
Range(0, numberOfCentroids)
.map { centroidId => (centroidId, varNames.map { varName => s"${varName}_${centroidId}" }) }
.toMap
val splitVector: InhomogeneousTransformation[Vector[Real], Map[Int, Vector[Real]]] =
new InhomogeneousTransformation(
v =>
Range(0, numberOfCentroids)
.map { centroidId =>
(centroidId,
Vector(v(varNamesForCentroids(centroidId))
.components
.map { case (key, value) => (key.dropRight(1 + centroidId.toString.length), value) }))
}.toMap)
val vectorsToClusterization: InhomogeneousTransformation[Map[Int, Vector[Real]], kCentroidsClusterization] =
new InhomogeneousTransformation(v => new kCentroidsClusterization(v))
val clusterizationForMetric: InhomogeneousTransformation[kCentroidsClusterization, (kCentroidsClusterization, Seq[Vector[Real]])] =
new InhomogeneousTransformation(clusterization => (clusterization, vectors))
val quality: Metric[Vector[Real]] = splitVector * vectorsToClusterization * clusterizationForMetric * SquareDeviationSumMetric
(new OptimizationTask(f = quality, searchArea = totalSearchArea), splitVector * vectorsToClusterization)
}
}
Здесь следует обратить внимание на две строки:
val quality: Metric[Vector[Real]] = splitVector * vectorsToClusterization * clusterizationForMetric * SquareDeviationSumMetric
(new OptimizationTask(f = quality, searchArea = totalSearchArea), splitVector * vectorsToClusterization)
В первой из них строится композиция преобразований: вектор разбивается на систему векторов, описывающие центроиды, центроиды преобразуются в кластеризатор, кластеризатор оценивается по метрике «суммарное расстояние точек кластеров от соответствующих центроид» . Полученная композиция преобразований в дальнейшем может рассматриваться как целевая функция для задачи оптимизации.
Кластеризатор, построенный с помощью алгоритма K-Means однозначно определяется своими центроидами. Сам алгоритм K-Means представляет собой постоянную замену текущих центроид новыми центроидами, рассчитанными как среднее значение всех векторов в отдельно взятых кластерах. Таким образом, в любой момент времени состояние алгоритма K-Means можно представить как набор векторов.
Таким образом, кластеризатор может быть построен либо напрямую с помощью алгоритма K-Means, либо с помощью решения задачи поиска оптимального кластеризатора, обеспечивающего минимум суммарного расстояния точек кластеров от соответствующих центроид.
Сгенерируем несколько синтетических наборов данных размерности 2, 3 и 5.
f[mu_, sigma_, N_] :=
RandomVariate[#, N] & /@ MapThread[NormalDistribution, {mu, sigma}] //
Transpose
Num = 100;
sigma = 0.1;
data2D = Join[
f[{0.5, 0}, {sigma, sigma}, Num],
f[{-0.5, 0}, {sigma, sigma}, Num]
];
ListPlot[data2D]
Export[NotebookDirectory[] <> "data2D.csv", data2D, "CSV"];
Num = 100;
mu1 = 0.0; sigma1 = 0.1;
mu2 = 2.0; sigma2 = 0.2;
mu3 = 5.0; sigma3 = 0.3;
data3D = Join[
f[{mu1, mu1, mu1}, {sigma1, sigma1, sigma1}, Num],
f[{mu2, mu2, mu2}, {sigma2, sigma2, sigma2}, Num],
f[{mu3, mu3, mu3}, {sigma3, sigma3, sigma3}, Num]
];
dimReducer = DimensionReduction[data3D, Method -> "TSNE"];
ListPlot[dimReducer[data3D]]
Export[NotebookDirectory[] <> "data3D.csv", data3D, "CSV"];
Num = 250;
mu1 = -2.5; sigma1 = 0.9;
mu2 = 0.0; sigma2 = 1.5;
mu3 = 2.5; sigma3 = 0.9;
data5D = Join[
f[{mu1, mu1, mu1, mu1, mu1}, {sigma1, sigma1, sigma1, sigma1,
sigma1}, Num],
f[{mu2, mu2, mu2, mu2, mu2}, {sigma2, sigma2, sigma2, sigma2,
sigma2}, Num],
f[{mu3, mu3, mu3, mu3, mu3}, {sigma3, sigma3, sigma3, sigma3,
sigma3}, Num]
];
dimReducer = DimensionReduction[data5D, Method -> "TSNE"];
ListPlot[dimReducer[data5D]]
Export[NotebookDirectory[] <> "data5D.csv", data5D, "CSV"];
И «прогоним» их через оба алгоритма построение кластеризатора. Полученные результаты сведем в таблицу:
2D | 3D | 5D | |
---|---|---|---|
Clusterization Quality (via K-Means): | 90.30318857796479 | 96.48947132305597 | 1761.3743823022821 |
Clusterization Quality (via Optimization): | 87.42370021528419 | 96.4552486768293 | 1760.993575500699 |
По таблице видно, что даже несложный алгоритм оптимизации может успешно решить задачу построения простейшего кластеризатора. При этом созданный кластеризатор будет оптимальным (а если честно, то субоптимальным, так как используемый метод оптимизации не гарантирует нахождение точки глобального оптимума [3]) с точки зрения используемой метрики качества. Естественно, для задач большей размерности используемый алгоритм оптимизации уже вряд ли подойдет (тут лучше пользоваться более сложными и эффективными алгоритмами, основывающимися на нескольких эвристиках разного уровня). Для небольшой же синтетической задачи Random Search справился достаточно хорошо.
Хочется поблагодарить всех, кто прочитал статью, отписался в комментариях. Словом, всех, кто внес свой вклад в создание данной работы. Наверное, следует сразу отметить, что статьи на эту тематику будут появляться по мере возможностей и моей текущей загруженности. Но мне хочется сказать, что на этот раз я постараюсь довести начатое мной дело до конца.
Ссылки и литература
Автор: Валентин Пановский
Источник [19]
Сайт-источник PVSM.RU: https://www.pvsm.ru
Путь до страницы источника: https://www.pvsm.ru/programmirovanie/255257
Ссылки в тексте:
[1] этой: https://habrahabr.ru/company/edison/blog/269789/
[2] нелинейного программирования: https://ru.wikipedia.org/wiki/%D0%9D%D0%B5%D0%BB%D0%B8%D0%BD%D0%B5%D0%B9%D0%BD%D0%BE%D0%B5_%D0%BF%D1%80%D0%BE%D0%B3%D1%80%D0%B0%D0%BC%D0%BC%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5
[3] локального экстремума: https://ru.wikipedia.org/wiki/%D0%AD%D0%BA%D1%81%D1%82%D1%80%D0%B5%D0%BC%D1%83%D0%BC
[4] генетические алгоритмы: https://habrahabr.ru/post/128704/
[5] алгоритм симуляции отжига: https://habrahabr.ru/post/112189/
[6] популяционные: https://en.wikipedia.org/wiki/Fish_School_Search
[7] композиции: https://ru.wikipedia.org/wiki/%D0%9A%D0%BE%D0%BC%D0%BF%D0%BE%D0%B7%D0%B8%D1%86%D0%B8%D1%8F_%D1%84%D1%83%D0%BD%D0%BA%D1%86%D0%B8%D0%B9
[8] википедии: https://en.wikipedia.org/wiki/Random_optimization
[9] Код проекта: https://github.com/wol4aravio/Kaimere/tree/7aa7b634983c3410e99dab3b0b0c4919c31ba54a
[10] Код для генерации/визуализации: https://github.com/wol4aravio/Habrahabr-Article-1
[11] 1: https://ru.wikipedia.org/wiki/K-means
[12] 2: https://en.wikipedia.org/wiki/K-means_clustering
[13] 3: http://projecteuclid.org/euclid.bsmsp/1200512992
[14] 4: https://habrahabr.ru/post/67078/
[15] 2: https://books.google.ru/books?id=y4JUSgAACAAJ&dq=%D0%BF%D0%B0%D0%BD%D1%82%D0%B5%D0%BB%D0%B5%D0%B5%D0%B2+%D0%BB%D0%B5%D1%82%D0%BE%D0%B2%D0%B0+%D0%BC%D0%B5%D1%82%D0%BE%D0%B4%D1%8B+%D0%BE%D0%BF%D1%82%D0%B8%D0%BC%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D0%B8+%D0%B2+%D0%BF%D1%80%D0%B8%D0%BC%D0%B5%D1%80%D0%B0%D1%85+%D0%B8+%D0%B7%D0%B0%D0%B4%D0%B0%D1%87%D0%B0%D1%85&hl=en&sa=X&redir_esc=y
[16] 3: http://www.springer.com/us/book/9781441916631
[17] 1: https://books.google.ru/books?id=RIn-oAEACAAJ&dq=learning+scala&hl=en&sa=X&ved=0ahUKEwjJub6b1enTAhWrHJoKHfeVC9kQ6AEILDAB
[18] 2: https://books.google.ru/books?id=xVU2AAAAQBAJ&printsec=frontcover&dq=learning+scala&hl=en&sa=X&ved=0ahUKEwjJub6b1enTAhWrHJoKHfeVC9kQ6AEIXTAJ
[19] Источник: https://habrahabr.ru/post/328198/?utm_source=habrahabr&utm_medium=rss&utm_campaign=best
Нажмите здесь для печати.