Яндекс кружок по ИИ (разбор)

Вступление

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

P.s. с такими решениями без штрафов выбивается топ 1-2 (Мои 60к штрафов дада)

Инфо

1. Весь код будет прикреплён к посту
2. Идей для решения каждой из задач немало. Я лишь показываю как можно было достичь хороший результат

Задача A

У этой задачи на самом деле довольно простое идейное решение на 495к+ скора на паблике.

У нас есть 2 основных подхода как мы можем рассматривать эту задачу:
1) Пытаться найти наиболее похожую функцию и под неё подстроить предсказание

2) Рассмотреть задачу как временной ряд с выбросами, где мы уже знаем данные о будущем и нам лишь нужно восстановить ряд.

Я выбрал второй подход

Решение

1) Выбираем окно в k семплов

2) Считаем медиану в этом окне

3) Смотрим на |x_i - median| > k * std,

где

median - медиана локального подокна

std - стандартное отклонение

x_i - проверяем каждый семпл в подгруппе

k - просто коэффициент, который вы подбираете ручками

4) Если условие выполняется, то ничего не меняем

4.1) Если условие не выполняется, то берём ещё меньшее подокно (или оставляем такое-же) считаем в нём медиану и заполняем ей этот "выброс"

И так делаем итеративно для всех n по всем m

Вывод

Изначально я траил конфиг с несколькими окнами и подобное и именно так и было выбито 497к, но я продолжал тестить, а штраф копиться, поэтому оставил сабм на 496к без штрафа, со штрафом 486к

Задача Б

Моя самая нелюбимая задача (40к штрафов), но не по причине штрафов, а потому что я очень долго пытался её улучшить и забивал на штрафы. У меня немного получилось это сделать, но решение у меня очень очень глупое и примитивное. Я просто вывел несколько фичей (вы их увидите в коде). В описании решения будет лишь основная и первая идея на 429к

Идея вкратце: Сортируем токены по невозростанию длины

Решение

1) Мы сортируем токены по убыванию длины, то есть вначале самые длинные, и мы пытаемся сначала встроить длинные

2) Потом просто перебираем все токены

3) Для каждого токена перебираем все слова

4) Внутри слова перебираем все подстроки длины токена и проверяем можем ли мы его встроить.

4.1) Чтобы мы могли встроить токен у нас должно выполняться несколько условий:

1. Английская буква, которую мы смотрим не используется в глобальном словаре (инглиш ту марс), или если используется, то подходим нам по конфигурации
2. Английская буква, которую мы смотрим не используется во временном словаре (инглиш ту марс), или если используется, то подходим нам по конфигурации. Временный словарь - это словарь, который мы пытаемся собрать для конкретной подстроки, если у нас получается собрать его, так чтобы ни одно из условий не нарушилось, то мы добавляем результаты временного словаря в глобальный. (Мы добавляем новые обозначения буква к букве)

5) Если подходит, то просто итеративно маппим для каждого токена буквы подходящие ему.

6) Вот вам тупой солюшн Бшки на хороший скор

P.s. В конце концов мне удалось выбить 436к чистого скора, но я там сортировал не только по длине, ввёл ещё 2 фичи, но это уже дополнение и оно будет в файле.

Вывод

Она была не сложной, а нудной. Идея её решения не кажется мне красивой в отличие от остальных задач, однако тоже полезно и прикольно было порешать!

Я в итоге на этой задаче выбил самый худший скор из всех своих, но это логично. У Бшки в среднем скоры хуже были, поэтому вот вам мои сабмиты

Задача C

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

1) Просто разбить kmeans'ом на k кластеров

2) Более продвинутая техника 1D Kmeans + DP, и перебрать разные k, например:

[1, 2, 4, 8, 16, 32, 64, 128, 256] - а потом выбрать лучшее.

3) Просто какая-то смешная эвристика, которая, на удивление очень хорошо работает, например перцентили (это задействовано и в моём решении)

3.1) Или просто взять n знаков после запятой и это оставить как группы

Спойлер

Я не претендую на самое лучшее по баллам решение C-шки, я выбил всего-лишь 482666, я видел и скоры побольше, однако я претендую на то, что моя идея просто ахеренна

Моё решение (идея и обоснование)

Идея решения

Если мы разобьём на в самом начале наши данные на 256 кластеров, то потом мы можем объединять ближайшие кластеры и тем самым получить инфу обо всех кластерах, то есть у нас изначально 256 кластеров, объединяем те, которые при объединении дают максимальный скор и так делаем итеративно, пока у нас не останется 1 кластер. А в самом конце выбираем самое лучшее количество d, тем самым это нам позволит будто бы сделать оптимальное решени

Математика

RMSE_{pixel}

И сейчас начнётся миллион скринов формулок из обсидиана (ЛЕТССС ГОУУУУ):

Так мы можем высчитать общее отклонение RMSE_{pixel} при условия наличия данных для всех групп

Объединение кластеров

Если мы хотим объединить 2 ближайших кластера, то что нам нужно для этого пересчитать, правильно:

RMSE_{pixel}, RMSE_{edge} (в итогу решение без него, но для него тоже есть обоснования), ну и чисто стат. приколы SSE (сумма квадатов отклонений это MSE * n), среднее новой группы

Давайте пересчитывать!

1) Среднее

2) Нам нужны SSE для старых групп, чтобы посчитать для новой

3) Чтобы высчитать новое RMSE нам просто нужно по факту разделить SSE_{new} на количество семплов в новой группе, так давайте посчитаем SSE_{new}

Последний член нужен, т.к. у нас новое среднее и центроида смещается, поэтому последний член нормирует эту величину, как раз-таки смещения квадратичное первого среднего от второго нормируется.

Проще говоря последний член - это межгрупповая объяснённая дисперсия (ANOVA привет)

4) Теперь нам ничего не мешает пересчитать RMSE_{pixel} для новой группы

Вот так мы можем обновлять RMSE_{pixel} для каждой группы.

RMSE_{edge}

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

Интуиция

Если RMSE_{edge} высокий - это значит, что разделение на кластеры очень сильно рваное и абсолютно не гладкое

Реализация

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

Решение

Теперь вы понимаете основные обоснования и бэкграунд моего решения и я могу вам описать все шаги:

1) Разбиваем наши данные на 256 перцентилей по уникальным значениям (или меньше, если уникальных меньше 256), то есть берём массив с уникальными значениями и перцентили в нём - это наше начальное разбиение.

2) Потом считаем для него все статистики и скоры

3) Идём итеративно и сжимаем количество кластеров, пересчитывая и записывая новые результаты

4) В конце выбираем лучший скор и выбираем эти центроиды и количество кластеров и выводим.

Дополнительная информация

Если вам интересно как моё решение показывало себя на тестах, то вот вам график восстановленный с первого теста моим алгоритмом

Видите этот скачок в самом начале - это очень странная и контрестественная фигня подтолкнула меня на то, что с моим решением, что-то не так. Так на самом деле и было. Из-за моих упрощений RMSE_{edge} считается кривовато и, поэтому финальный сабмит был без него. (В этом используются веса для скора такие-же как и в задаче)

Вот как выглядит график без RMSE_{edge} как вы видите уже намного более правдоподобно и гладко. (В этом используются веса для скора [0.85, 0.0, 0.15])

Где первое значение веса

w_1 - RMSE_{pixel}

w_2 - RMSE_{edge}

w_3 - Нормировка на количество кластеров (они штрафовали за большое количество кластеров, т.к. основная задача сжать)

Это тоже график моим восстановлением, но если изначально разбивать не перцентилями, а кластеризацией, что было-бы более корректно, однако как вы видите отклонения весьма незначительные а прирост по времени от перцентилей очень значимый.

Выводы

Мне удалось не только решить все задачи на весьма хороший балл, но и придумать очень весёлое решение для C, кому интересно вот скоры

Моей основной и, даже, единственной проблемой было, то что я постоянно хочу улучшить свой базовый скор и забиваю на штрафы из-за этого я потерял свой топ 2, но зато улучшил алгоритм для Б и добавил разных эвристик!

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

А в остальном было очень очень круто! Спасибо яндексу за крутой и интересный контест!