Типа результаты умножений несколько раз используются

Ок, смотрю вот эту статью: https://arxiv.org/abs/1509.09308

Ну ты прав, в статье именно о повторном использовании, алгоритмы это дополнительная плюшка

там четко написано что конволюция F(MxM, RxR), где МхМ это размеры картинки на выходе, RxR размеры фильтра, требует (M+R-1)(M+R-1) умножений. В нашем случае, для первого уровня: М = 3, R = 3. Значит должно быть минимум (3+3-1)(3+3-1) = 25 умножений. Плюс 9 умножений на втором уровне. Итого 25+9 = 34 умножений. Как они получили 18?

На выходе 1х1

это выход второго слоя, на первом выход 3х3

А ты это имеешь ввиду

либо они как то совмещают два уровня, но не пойму как

Допустим у нас на входе один канал, размер выходного изображения 3х3 (т.е. 9 пикселей, а к входному добавляются соответствующие размеру фильтра нулевые паддинги по краям), и свёртка происходит (а) одним слоем с одним фильтром 5х5, (б) двумя последовательными слоями, в каждом по одному фильтру 3х3

тогда в случае (а) получается:
(5*5) * (9) = (25) * (9) операций
в случае (б) получается:
(3*3) * (9) + (3*3) * (9) = (9+9) * (9) = (18) * (9) операций

нет, выходное изображение у нас 1х1

тогда получается (а)
(5*5) * (1) = (25) * (1) операций
(б)
(3*3)*(1) + (3*3)*(1) = (18) * (1) операций

как ты получил (б)?

на первом уровне 5х5 картинка, и по ней ездит 3х3 фильтр

да, 9 наложений фильтра на 3х3 окно, то есть 3х3х3 умножений, разве нет?

то есть 3х3х9

используя метод Винограда, мы уменьшаем это число до 25

(причем добавляется куча сложений)

там же написано что минимальное число умножений это количество входов, то есть 5х5=25

Давай я попробую объяснить без привязки к статье и формулам минимального числа умножений и прочего

Вот у нас есть, например, входной feature map размером NxN (количество каналов для простоты будем брать = 1), и мы хотим получить двумя способами (свёрткой 5х5 или двумя свёртками 3х3) выходной feature map также размером NxN

<Лирическое отступление>
для того, чтобы сохранился размер feature map после свёрточного слоя с ядром KxK , K>1 добавляют нулевой паддинг, т.е. увеличивают входное изображение, добавляя границы по бокам
для свёртки 5x5 это будет по два пикселя с каждой стороны, для свёртки 3х3 - один пиксель с каждой стороны. Допустим мы их добавляем, т.к. мы хотим одинаковые размеры NxN на выходе.
</Лирическое отступление>

Получается:
А) Чтобы получить выходной feature map размером NxN одной свёрткой 5х5 мы должны пройти центром этой свёртки по NxN точкам исходного feature map и каждый раз провести 5х5 умножений, получится (25) * (N*N) операций
Б) Чтобы получить выходной feature map размером NxN двумя последовательными свёртками 3х3 мы должны:
1) Пройти центром первой свёртки 3х3 по NxN точкам исходного feature map, каждый раз провести 3х3 умножений, получится (9) * (N*N) операций и на выходе - промежуточный feature map размером NxN
2) Пройти центром второй свёртки 3х3 по NxN точкам промежуточного feature map-а, каждый раз производя 3х3 умножений, получится ещё (9) * (N*N) операций - и на выходе - итоговый feature map размером NxN
В итоге получается (9)*(N*N) + (9)*(N*N) = 18 * (N*N) операций, что в 25/18 раз меньше