​​#statistics

Прекращайте использовать метод локтя в k-means.

Так называется недавно вышедшая статья от автора из университета Дортмунда. Немного кликбейтный заголовок, но статья весьма интересная.

Итак, как выглядит метод локтя?

1. Строим много кластеризаций k-means с разным количеством k;
2. Для каждого отдельного k считаем сумму квадратов внутрикластерных расстояний до центра кластера (within-cluster sum of squares, WCSS). Для sklearn это будет атрибут inertia_.
3. "На глаз" выбираем такое k, где у нас происходит "перегиб" (отсюда и метод локтя) и WCSS перестает существенно уменьшаться. Это и будет итоговым числом кластеров k.

У такого метода есть один некоторые минусы, например, выбор k "на глаз". Потому в разных работах предлагались методы автоматизации метода локтя.

Как можно улучшить метод?

1. Jump method. Давайте искать максимум SSE_k ** -Y - SSE_k ** -Y, где степень Y может варьироваться, но авторы предлагают брать Y=1/2 * dimensionality (то есть половина от размерности пространства признаков).
2. L-method. Возьмем две линейных функции (перед перегибом и после). Выберем лучшую кусочно-линейную аппроксимацию.
3. Kneedle algorithm. Возьмем полиномиальную кривую (сплайн), нормализуем от 0 до 1. Сравним с диагональю. Берем последний максимум перед задаваемым threshold.
4. Улучшение шага 3. Давайте искать максимум для SSE_k-1 - SSE_k / (SSE_k - SSE_k+1) - 1.
5. В библиотеке pyclustering используется метод ElbowLen, которые считается (x_k*(y_0 - y_1) + (x_1 - x_0)*y_k + (x_0*y_1 - x_1*y_0)) / (sqrt((x_1 - x_0)**2 + (y_1 - y_0)**2)), где x0, x1, y0, y1 - минимумы и максимумы графика.
6. AutoElbow. Вычисляем ((x_k - 1)**2 + (y_k - 1)**2) / (x_k ** 2 * y_k **2) на нормализованном на [0,1] графике.

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

Мы можем отойти от эвристик над методом локтя и прочих геометрических манипуляций в сторону вариационных методов (предполагается, что они более теоретически обоснованы). В статье по ним проходятся весьма поверхностно, так что некоторые из них я не совсем понял ¯\_(ツ)_/¯

1. Variance Ratio Criterion (VRC). Считаем ((SSE_1 - SSE_k) / (k - 1)) / (SSE_k / (n-k)). Авторы рассматривают это, как некий аналог F-статистики.
2. Метод Mariott. Рассматривается детерминант ковариационной матрицы |W|.
3. KL-index. Давайте рассмотрим DIFF_k = (k - 1)**(2/p)*SSE_k-1 - k**(2/p)*SSE_k. Потом ищем максимум KL(k) = |DIFF_k / DIFF_k+1|.
4. Метод Pham. Считаем SSE_k / (alpha_k * SSE_k-1), где alpha_2 = 1 - 3/(4*d) и alpha_k = 5/6 * alpha_k-1 + 1/6 (что моделирует ожидаемое изменение равномерного распределения).

Учитывая задачу кластеризации, можно придумать и критерии, основанные на расстояниях.

1. DUNN index.
2. David-Bouldin index.
3. Silhouette score.

Но это не все. Мы еще можем использовать теоретические подходы, основанные на теории информации.

1. Bayesian information criterion (BIC).
2. Akaike Information Criterion (AIC).

Ну и, напоследок, еще можно использовать симуляционный критерий.

1. В данном случае, мы считаем GAP_k = E[log(SSE'_k)] - log(SSE_k). И выбираем наименьший k, где GAP_k >= GAP_k-1 - std_k+1. Где SSE'_k - базовый SSE, а std_k+1 - среднеквадратичное отклонение оценок.

А какой итоговый вывод?

Не использовать метод локтя. Предпочитаемыми методами авторы считают VRC (реализация sklearn), Bayesian Information Criterion (BIC) (материал с реализацией) или симуляционный критерий (GAP-статистику, материал с реализацией).

#dl #nlp

Design distributed cache

Хочется порекомендовать замечательный youtube-канал System Design Interview. Автор вещает на понятном русском английском :)

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

Например, видео о Distributed Cache. Автор не пытается сразу городить вундервафлю, выдавая готовое решение. Как и следует делать всегда при создании системы, сначала автор описывает проблему и рассуждает, чего мы хотим добиться, применяя кеш, какие есть функциональные и нефункциональные требования.

Всё достаточно просто, локальный кеш, LRU – алгоритм, применяемый для вытеснения данных при переполнении кеша. Дальше – интереснее, появляется распределённая система, и этот distributed вносит проблемы. Рассматриваются dedicated и co-allocated кластеры, способы управления кластером, какие алгоритмы применяются для распределения данных по шардам, их плюсы и минусы.

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

Вопрос, который не освещается в видео, но заслуживает внимания – прогревания кеша. Что делать при старте, когда кеши пустые?

P.S. У этого канала интересная история. Автор выпустил десяток добротных видео, получил много приятных отзывов и пропал на два года. Потом вернулся и сказал, что все это время готовил полноценный курс и не отвлекался. У нас пока руки не дошли посмотреть более подробно, но должно быть интересно.

#youtube #skills #резюме

#dl #cv

​​Attending To Graph Transformers

by Luis Müller, Michael Galkin, Christopher Morris, and Ladislav Rampasek

arxiv

Our new survey on Graph Transformers (GTs) adjoined by some “mythbusting”.

We come up with categorization of GTs according to 4 main views:
🗺️ used Encodings,
🌐 expected Input Features (geometric or non-geometric),
✨ Tokenization (nodes, nodes+edges, subgraphs), and
🧮 Propagation (fully-connected, sparse, hybrid).

We investigate 4 common expectations and claims about GTs. Although conclusions are more nuanced (see the paper), we label them with pretentious badges ✅ Confirmed / ❌ Busted / 🤔 Plausible

1️⃣ Are GTs theoretically more expressive than GNNs?

❌ Busted. There is no inherent property of GTs that makes them more expressive. Instead, their expressivity stems from their positional/structural encodings. (And making those maximally expressive is as hard as solving the graph isomorphism problem.)

2️⃣ Can graph structure be effectively incorporated into GTs?

✅ Confirmed. GTs can identify graph edges (easy task), count triangles (medium), and distinguish regular graphs (hard task). But there is still room for improvement.

3️⃣ Does global attention reduce over-smoothing?

🤔 Plausible. In heterophilic graphs, GTs clearly outperform vanilla GNNs but still lag behind specialized SOTA models. Maybe we need a different structural bias?

4️⃣ Do GTs alleviate over-squashing better than GNN models?

🤔 Plausible. The Transformer perfectly solves NeighborsMatch where GNNs struggle. However, this is a synthetic “retrieval” task that doesn’t test (sub)graph representation.

🎁 Bonus: Attention matrices contain meaningful patterns and explain GT performance.

❌ Busted. We couldn’t find any strong interpretability of attention scores for downstream tasks. We suggest following Bertology in NLP that moved from dissecting attention to designing benchmarks.

Подборка материалов по ускорению работы таблиц на кликхаусе

Паттерны работы с кликом

Интересный паттерн клика - не надо бояться больших таблиц. Действительно больших) и здесь на первое место по оптимизации выходят такая штука как кодеки сжатия столбцов.

Видео про оптимизацию больших таблиц
Хорошая статья altinity про кодеки и lowcardinality
Методика тестирования различных кодеков

Как сблизиться с командой? Памятка для руководителей и эйчаров

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

1️⃣ Интересуйтесь состоянием сотрудников. Оторвитесь от работы и спросите у коллеги, как дела. Сделайте это, даже если вам неловко, — в этом и заключается лидерство. Только не стоит навязывать разговор, если человек не хочет. Главное, чтобы каждый мог свободно рассказывать о наболевшем при необходимости.

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

3️⃣ Поощряйте сотрудников отдыхать. Больше четверти людей не уходят в отпуск больше чем на четыре дня, а абсолютное большинство по итогам года не отгуливает отпуск целиком. Проблема в том, что отпусками и отгулами пренебрегают сами руководители. В компаниях, где руководители спокойно отрываются от работы, чтобы восстановить силы, сотрудники следуют их примеру.

4️⃣ Постарайтесь увидеть человека в каждом сотруднике. Многие компании декларируют подобные ценности на бумаге, но на практике руководители и эйчары часто фокусируются на совсем других вещах. Хотя практика показывает, что люди со здоровой психикой активнее вовлекаются в работу и в конечном итоге приносят больше пользы бизнесу.

🔗 Как обстановка на работе отражается на психическом здоровье — смотрите по ссылке

тревожный эйчар | психологическая поддержка команд

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

#Жека #machinelearning

О проекте, который надо было убить
#ml #career #fail #coolstorybob

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

Немного предыстории для контекста. Пришёл я в текущую компанию в апреле 2020, как раз как лохдаун обьявили, а дочке исполнилось 4 месяца.  Работа с дивана, порой дитё подсовывают, когда дебажишь, поначалу по 5 звонков в день, чтоб во все вникнуть, доступов еще нет, мак не привезли из-за бешеного спроса во время ковида – в-общем, было весело. Пришел синьором, а подопечных всего трое, причем неформально, и двух из них я скоро потерял. Девушка-миддл, которая меня вводила в курс дела, почти сразу ушла недели на 3 в бёрнаут, еще полгода мучалась и в итоге уволилась (у нее ADHD, а ковидное одиночество привело к бессоннице и куче проблем со здоровьем) - планировала изучать мозг, чтоб лучше понимать, что у нее самой в мозгу происходит. А толкового пацана-джуна продолбали сами, ему два раза продлевали временный контракт, и по закону Нидерландов с 3-го раза обязаны были дать постоянный, а одобренного бюджета на это не было. И так я остался на время с одной индусской, которая топ, но все же.

Один из проектов, который я перенял – LaQua, language quality assessment, эдакий PoC (proof of concept), затянувшийся на полтора года. Примерно в 10% случаев ревьюеры отшивают статьи из-за низкого качества языка, и хочется автоматически находить совсем уж дико написанные статьи. К тому же, одна из схем монетизации – можно подсветить плохо написанные абзацы и посоветовать обратиться к сервису proof-reading. На момент моего прихода бизнес-ожидания были колоссальные, хотели что-то типа научной версии Grammarly, был, конечно, и mismanagement, т.к. сильно доверились синьору, который был до меня и неплохо так наломал дров (чувак – с синдромом Ph.D.-гая, даже по оставшимся от него тикетам было видно, что он только и делал что архив читал, а про прод и Валуе (аминь!) не особо думал).

Еще проверка гипотезы затянулась, т.к. уж больно хорош, как кажется, датасет – сотни тысяч статей, прошедших через сервис по пруф-ридингу, т.е у нас было много пар вида “оригинальное предложение; его поправленная версия”. Пришел, чекнул, что есть, как seq2seq задача совсем не заводилась, ладно, пытаемся зафайнтюнить SciBERT на бинарную классификацию "хорошее vs. плохое предложение”. И тут я понимаю, что все что чуваки делали работает примерно на уровне шума. За месяц проверил сам пару гипотез (хотелось как регрессию решить, предсказывать левенштейна, т.е. как сильно надо поправить оригинальный параграф), и устроил внутри команды своего рода Толоку из Экселя, палок и изоленты – быстро чекнули гипотезу, что мы сами вообще можем отличить хорошие параграфы от плохих. На выходе - 60% точности (если подсвечиваем параграф текста как плохой, это только на 60% верно), да еще и black box.

Идей, конечно, много было, там и Grammarly опубликовали свой алгоритм, да и просто крутая тема (у Grammarly, говорят, в проде не нейронки, но тссс….). Но все же если фэйлить, то надо быстро. Вот я и собрал всех оунеров, менеджеров, представился, и донес до них, что наши попытки пора прикрыть и лучше переключиться на оценку сторонних решений типа Grammarly. То есть я рекомендовал не полностью прибить проект, а просто купить продукт, вместо того, чтоб парой джунов и одним синьором сделать его с нуля. Зашло неплохо, удивился, как адекватно это воспринял и мой менеджер, и прочие. Такой вот конструктивно-негативный опыт, вроде и фэйл, но вроде и нет. Вывод: всегда надо держать в уме вариант, что проект, который ты сейчас тащишь, воообще-то может быть выгодно прибить. И хорошо бы иметь весомые аргументы, чтоб (самому себе) объяснить, почему проект должен существовать. Конечно, когда дают свободу делать PoC, все не так жестко, но тем не менее, надо понимать, что вместо текущего исследовательского проектика ты вообще-то можешь делать другой, потенциально очень прибыльный.