Комментарии 19
Попарный древовидный алгоритм сложения (из предыдущего пункта статьи) показался мне более простым, чем алгоритм Кэхэна.
Недавно, на Хабр был перевод "Укрощаем суммы с плавающей запятой" с некоторыми сравнениями. Не то, что бы зело профессиональный, но познавательный.
Спасибо за ссылку! Там попарный древовидный способ указан как тратящий слишком много ресурсов на рекурсию. В случае слияния словарей рекурсия несущественна. Так как, на практике, более миллиона словарей сливать бессмысленно. А это всего около 20 вызовов.
А вот то, что алгоритм Кохэна оказался более точным - это интересно. В своих экспериментах я не стал его реализовывать, так как он гораздо медленнее и сложнее, чем попарное усреднение словарей. И требует больше памяти. И более сложно распараллеливается.
Там попарный древовидный способ указан как тратящий слишком много ресурсов на рекурсию.
У алгоритмов типа скалярного произведения (взвешенной суммы), большая доля ресурсов уходит на обмен кэш L1 с памятью и/или L2/L3. А поэтому параметру древовидный способ проигрывает алгоритму Кэхэна примерно раза два.
А вот то, что алгоритм Кохэна оказался более точным - это интересно.
Ни Вы (при обосновании потребностей), ни они (при создании тестовых наборов), не приводите чисел обусловленности:
Оценка относительной ошибки алгоритма Кэхэна:
![\frac{|E_n|}{|S_n|} \le \big[2\varepsilon + O(n\varepsilon^2)\big] \frac{\sum\limits_{i=1}^n |x_i|}{\left|\sum\limits_{i=1}^n x_i\right|}.](https://habrastorage.org/getpro/habr/upload_files/998/6ac/71d/9986ac71d0c0d6722af17ddfa7645b2e.svg)
Т.е. если Вы преобразовали np.float32() в np.float64(), а потом просумируете алгоритмом Кэхэна, то суммирование будет реализовано примерно с точностью 104 бита. Этого много, мало или достаточно?
Альтернативный вариант - тупое суммирование np.float128() с точностью 63 бита, может оказаться гораздо шустрее.
Альтернативный вариант - тупое суммирование np.float128() с точностью 63 бита, может оказаться гораздо шустрее.
PyTorch не поддерживает точность float128. Придётся велосипеды конструировать. Кстати, а почему у float128 точность 63 бита?
Т.е. если Вы преобразовали np.float32() в np.float64(), а потом просумируете алгоритмом Кэхэна, то суммирование будет реализовано примерно с точностью 104 бита. Этого много, мало или достаточно?
На практике оказалось, что попарное усреднение словарей (тем более, что оно делается сразу со словарями, а не по отдельным числам из разных словарей), сразу даёт существенную прибавку к точности работы нейросети.
Алгоритм Кохэна, наверное, ещё что-то улучшит, в особенности на сверхглубоких нейронных сетях, но на моих 16-ти слоях я не увидел смысла его делать.
Кстати, а почему у float128 точность 63 бита?
Злые языки говорят - спасибо АНБ. В 1979/1980, когда сделали MC68881/Intel 8087, оказалось, что один из возможных вариантов их использования - 64 битная арифметика (64 битный умножитель) на основе 80 битных плавающих чисел (binary80).
Сейчас эти binary80, обычно, хранят в 16 байтах.
... Усреднение с использованием метода PyTorch sum(). В нём, судя по всему, встроены специальные алгоритмы
ИМХО, под капотом numpy.sum(), который суммирует деревом с блоками по 128 чисел, которые ещё разбиваются по 8 для SIMD, т.е. эффективно блок дерева ≈16 чисел.
На практике оказалось, что попарное усреднение словарей (тем более, что оно делается сразу со словарями, а не по отдельным числам из разных словарей), сразу даёт существенную прибавку к точности работы нейросети.
Ну, в деле словарей, возможно так удобнее. Хотя, по два, или большему числу непонятно.
Особенно в случае, преобразования np.float32() в np.float64() для усреднения и последующего обратного преобразования. После этого преобразования имеем, 29 запасных нулевых бит, если у нас 1024 числа, а усредняемые числа изменяются не более чем в 0.5*10⁶ раз, то после обратного преобразования, средний np.float32() будет корректным округлением точного результата.
Алгоритм Кохэна, наверное, ещё что-то улучшит, в особенности на сверхглубоких нейронных сетях, но на моих 16-ти слоях я не увидел смысла его делать.
Вопрос философский, требующий конкретных оценок того, сколько бит надо. Есть вариант с math.fsum(), который является развитием Коэхэна, но не с двумя накопителями, а до 39 (для произвольных double, что бы обеспечить точное представление любой суммы, для данных полученых из np.float32, накопителей никогда не будет больше 6).
Я посмотрел в википедию и увидел, что float128 имеет 112 бит в мантиссе, а не 63. Что Вы всё-таки имели ввиду? Просто оговорка?
Нет, не оговорка. Единственно, что, и сравнительно шустро, и более менее доступно в быту это расширенная точность. Просто Numpy её почти всюду в документации обозначает типом np.float128 и только в паре мест раскрывает его подлинное имя np.longdouble. 😉
Да IEEE 754 определяет тип binary128 (в новом стандарте C23 для него, ну наконец то, завели тип float128_t), но его поддержка, на бытовом уровне, весьма и весьма ограничена и, чаще всего, программная, а не аппаратная (ну, кроме "монстров" SPARC, POWER и т.п.).
Но процессор ж "по умолчанию" это ж x86_64. Как и исторически неплохая поддержка типов языка C long double, Numpy np.longdouble (он же np.float128 для x86_64, поскольку в памяти он занимает 16 байт или 128 бит) неплохая. Опять же пока более менее шустрая аппаратная реализация.
Конечно, новые процессоры ARM, Nvidia GPU и т.п., уже весьма распространены, но пока ограничиваются binary16/32/64.
Ну, а если уж на ARM, Nvidia GPU брать программную реализацию четверной точности для вычислений, а не для ввода/вывода, то уж никак не binary128/binary256 от IEEE, а double-double и quad-double, которые построены на алгоритме Кэхэна и его производных.
Что-то значение ошибки не пойму.
Float64 0.0010030090270812563 -1.2397194382174348e-09Float32
PyTorch Sum() error: 0.001003009150736034 0.01188516616821289
Float32 PyTorch + error: 0.001003015786409378 0.6655693054199219
Float32 PyTorch TreeSum error: 0.001003009034320712 0.0
Итак, точное значение 0.001003009034320712. Тогда ошибка Float32 PyTorch + error будет (0.001003015786409378 - 0.001003009034320712) / 0.001003009034320712 = -6,7318323514133179611157240783682e-6, в процентах это примерно 0.00067%.
Ну и по другим тоже. Как получено значение, скажем, 0.6655693054199219 ?
Ну и чисто по теории что-то ошибка великовата. При одном сложении максимальная погрешность будет 2 в минус 23 от максимального слагаемого (один его младший бит). Если умножить на 1000, получим 0,00011920928955078125. Это 0.012%. Прилично, конечно, но не 0.67% все же. Причем 0.012% - это максимальная оценка, реально будет меньше...
А вообще, тема интересная, плюсую с удовольствием! )
Чуток занудства
Суть в том, что float32 (тип данных по умолчанию в PyTorch) имеет 23 бита для хранения цифр после запятой, это примерно 6-7 десятичных цифр.
Если быть точным, то 23 бита не после запятой, а всего значащих. Где там запятая - не важно, собственно, сам формат и называется "с плавающей запятой" :)
Float64 0.0010030090270812563 -1.2434497875801753e-12
Float32 PyTorch Sum() error: 0.001003009150736034 1.1920928955078125e-05
Float32 PyTorch + error: 0.001003015786409378 0.000667572021484375
Float32 PyTorch TreeSum error: 0.001003009034320712 0.0
Спасибо за найденную ошибку. Код исправил. Вот правильные цифры для 1/997. Карму поднял)
Да, ошибка уменьшилась. Но она, всё равно, самая большая для наивного суммирования и усреднения.
Если быть точным, то 23 бита не после запятой, а всего значащих. Где там запятая - не важно, собственно, сам формат и называется "с плавающей запятой"
В том-то и суть, что у формата с плавающей запятой запятая всегда на втором месте, поэтому можно говорить о фиксированном числе знаков после запятой.
В двоичном представлении на первом месте всегда единица, потом запятая. Поэтому эту единицу не хранят, а хранят именно знаки после запятой.
При одном сложении максимальная погрешность будет 2 в минус 23 от максимального слагаемого (один его младший бит). Если умножить на 1000, получим 0,00011920928955078125. Это 0.012%. Прилично, конечно, но не 0.67% все же. Причем 0.012% - это максимальная оценка, реально будет меньше...
Дело в том, что одно из слагаемых постоянно растёт, поэтому ошибка при каждом последующем сложении увеличивается. Поэтому нельзя ошибку просто умножить на 1000. Фактически, это будет сумма арифметической прогрессии.
Не соглашусь. Арифмитическая прогрессия возможна, если есть умножение, тут его нет.
При каждом сложении ошибка не более 1 двоичного значащего разряда от текущей суммы.
Вообще да, по мере сложения она будет расти, так как сумма растет. Но расти будет ошибка текущей операции по отношению к предыдущим. Те ошибки, которые уже в сумме, не растут. Поэтому, оценка один двоичный разряд мантиссы результатирующей суммы, умноженный на число слагаемых - это оценка с большим запасом. Как если бы все ошибки были, как последнее сложение. А они были такие же или меньше.
Если не согласны - приводите аргументы, обсудим, может и я где-то ошибаюсь.
Арифмитическая прогрессия возможна, если есть умножение, тут его нет.
Вы перепутали геометрическую прогрессию с арифметической. В арифметической умножение не нужно.
В остальном вы правы. Действительно, можно оценить максимальную общую ошибку по последнему знаку результирующей суммы * число сложений.
Только в первом вашем комменте не было про результирующую сумму, поэтому я подумал, что вы предлагали брать ошибку от обычного слагаемого, а не от суммы и умножать на 1000. Наверное, я вас неправильно понял и вы подразумевали именно результирующую сумму.
Точно! Перепутал)
Тогда вопросов нет. Ошибка, действительно, возрастает с ростом суммы и похожа на сумму членов арифметической прогрессии.
Да, я предлагал взять младший бит результата и умножить его на количество слагаемых, что бы грубо получить предел ошибки. Но это с запасом. Наверное, если подумать, его можно уменьшить. Ошибки в статье были заведомо больше этой оценки и поэтому я полез проверять)
Интересно было бы сравнить со стеккингом или беггингом
Идея интересная, но как-будто уже известные вещи решают каждую из описанных проблем эффективнее:
Distributed Data Parallel, Fully Shared Data Parallel или DeepSpeed для распределенного обучения
Адаптеры вроде P-tuning, LoRA и еще 1000000 способов для дообучения без риска потерять исходную модель
Мешать новую выборку для дообучения с выборкой из иходного датасета или настраивать Loss-функцию так, чтобы выход дообученной модели не сильно расходился с претрейном для стабильного дообучения с минимальным забыванием
Идея с тем, чтобы усреднять веса модели и как-то еще их объединять интересная, но как будто для того, чтобы пришлось применять этот метод, а не один из вышеписанных должно сойтись слишком много звезд на небе или мне кажется?
Не проще/эффективнее в том случае смотреть как комбинировать и эффективнее учить адаптеры?
Чтобы выбрать правильный подход, нужно знать их все. В этом сложность.
В моём случае настолько огромный датасет, что дообучающая выборка на много порядков больше обучающей. Поэтому я выбрал подход описанный в статье. Он дал и параллелизм и контролируемое забывание, а не катастрофическое.
Тем не менее, возможно, мой редкий опыт кому-то пригодится, поэтому он выражен в форме статьи.
Слияние словарей в PyTorch: зачем нужно и подводные камни