iggisv9t channel

Вращайте барабан.

И попробовал убрать все вершины со степенью 1. Сильно лучше не стало, поэтому главный вывод что мне надо перестать мучать matplotlib и найти другой способ отрисовки всей этой ерунды.

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

Я кстати тоже не очень понимаю весь этот движ с графами Кэли (тут наверняка половина подписчиков о нём знает по соседним чатам) но внутри есть задачи выдумыавть новые укладки, детектировать симметрию и всё такое. Такие графы ведут себя сильно не похоже на привычные scale-free networks из каких-нибудь соцсетей.

А ёжик на очереди на такую же анимацию. Там как раз из-за других свойств графа читаемость в 3D лучше.

Отдельно начальная и конечная точка. Можно эту кашу разгребать по-разному. Очень хочется написать свой вариант force atlas на сфере или вложенных сферах, но не знаю когда руки дойдут. Ещё там была выше картинка с варлусом. Они решают эту проблему, тем что из каждой вершины рисуют укладку на новую сферу с центром в данной вершине. Как это переложить на графы с циклами — не понятно. Нужно городить эвристики.

Продолжаем кубики Рубика. Проблема такая, что force atlas конечно самую красивую картинку рисует, но кое-что искажается, а именно глубина шага. Решением кажется принудительно взять и расставить вершины на удалении от центра равном шагу. Кажется, берёшь просто и в полярных координатах оставляешь угол, а радиус заменяешь на глубину. Но получается читаемость хуже. Хотя честнее.

У меня есть пара идей на этот счёт, но пока в качестве PoC вот такое вот.

Что интересного видно — есть вершины которые force atlas прижимает к центру, хотя у них глубина максимальная для этого графа. Получается, это что-то типа противоположных состояний для кубика относительно исходного.

Теперь этот ёжик будет жить с нами

Об островках регулярности (или о миллионе двойных маятников)

Возьмём в диапазоне [-π, π] для θ₁ и θ₂ решётку двойных маятников, и посмотрим на их эволюцию (на рис. cos(θ₂)), демонстрирующую хаотическое поведение для достаточно больших энергий (чувствительны к начальным условиям).

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

P.S. сюжет появился в комментариях замечательного канала "человек наук", спасибо за вдохновение)
P.P.S. кстати это всего 20 строчек кода и около секунды вычислений, см. в комментариях)

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

Из забавного, но одновременно очевидного — первым делом я посмотрел на каких страницах у меня был самый большой visit_time (распределён он экспоненциально, кстати). Это оказались страницы типа meet.google.com и страницы которые оставались открыты пока я был afk. Ваш любимый товар — пакет.

База так себе документирована. Ну то есть доки или надо читать целиком, чтобы понять вообще всё, либо вообще не читать. И ещё они доступны в виде снапшотов на веб архиве только
https://web.archive.org/web/20210404095503/https://developer.mozilla.org/en-US/docs/Mozilla/Tech/Places/Database

Вот тут рассказывают как её найти
https://support.mozilla.org/en-US/kb/profiles-where-firefox-stores-user-data

К счастью там всё не очень сложно, догадки не с первого раза но после пары попыток оправдываются. Чтобы превратить историю в граф нужно поджойнить табличку moz_historyvisits на саму себя по по id и from_visit чтобы получить пару place_id источника и куда оттуда был переход. Ну и табличка с соответствием страниц всей остальной информации лежит отдельно.

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

Оказалось, что даже не надо придумывать специальных инструментов. Firefox хранит историю в sqlite базе и можно просто взять и вытащить из неё пару табличек и граф готов. Можно картографировать собственную деятельность, автоматически выделять области интереса и ключевые точки.

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

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

Раньше чтобы тебя не детектили системы как человека надо было носить одежду как справа. Теперь достаточно одежды как слева.

Я напомню что среди DSов есть секта:

ОБУЧЕНИЕ ВСЕ, вам достаточно сделать import openai и все. И почему они все ведут какие то курсы... На работу их не берут что ли...

А блогпост хорош, там есть краткий пересказ пеперов про force atlas и про barnes hut optimization (оригиналы очень рекомендую почитать всем кто шатает Gephi, очень легко читаются и проливают свет на детали реализации и настройку параметров), есть про сам протокол Bluesky, немного про всякие технические детали проекта. Про эмбеддинги можно было копнуть тему поглубже, потому что бывают и покруче. Я не устаю рекламировать в этом смысле ещё одного Антона.

Ну и самое обломное: нет никакого анализа, из чего состоит граф bluesky и что за кластера и всё такое. Может напишет в следующих сериях, а может надо самим шататать визуализацию https://aurora.ndimensional.xyz/ (у меня завелась только на одной машине из двух)

Мне тут упомянутый постом выше Антон прислал интересное https://joelgustafson.com/posts/2024-11-12/vizualizing-13-million-bluesky-users

Чувак скачал bluesky, составил граф из 13 миллионов юзеров, написал под него свой force atlas на zig и запилил даже инструмент. Потом фиганул в какие-то первые попавшиеся графовые эмбеддинги и пронал через UMAP.

Я как всегда прежде чем рассказывать про какую-нибудь штуку пытаюсь сам её испробовать. Так вот его тул для больших графов https://github.com/nDimensional/andromeda пока сыроват. Ну настолько, что у меня с ним граф на 3.4 Млн рёбер выглядит как на прикреплённой картинке.

С одной стороны я тоже захотел выучить zig, с другой если нужен именно force atlas на очень толстых графах, то есть https://cosmograph.app/run/

Эта картинка ждала 4 года

Невероятным образом, эта история канула в лету и не существует в канале (что странно и подозрительно), поэтому я ее продублирую.

N лет назад (>=4) мне написал читатель. В то время он был на стажировке в Берлине и изучал нервную систему осьминогов и рассказывал интересную байку из своей области.

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

Думали, как это проверить и придумали: давайте наденем на осьминога 3D-очки и будем показывать в 3D фотографию добычи. Если он отреагирует, значит бинокулярное (потому что в монокулярном это было бы не похоже на добычу, а просто на какие-то яркие цвета).

И в итоге да, осьминог отреагировал и так вроде бы как доказали, что у них бинокулярное зрение как и у нас. Но самое прекрасное — фото эксперимента (хоть тут и каракатица, но вроде бы зрительные системы у них очень похожи).

UPD: Оригинальная статья

Вы наверное знаете про межпланетную транспортную сеть?

Она красива и фундаментальна. Но не об этом пост.

Эта сеть является одним из великого множества примеров, где метрики (т.е. функции расстояния, коммутативные относительно своих двух аргументов) -- это неподходящий, неуклюжий инструмент.

Лететь по траектории от планеты А к планете Б -- это вовсе не одно и то же, что лететь по этой же траектории в противоположном направлении от Б к А.

Метрики работают лишь в очень простых постановках, в линеаризируемых масштабах.

Хороший повод вспомнить Walrus. Он как раз для графов которые в стороны быстро разрастаются. Жаль он давно заброшен
https://t.me/sv9t_channel/292

Должно быть вот так. Это опять кубик 2х2х2, но теперь один угол зафиксирован, то есть разрешены только 6 ходов из 12. Глубина 8. Т.к. графовые укладки придумывали для совсем других графов, я подумал, что тут можно что-то своё сочинить. Каждому повороту я присвоил смещение по одной из координат и так расположил точки. Чтобы разные состояния не склеивались, я добавил маленькое смещение как функцию от состояния. Какие из этого делать выводы пока не знаю.

Скопировал код со стековерфлоу и словил забавные глитчи. Много лет назад наступал на эту граблю, когда числа из имён файлов (тут номера кадров) сортируются в алфавитном порядке (1, 10, 11, 2 ..)

А вот если взять глубину 6, и потом по матрице смежности пройтись с окном в 500. То есть каждый пиксель — это сумма квадратика со стороной 500. (правда тут циклическая палитра, чтобы красивее было)

Без фокусов визуализировать не получится, т.к. у неё сторона 247044 и надо массив такого размера аллоцировать в явном виде.

Вот вам BFS кубика Рубика 2х2х2 на глубину 4. Если дальше, то получается уже совсем каша

UPD: engrafo который использовался для конвертации из tex в html внутри arxiv vanity тоже не смог прожевать конкретно эту таблицу. Так что скорее всего сам инструмент работает, просто исходники статьи кривоваты.

Ӭ̶̫͓͍͖̙̫͇̘́̂̄̈̅́͐́̀̍̽͘̚̚͜т̶͚̲̖̰͙̱̻̫͉̤̦͌̌͑́̈́͋̄̂̈̕ͅ ͜о̶͑ ̌͋̃̍̍ ̧̨͍̘̥̫̬̠͓̩͉̞̮̺̀̆̉͘͠ ̴̯̪̜̠̯͋͗̑̃͐͜ͅя̵͈̈ ͕̘͚̗ ̴͗̅̉̈́̋̇̑́̅͘ ̹̣̪̓̈́̚п̸̞̰͎̺͓͈͑ ̙͎о̶̐̉̆̆̈́̚͝͝͠͝ ̯̱͍̈́̍п̴̲̰͖̜̇̆̈̉͋̑̐̽̄͘͠ ̩р̵̀̈́̃̍ ̡̹̩͚о̵́̋̎̚ ̡̧̢̯̀̒̒͌̃̈́̍͋͗̂͜͜б̷̢̹͌̅͝о̴͋̋̑͋͂͐́̍̈́̇̕ ̭̩͍̥ͅв̴̡̹͚̠̺͉̫̜̒̈́̋̓͝а̶̢̧͇̖̦̍̆̈́̈́̌͐̈́́л̵͗ ̡̙̼̟̥̦̙͔̺̱̖̜̼̠̆̂͑͊̉ https://github.com/michal-h21/tex4ebook чтобы читать пеперы с arxiv на читалке. На самом деле до этого надо было ещё повозиться и на ходу выяснять каких зависимостей ему не хватает.

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

Есть ещё вот такая штука https://github.com/soumik12345/Arxiv2Kindle — она отработала гладенько, но на выходе всё-таки pdf, хотя с мелкой страницей, которая должна норм рендериться целиком на читалке. Если компилить tex в epub так и не получится, то в принципе приемлемый вариант.

Желание разложить что-угодно по группам на основе схожести - естественная черта человека, но задача кластеризации данных, почти всегда как плохое ТЗ для дизайнера - делай красиво, а не красиво не делай. Какой алгоритм кластеризации хороший, а какой плохой если сравнивать результат их работы не с чем? Джон Клейнберг из Корнеллского университета в 2002 году сформулировал три критерия хорошего алгоритма кластеризации:

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

В своей работе "Теорема о невозможности кластеризации" Клейнберг доказывает что никакой алгоритм кластеризации не может удовлетворять одновременно трем названным условиям. Масштабная инвариантность нарушается когда для определения принадлежности точки к кластеру используются относительные расстояния с заданным порогом. Насыщенность нарушается, если заранее фиксируется количество кластеров. Согласованность нарушается когда для объединения точек в кластеры используются абсолютные расстояния не превышающие некоторый порог. С другой стороны указанные критерии это субъективное представление о красивом/полезном разбиении множества на группы, с которым необязательно соглашаться. Максимально понятно, без математики, теорема описана тут.

https://www.youtube.com/watch?v=VclIzvFnuZM

Все кругом рекомендовали читать "задачу трёх тел" и две последующие книги. Я сдался и вот уже третью книгу читаю. И вот что интересного вспомнил.

Как проверить, что мы живём в трёхмерном пространстве, а не просто застряли на маленьком кусочке в более высокоразмерном пространстве? Вот есть в физике всякие законы взаимодействий. И там всюду в знаменателе квадрат расстояния. Вот представим себе окружность и из центра проведём до неё линии с одинаковым углом между ними. То, сколько линий пересечёт сегмент окружности будет линейно зависеть от расстояния до центра. А если проделать то же самое со сферой, то плотность точек пересекающий кусок её поверхности убывает уже с квадратом расстояния. Если взять четырёхмерную сферу, то там плотность силовых линий будет убывать ещё быстрее. Так что если мы заметим, что какие-то силы убывают быстрее, чем с квадратом расстояния, то всё. Но такого пока не наблюдается. (хотя говорят, что на очень малых масштабах такие приколы могут происходить.
На самом деле я пересказал вам вот это https://sly2m.livejournal.com/587768.html — там чуть по подробнее но таким же простым языком.

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

https://t.me/kwsddump/1607

http://www.datagenetics.com/blog/september32012/index.html

И ещё вот такую штуку можно вспомнить

https://mespadoto.github.io/proj-quant-eval/post/projections/

Ребята прогнали кучу снижалок размерности на куче датасетов.

Статья топчик. Хотя кажется, недоумения и споры о нелинейных методах снижения размерности никогда не прекратятся всё равно.

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

Когда признаки уж слишком разношёрстные, а посмотреть на данные как на картинку всё равно хочется -- можно использовать автоэкодеры. Одна только беда -- с ними ещё важнее понимать что делаешь, иначе выйдет полнейший нонсенс. Зато можно подобрать достаточно хорошие параметры для представления и даже можно зашить в лосс дополнительные условия. Я вот когда-то приделывал KL-divergence в лосс чтобы было чуть-чуть похоже на tSNE.

Напоследок -- кроме широко известного UMAP есть очень шустрый ncvis, или если хотите на GPU то можно попробовать trimap.

И совсем последнее. Когда-то мы с Антоном (@epsiloncorrect) и ребятами из ncvis начинали делать бенчмарк всяких таких методов, но так и не закончили. Если у кого-то чешутся руки, то можете подхватить.

Написала небольшую статью на Хабре про алгоритмы снижения размерности, жду ваших классов 👍:

https://habr.com/ru/articles/811437/

В дополнение к статье рекомендую посмотреть вот эту замечательную демонстрацию работы UMAP и t-SNE (уже не моего производства): https://pair-code.github.io/understanding-umap/

#математика_в_ML #учебные_материалы