Подводя итоги 2021 года (часть 2)

Я рассказал об одном из своих достижений в предыдущей заметке, но куда интереснее и поучительнее разбирать ошибки. А они тоже были, куда же без них?!)

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

Есть и другой момент — это личное сопереживание. Когда какой-то опыт проходит через себя, он воспринимается совсем по-другому. Мало ли что там с кем-то произошло, мы всегда ориентируемся на себя, на свои текущие интересы и потребности. В лучшем случае мы отстранённо констатируем: человек поступил глупо, мне так поступать не стоит. Но вот вопрос, повлияет ли это как-то на наши дальнейшие поступки, станет ли чужой опыт частью нашего собственно? Вряд ли. А в худшем случае мы подумаем: ну и лох, надо же было так облажаться, уж я бы так не сглупил. Вряд ли это можно отнести к релевантному опыту).

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

Ошибки, конечно, интересны не сами по себе, а в контексте их осознания и осмысления, т.е. что было вынесено из этих ошибок? И было ли вообще что-то вынесено? Можно совершить тысячу ошибок, но не заметить ни одну из них. Такие ошибки не имеют ни смысла, ни пользы.

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

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

Итак, технические ошибки. Их две, одна побольше, а другая поменьше, но обе они на тему велосипедостроения. Наверное, у каждого профессионального программиста есть свой любимый «велосипед», а то и не один. Есть и история о том, как он писал что-то, что не нужно было писать вообще, что проще было найти и использовать в готовом виде. Я говорю про open source библиотеки.

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

Я не могу сказать точно, что меня побудило писать свою реализацию функционала для формирования предиктавных моделей по методу k-ближайших соседей (более полная англоязычная версия: k-nearest neighbors algorithm). Отчасти это недооценка сложности, отчасти самомнение. И ведь я знал, как это делается по канону, но почему-то решил что сделаю своею реализацию, более простую и эффективную.

Есть такая замечательная книга по машинному обучению: «Основы машинного обучения для аналитического прогнозирования. Алгоритмы, рабочие примеры и тематические исследования».

На 234-235 стр. чётко и ясно сформулирована основная проблема для метода k-ближайших соседей (перебор большого числа вариантов), а также классическое решения это проблемы: k-мерное дерево или k-d дерево. Но я же могу и без всяких деревьев, у меня свой, особый путь!)

В общем потратив немало времени и сил я все же сделал какое-то своё альтернативное решение на основе мапки (HashMap) и предсоздания всех возможных вариантов атрибутов в виде ключей карты. Я не буду сейчас углублять в своё решение, оно получилось очевидно кривым и ограниченным, но понял я это не сразу.

Основная проблема в моем решении была в том, что мне пришлось дискретизировать значения атрибутов в обучающей выборке. Как это выглядело на практике? Примерно так:

pub fn calc_ratio(v1: u32, v2: u32) -> f32 {
    assert!(v1 <= v2);
    let ratio = v1 as f32 / v2 as f32;
    match ratio {
        x if (0.0..0.4).contains(&x) => 0.0,
        x if (0.4..0.8).contains(&x) => 0.5,
        _ => 1.0,
    }
}

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

Чтобы мой способ хранения и учета k-ближайших соседей работал c нужной производительностью, мне приходилось огрублять значения и искусственно понижать размерность пространства. И самое печальное, что я долго не видел в этом проблемы. Были проведены тысячи прогонов для формирования предикативных моделей и тысячи экспериментов по оценке точности этих моделей. И во всех из них была систематическая ошибка, связанная с ненужной, вредной дискретизаций. Любой следующий эксперимент сравнивался с теми результатами, которые были полученные ранее, но получены все также с помощью кривой реализации метода k-ближайших соседей. Я легко мог не заметить прирост точности, просто потому что терял его на загрубленых данных.

Дошло до меня это довольно поздно — примерно спустя пол года после начала проекта, а дошло во время вынужденной приостановки работ над проектом. Тогда я устроился на новую работу (писал об этом в предыдущей заметке) и мне стало не до домашнего проекта. Слишком много времени и сил уходило на работу, поэтому я временно отложил проект, но какие-то мыли по нему в голову приходили. Потом к концу года стало немного лёгче, я вернулся к проекту и переделал своё кривое решение на классическое k-d дерево. Если кому-то интересно, то я использовал: kiddo.

Это отличная реализация k-d дерева с хорошим API и высокой производительностью. На моих объемах данных и не самом производительном железе расчёт прогноза происходит примерно в пределах 10 микросекунд (10 * 10-6 секунды). Единственное неудобство — использование массивов, это накладывает некоторые требования к инфраструктуре, в основном это выражается в более строгой типизации и активном использовании обобщений. Но в общем и целом ничего такого непреодолимого. Просто для примера кусочек моего кода:

pub struct Predictor<P, const N: usize>
where
    P: Eq + Ord + Copy,
{
    id: PredictorId,
    name: String,
    patterns: KdTree<f32, Ordering, N>,
    forecasts: Vec<Forecast<P>>,
...

Здесь KdTree — сущность из библиотеки kiddo, а N — размер массива, на основе которого строится дерево, это как раз то, что приходиться типизировать, P — это цена, которая также может быть обобщена.

В общем как только я переделал своё самопальное решение на нормальное k-d дерево, я практически сразу же получил хорошие результаты, т.е. увидел, что мои прогнозные модели действительно работают. Причём работают даже одномерные модели! Тогда как раньше я пытался что-то там построить на 4-х и 5-ти и даже 6-ти мерных моделях. Что вообще довольно сложно сделать с тем объем обучающих данных, которым я оперировал (т.н. проклятье размерности).

Вторая моя техническая ошибка была значительно меньше по последствиям. Время я, конечно, на ней тоже потерял, но не так чтобы совсем много. Ошибка выразилась в переусложненном решении. С учётом того, что у меня много расчётов, связанных со скользящим окном, мне нужен функционал, которые это окно моделирует. Также стоит принять во внимание, что сделки сыплются в произвольные моменты времени. Я их накапливаю в векторе (Vec), а потом использую метки времени, которые есть у сделок, чтобы сформировать нужное мне окно. Что делать с устаревшими данными, которое уходят за левую границу окна? Очевидно, что их можно/нужно как-то подчищать, чтобы не отъедать свободную память. Вопрос, как это делать?

И вот здесь я ошибочно выбрал трудный и сложный путь. Не найдя ничего подходящего в виде библиотек (есть какой-то ttl_cache, но мне они не понравился из-за того, что проект заброшен), я решил сделать что-то своё. И это своё вылилось в специальную библиотеку, которая при создании нового хранилища запускало фоновый процесс, который контролировал время жизни хранимых данных и подчищал те из них, которые устарели. Сделано это было на tokio, т.е. использовался tokio::spawn.

Уже гораздо позднее, когда я вновь вернулся к проекту и решил использовать другое решение для формирования прогнозных моделей по методу k-ближайших соседей, я осознал, что мой TtlStorage — это какая-то ненужная, избыточная хрень.

До переделок и упрощения выглядело это как-то так:

type Queue<T> = Arc<RwLock<Vec<(DateTime<Utc>, T)>>>;

(DateTime здесь из chrono)

// storage with time to live
pub struct TtlStorage<T> {
    queue: Queue<T>,
    datetime: Option<Arc<FakeCurrentDateTime>>,
}

Фоновый процесс для очистки устаревших данных выглядел так:

async fn run_remove_outdated_items(
    datetime: Option<Arc<FakeCurrentDateTime>>,
    queue: Queue<T>,
    life_time: Duration,
    check_interval: Duration,
) {
    tokio::spawn(async move {
        let period = tokio::time::Duration::from_micros(check_interval.num_microseconds().unwrap() as u64);
        let mut interval = tokio::time::interval(period);
        loop {
            interval.tick().await;
            let now = if let Some(dt) = datetime.clone() {
                dt.now()
            } else {
                Utc::now()
            };
            Self::actualize(now, queue.clone(), life_time);
        }
    });
}

// dt - это "текущая" дата-время (фейковая или настоящая)
fn actualize(dt: DateTime<Utc>, queue: Queue<T>, life_time: Duration) {
    let pos = queue
        .read()
        .iter()
        .enumerate()
        .rev()
        .find(|(_, p)| dt - p.0 > life_time)
        .map(|p| p.0);

    if let Some(i) = pos {
        queue.write().drain(..i + 1);
    }
}

Здесь можно заметить RwLock (мьютекс из parking_lot), который приходится вводить для того, чтобы данные можно было шарить между потоками. Что явно не лучшим образом сказывается на производительности или точнее может сказаться. Вопрос зачем все это городить, если можно с некоторой периодичностью снаружи дёргать функцию актуализации, которая будет подчищать устаревшие данные? Если не накладывать такую обязанность на TtlStorage, то все становиться значительно проще и быстрее.

FakeCurrentDateTime был нужен для обновления времени где-то снаружи. Это требуется в случае прогона модели на исторических данных, т.е. текущее время это не время now(). Выглядел FakeCurrentDateTime так:

pub struct FakeCurrentDateTime {
    dt: RwLock<DateTime<Utc>>,
}

В итоге я это, конечно, все переделал, избавился от фонового процесса в хранилище, избавился от мьютекса и от FakeCurrentDateTime тоже избавился. Само хранилище при этом стало предельно простым. Единственное неудобство — вызов актуализирующей функции это теперь обязанность владельца хранилища. Но это разумный компромисс.

После переделок хранилище стало выглядеть так:

pub struct TtlStorage<T> {
    items: Vec<T>,
    items_dt: Vec<DateTime<Utc>>,
    life_time: Duration,
}

Я могу оформить и выложить код нового, упрощённого хранилища. Хотя, если честно, не вижу особого смысла, оно тривиальное и создавать для него open source решение мне кажется избыточным. Но может быть, кому-то это будет интересно в качестве простого примера. В общем я ещё подумаю.

Rust — мощный язык и сделать на нем можно многое, но он не освобождает от необходимости думать. Проектные решения, а также ошибки, с ними связанные — это всегда прерогатива и ответственность программиста.

Самое действенное средство от таких глупостей — это, конечно, Code Review. В рабочих проектах можно и нужно организовывать совместный просмотр и обсуждение проектных решений. В домашних проектах с этим несколько сложнее, но все равно стоит искать собственные глупости. Можно на время отойти от проекта, дать себя время подумать, оценить его как бы со стороны, постраться критично взглянуть на свои решения. И тогда ошибки обязательно всплывут. Часто они воспринимаются, как-то что громоздкое, неудобное, странное. Почти всегда это какие-то переусложнения.

На этом я закончу своё повествование, до новых встреч!

Валерий Чугреев, 04.01.2022

Подписаться
Уведомить о
guest
0 комментариев
Межтекстовые Отзывы
Посмотреть все комментарии