Эксперимент.

[thesz]

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

(проверяю идеи)


import Data.Bits

import Data.List (splitAt, genericLength, foldr1)

import Data.Word

crc32 :: Word32 -> Word32
crc32 = head . drop 32 . iterate step . xor 0x01020304
where
step x
| odd x = shifted `xor` 0xedb88320
| otherwise = shifted
where
shifted = shiftR x 1

crcs :: [Word32]
crcs = tail $ iterate crc32 1122334455

floats :: [Double]
floats = map ((\x -> x - 1) . (*2)) $ map (/0x1000000) $ map (fromIntegral . flip shiftR 8) crcs

slicedFloats :: Int -> [[Double]]
slicedFloats n = map fst $ tail $ iterate (splitAt n . snd) (undefined, floats)

norm vs = map (m*) vs
where
m = (1/) $ sqrt $ sum $ zipWith (*) vs vs

cosAttained n m = fst (cosineGroundTruth combinedByCosine, cosineGroundTruth combinedByCosineSign)
where
(start : minPos : directions') = slicedFloats n
directions = map norm $ take m directions'
groundTruth = norm $ zipWith (-) minPos start
cosineGroundTruth vs = sum $ zipWith (*) groundTruth vs
cosinesDirections = zip (map cosineGroundTruth directions) directions
combinedByCosine = norm $ foldr1 (zipWith (+)) $ map (\(c,d) -> map (*c) d) cosinesDirections
combinedByCosineSign = norm $ foldr1 (zipWith (+)) $ map (\(c,d) -> map (*signum c) d) cosinesDirections

Предел получается в районе обратного корня из 2. Это разумно ожидать. До косинуса, равного половине, мы добираемся за выборку, равную трети от размерности вектора. Четверть - где-то в районе 7%, пятая часть - 4,7%. Снижая скорость приближения, мы можем уменьшить количество вычислений.

Теперь меня интересует, где будет находиться минимум операций с плавающей точкой для разного разбиения некоторой матрицы коэффициентов.

Мне не нравится градиентный спуск, как его применяют сейчас. Он был придуман, в его современной форме, из-за ограниченности ресурсов (особенно learning rate) и уже довольно давно. У него есть проблемы со значениями и он плохо применим в новых системах (то самое обучение подкреплением). Поэтому я и пытаюсь получить что-то другое. Две вещи, которые мне очень не нравятся, это скорость обучения (learning rate) и обратное распространение ошибок (backpropagation). Обе они подозрительны мне из-за связанной с ними магии - для скорости обучения придумывают вычурные "расписания" (learning rate cosine schedule, например), обратное распространение ошибок требует хитрых приведений (batch normalization, ADAM и тп), чтобы оно обучало более-менее быстро на современных данных.