У LLM в каждой конкретной версии размеры матриц вполне себе фиксированные, так что с этим проблем нет. Тензорные ядра тоже без дела не сидят. Штрассен же рекурсивный, сводит задачу к нескольким другим в 2 раза меньше, а для достаточно маленьких задач дальше на рекурсию слишком много ресурсов тратится, и быстрее в лоб (через тензорные ядра). Это как в сортировках на C++ и Java - они гибридные: как только в рекурсивной сортировке размер кусочка массива становится маленьким (скажем, до 10-16 элементов) - становится быстрее сортировать вставками, чем дальше делить рекурсивно пополам. В умножении матриц проблема скорее в том, что размер этого переходного маленького кусочка слишком большой для текущих размеров LLM.
У вас просто LLM (Little Language Models) слишком маленькие. Вот будут видеокарты на пару терабайт памяти - Штрассен будет быстрее.
А если серьезно - Штрассен вполне обгоняет умножение в лоб где-то на размерах матриц 1000 на 1000 на CPU в один поток. Но Штрассена проблематично распараллеливать на видеокартах, и видимо пока с этим никто особо не заморачивается - проще через тензорные ядра в лоб числа молотить.
Это в базовой куче. Если завести массив отслеживания позиций элементов в куче (в код кучи вносится модификация - при каждом свапе элементов этот массив корректируем) - то можно вполне быстро.
А это n-мерное пространство сейчас с нами в одной комнате?
Это математическая абстракция. Декарт в свое время придумал декартовы координаты как способ работы с алгебраическими уравнениями на геометрической плоскости. До Декарта вот этих осей абсцисс и ординат не было, и у точек координат тоже не было. Оказалось удобно. А потом понеслось... а если в уравнении переменных не 2, а 3? а если вообще n?
Лучше всего для психического здоровья работать с n-мерным пространством как с набором точек, у которых n координат. Представлять себе только 3-мерное пространство, про n-мерное думать "ну там наверно всё выглядит примерно аналогично".
Если герой этой статьи на Хабре нашел как запихать много сфер в n-мерное пространство, думаю, несложно будет адаптировать его находку к тому, чтобы запихать много "шапочек" на n-мерную сферу.
Ну как, 1 байт - это точка в 8-мерном пространстве, а именно вершина 8-мерного единичного гиперкуба. Машинное 32-битное слово aka int в C++ - точка в 32-мерном пространстве. Блоки бит корректировать эффективнее, чем каждый бит по-отдельности. Например, кодом Хэмминга.
Коды коррекции ошибок такие - "ну да, ну да, пошли мы нафиг". Всем же известно, что упаковка сфер полезна только с трёхмерном пространстве - арбузы на рынке в пирамидки складывать. А то, что, скажем, плотность передачи данных по вайфаю можно будет раз в 100 увеличить - это никому не нужно.
Это вопрос к Хабру, наверно. У меня формулы внутри текста в разных браузерах вообще везде разные: в Edge непомерно большие, в Яндекс-браузере на телефоне непомерно маленькие. При всём при этом в режиме редактирования статьи размеры формул везде идеально как надо.
У меня задача получилась эквивалентная такой. На примере тернарного случая: нужно посчитать количество способов расставить в кубе 3х3х3 числа от 1 до 3 так, чтобы в каждом ряду (из 3х элементов), параллельному оси x, была ровно одна единица, в каждом ряду, параллельному оси y, была ровно одна двойка, и в каждом ряду, параллельному оси z, была ровно одна тройка. Для кватернарного случая это будет уже гиперкуб 4х4х4х4, числа от 1 до 4, направлений осей 4. Ну и так далее.
Вот эти ваши "дефекты" по сути кодируют положения всех единиц, где цвет - это номер слоя, в котором эти единицы располагаются. Как только мы зафиксировали положения единиц, задача распадается на X независимых - нам нужно посчитать для каждого слоя (или "гиперслоя" при X>3) количество способов расставить там остальные числа, после чего количество этих способов по всем слоям перемножить (это по сути функция Ф). Ну и ответом будем сумма способов по всем "дефектам".
Из ограничений выше следует, что в каждом гиперслое единиц должно быть поровну, иначе числа для других осей в этот гиперслой не поместятся. То есть в тернарном случае в каждом слое должно быть по 3 единицы, в кватернарном - по 16 (там гиперслои - это кубы 4х4х4). Так повезло, что для каждой расстановки трех единиц в одном слое в тернарном случае дальше способов заполнить либо 2, либо 0 (если расстановка этих трех единиц в один ряд). В кватернарном случае, боюсь, будет все сложнее, и просто умножением на степень двойки не отделаться.
Итого количество "дефектов" для кватернарного случая равно 64! / (16!)^4, что довольно много, поэтому объединять их в классы эквивалентности - хорошая идея. Но что-то классов эквивалентности тоже пока получается много)
3. В качестве представителя можно взять лексикографически максимальный по всем эквивалентным объектам. Представителей всех классов эквивалентности (а значит и сами классы) можно найти перебором с отсечениями. Просто генерируем элементы объектов в порядке учета их в лексикографическом порядке, применяем действия группы, если удалось перемешать элементы объекта так, что получился объект лексикографически больше - то окатываемся.
4. Можем. Для этого надо представить каждый элемент группы в виде последовательности базовых действий группы. Например, для куба 4х4х4: сначала вращение, потом перестановка слоев по оси x, потом по оси y, потом z. Теперь, пусть мы повращали и переставили слои по оси x. Тогда дальше у нас будут переставляться только блоки из 4 элементов. Но если множество этих блоков не совпадает с множеством блоков начального куба, то смысла их переставлять нет - там нет элементов стабилизатора.
Ну или можно глубже вникнуть в структуру группы. Например, для группы всех перестановокмощность стабилизатора для объекта(состоящего изэлементов), на который действует группа, равна произведению факториалов размеров подмножеств одинаковых элементов в.
У меня еще есть непонятки по прочитанному. Я у себя в голове немного другую модель задачи построил, она на изложенную в статье не до конца накладывается. Например, мне не до конца понятно почему для последних двух линий (двух "гиперслоев" в кватернарном случае) надо домножать на какую-то фиксированную степень двойки. У меня двойки для тернарного случая вылезают из функции Ф.
Если что, я свою модельку закодил, и она тоже дает 10752 для тернарного случая. Но наверно поля комментария будут "слишком узки", чтобы расписывать ее во всех подробностях.
Из всего, что здесь написано, интерес представляют идеи использования дробных и отрицательных чисел в некоторых местах. Но, думаю, математики уже давно додумались до применения такого в своих задачах.
Лупа и Пупа пошли получать зарплату. Лупа получил кучу денег, а Пупа — только одну купюру.
— Что случилось? — спросил я. — Один из тех несчастных случаев на производстве, — сказал он.
Я никогда не мог заставить его рассказать об этом подробнее.
Он просто сказал: «Один из тех».
Элементарное означает, что в нём используются только понятия и прочие инстументы, не выходящие за пределы школьной программы (без всяких лютых «высших» математик), хотя оно может быть довольно большим и его будет не так просто понять.
Это примерно как переписать программу без использования сторонних библиотек.
Это разные задачи. В теореме о четырёх красках граф планарный (точнее, плоский), то есть его можно нарисовать на плоскости так, чтобы ребра, изображенные в виде кривых, не пересекались. Здесь же граф единичный расстояний — т.е. рёбра могут пересекаться как угодно, главное чтобы при изображении на плоскости длины всех рёбер были равны единице.
У LLM в каждой конкретной версии размеры матриц вполне себе фиксированные, так что с этим проблем нет. Тензорные ядра тоже без дела не сидят. Штрассен же рекурсивный, сводит задачу к нескольким другим в 2 раза меньше, а для достаточно маленьких задач дальше на рекурсию слишком много ресурсов тратится, и быстрее в лоб (через тензорные ядра). Это как в сортировках на C++ и Java - они гибридные: как только в рекурсивной сортировке размер кусочка массива становится маленьким (скажем, до 10-16 элементов) - становится быстрее сортировать вставками, чем дальше делить рекурсивно пополам. В умножении матриц проблема скорее в том, что размер этого переходного маленького кусочка слишком большой для текущих размеров LLM.
Хотя не, Штрассена и даже чего побыстрее для GPU и TPU можно написать так, чтобы он обгонял умножение в лоб.
Итого Штрассен на 20% быстрее, чем cuBLAS, на матрицах 20к на 20к (не вчитывался, если честно, что там в плане погрешностей и устойчивости).
У вас просто LLM (Little Language Models) слишком маленькие. Вот будут видеокарты на пару терабайт памяти - Штрассен будет быстрее.
А если серьезно - Штрассен вполне обгоняет умножение в лоб где-то на размерах матриц 1000 на 1000 на CPU в один поток. Но Штрассена проблематично распараллеливать на видеокартах, и видимо пока с этим никто особо не заморачивается - проще через тензорные ядра в лоб числа молотить.
Думаю, в видеоиграх нужно запретить проигрыши, поскольку это может быть обидным.
Это в базовой куче. Если завести массив отслеживания позиций элементов в куче (в код кучи вносится модификация - при каждом свапе элементов этот массив корректируем) - то можно вполне быстро.
Ох уж этот Геданкен.
Это математическая абстракция. Декарт в свое время придумал декартовы координаты как способ работы с алгебраическими уравнениями на геометрической плоскости. До Декарта вот этих осей абсцисс и ординат не было, и у точек координат тоже не было. Оказалось удобно. А потом понеслось... а если в уравнении переменных не 2, а 3? а если вообще n?
Лучше всего для психического здоровья работать с n-мерным пространством как с набором точек, у которых n координат. Представлять себе только 3-мерное пространство, про n-мерное думать "ну там наверно всё выглядит примерно аналогично".
Если я буду подробно все расписывать - получится статья на 20 экранов)
Вот я нашел другую статью с видео на 7 минут, в которой на пальцах поясняется суть: Контактное число шаров и сферические коды / Этюды // Математические этюды
Если герой этой статьи на Хабре нашел как запихать много сфер в n-мерное пространство, думаю, несложно будет адаптировать его находку к тому, чтобы запихать много "шапочек" на n-мерную сферу.
Придумано, и много, но уже отнюдь не для начинающих Maximum flow problem - Wikipedia
Ну как, 1 байт - это точка в 8-мерном пространстве, а именно вершина 8-мерного единичного гиперкуба. Машинное 32-битное слово aka int в C++ - точка в 32-мерном пространстве. Блоки бит корректировать эффективнее, чем каждый бит по-отдельности. Например, кодом Хэмминга.
Коды коррекции ошибок такие - "ну да, ну да, пошли мы нафиг". Всем же известно, что упаковка сфер полезна только с трёхмерном пространстве - арбузы на рынке в пирамидки складывать. А то, что, скажем, плотность передачи данных по вайфаю можно будет раз в 100 увеличить - это никому не нужно.
У меня в одном браузере так (Edge)
В другом так (Firefox)
В третьем так (Яндекс на телефоне)
В режиме редактирования в Edge так
Явно с размерами формул что-то нездоровое происходит
Это вопрос к Хабру, наверно. У меня формулы внутри текста в разных браузерах вообще везде разные: в Edge непомерно большие, в Яндекс-браузере на телефоне непомерно маленькие. При всём при этом в режиме редактирования статьи размеры формул везде идеально как надо.
UPD. Написал в техподдержку, может поправят.
У меня задача получилась эквивалентная такой. На примере тернарного случая: нужно посчитать количество способов расставить в кубе 3х3х3 числа от 1 до 3 так, чтобы в каждом ряду (из 3х элементов), параллельному оси x, была ровно одна единица, в каждом ряду, параллельному оси y, была ровно одна двойка, и в каждом ряду, параллельному оси z, была ровно одна тройка. Для кватернарного случая это будет уже гиперкуб 4х4х4х4, числа от 1 до 4, направлений осей 4. Ну и так далее.
Вот эти ваши "дефекты" по сути кодируют положения всех единиц, где цвет - это номер слоя, в котором эти единицы располагаются. Как только мы зафиксировали положения единиц, задача распадается на X независимых - нам нужно посчитать для каждого слоя (или "гиперслоя" при X>3) количество способов расставить там остальные числа, после чего количество этих способов по всем слоям перемножить (это по сути функция Ф). Ну и ответом будем сумма способов по всем "дефектам".
Из ограничений выше следует, что в каждом гиперслое единиц должно быть поровну, иначе числа для других осей в этот гиперслой не поместятся. То есть в тернарном случае в каждом слое должно быть по 3 единицы, в кватернарном - по 16 (там гиперслои - это кубы 4х4х4). Так повезло, что для каждой расстановки трех единиц в одном слое в тернарном случае дальше способов заполнить либо 2, либо 0 (если расстановка этих трех единиц в один ряд). В кватернарном случае, боюсь, будет все сложнее, и просто умножением на степень двойки не отделаться.
Итого количество "дефектов" для кватернарного случая равно 64! / (16!)^4, что довольно много, поэтому объединять их в классы эквивалентности - хорошая идея. Но что-то классов эквивалентности тоже пока получается много)
По некоторым пунктам:
3. В качестве представителя можно взять лексикографически максимальный по всем эквивалентным объектам. Представителей всех классов эквивалентности (а значит и сами классы) можно найти перебором с отсечениями. Просто генерируем элементы объектов в порядке учета их в лексикографическом порядке, применяем действия группы, если удалось перемешать элементы объекта так, что получился объект лексикографически больше - то окатываемся.
4. Можем. Для этого надо представить каждый элемент группы в виде последовательности базовых действий группы. Например, для куба 4х4х4: сначала вращение, потом перестановка слоев по оси x, потом по оси y, потом z. Теперь, пусть мы повращали и переставили слои по оси x. Тогда дальше у нас будут переставляться только блоки из 4 элементов. Но если множество этих блоков не совпадает с множеством блоков начального куба, то смысла их переставлять нет - там нет элементов стабилизатора.
Ну или можно глубже вникнуть в структуру группы. Например, для группы всех перестановок
мощность стабилизатора для объекта
(состоящего из
элементов), на который действует группа, равна произведению факториалов размеров подмножеств одинаковых элементов в
.
У меня еще есть непонятки по прочитанному. Я у себя в голове немного другую модель задачи построил, она на изложенную в статье не до конца накладывается. Например, мне не до конца понятно почему для последних двух линий (двух "гиперслоев" в кватернарном случае) надо домножать на какую-то фиксированную степень двойки. У меня двойки для тернарного случая вылезают из функции Ф.
Если что, я свою модельку закодил, и она тоже дает 10752 для тернарного случая. Но наверно поля комментария будут "слишком узки", чтобы расписывать ее во всех подробностях.
Ну норм группа, похожие штуки уже давно придуманы и даже используются на практике
https://ru.wikipedia.org/wiki/Нумерация_Гёделя
https://ru.wikipedia.org/wiki/Гладкое_число
https://ru.wikipedia.org/wiki/Алгоритм_Диксона
Из всего, что здесь написано, интерес представляют идеи использования дробных и отрицательных чисел в некоторых местах. Но, думаю, математики уже давно додумались до применения такого в своих задачах.
Но ведь можно было дать рандомное лечение только одному ребенку, в итоге получить одну смерть с вероятностью 50%, и 0 смертей тоже с вероятностью 50%.
— Что случилось? — спросил я. — Один из тех несчастных случаев на производстве, — сказал он.
Я никогда не мог заставить его рассказать об этом подробнее.
Он просто сказал: «Один из тех».
Это примерно как переписать программу без использования сторонних библиотек.