iggisv9t channel

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

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

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

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

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

Хороший повод вспомнить 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 #учебные_материалы