ES
это без виноградов и прочего
Size: a a a
2017 April 14
ES
если мы не делаем паддинги для сохранения размера feature map - то тут другие подсчёты будут, но суть примерно та же вроде
NK
Evgeny, спасибо, я вроде понял! То есть здесь вся суть в том что мы сохраняем размеры feature map (причем не только на выходе, но и между двумя уровнями 3х3 сверток). Тогда да, глобально получается уменьшение умножений. Но если бы на выходе 5х5 feature map сжималась в один пиксель, то мы бы увеличивали число умножений от 25 до 90. Правильно?
ES
Если входное изображение 5х5, и мы не делаем паддинг, а делаем (а) свёртку 5х5 -> получая выход 1х1, (б) свёртку 3х3 -> получая выход 3х3 + ещё одну свёртку 3x3 - > получая выход 1х1, то да, тут получается операций 25 vs (3*3)*(3*3) + (3*3) = 25 vs 90, но это corner case
ES
потому что в реальности размеры изображений обычно больше, чем 5х5, а не на границах там получается всё по-другому
NK
Все понятно, большое спасибо! Хотя меня немного смущает table 3 in "Rethinking the Inception..." paper: там factorizing 7x7 convolution into 3 levels of 3x3 convolutions leads to increase from 3.8B ops to 4.8B ops.
A
Если входное изображение 5х5, и мы не делаем паддинг, а делаем (а) свёртку 5х5 -> получая выход 1х1, (б) свёртку 3х3 -> получая выход 3х3 + ещё одну свёртку 3x3 - > получая выход 1х1, то да, тут получается операций 25 vs (3*3)*(3*3) + (3*3) = 25 vs 90, но это corner case
Пересчитал для 8х8 (http://img.it610.com/image/info5/ad0f5af4e9434226a93546f8656c6a28.jpg) - действительно, получается экономия
NK
Пересчитал для 8х8 (http://img.it610.com/image/info5/ad0f5af4e9434226a93546f8656c6a28.jpg) - действительно, получается экономия
Andrey, размер входной картинки не важен, важно, что мы сохраняем этот размер на выходе. Например, Евгений показал выше что если входной размер 5х5, и мы хотим сохранить его на выходе, то получается: a) 5x5 умножений х(5х5) активаций на выходе, т.е 25х25 умножений. б) заменяем на два уровня 3х3 сверток: первый уровень: 3x3x5x5, затем второй уровень: 3x3x5x5, итого: 5x5x(3x3+3x3) = 18x25.
A
Это все понятно. Лично я завис на фразе о том, что "если тупо двигать такую сетку (две свертки 3х3), то мы увеличим объем вычислений". А мы тут именно что тупо подвигали сетку и поняли, что объем вычислений таки уменьшается.
YB
Давай я попробую объяснить без привязки к статье и формулам минимального числа умножений и прочего
Вот у нас есть, например, входной 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 раз меньше
Вот у нас есть, например, входной 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 раз меньше
Ага. Теперь ещё нужно для винограда посчитать.
Для 3х3 утверждают, что можно делать 16 операций вместо 36 для шага между точками выхода 2х2.
Для 5х5 и 7х7 тоже вроде фильтры сделали оптимизированные, но на год или полтора позже.
Для 3х3 утверждают, что можно делать 16 операций вместо 36 для шага между точками выхода 2х2.
Для 5х5 и 7х7 тоже вроде фильтры сделали оптимизированные, но на год или полтора позже.
NK
Это все понятно. Лично я завис на фразе о том, что "если тупо двигать такую сетку (две свертки 3х3), то мы увеличим объем вычислений". А мы тут именно что тупо подвигали сетку и поняли, что объем вычислений таки уменьшается.
честно говоря, статья очень коряво написана
YB
Это все понятно. Лично я завис на фразе о том, что "если тупо двигать такую сетку (две свертки 3х3), то мы увеличим объем вычислений". А мы тут именно что тупо подвигали сетку и поняли, что объем вычислений таки уменьшается.
Видимо, имеется в виду "Если тупо двигать сетку вместо того, чтобы переиспользовать результаты прошлых участков"
EZ
Видимо, имеется в виду "Если тупо двигать сетку вместо того, чтобы переиспользовать результаты прошлых участков"
А как мы их переиспользуем?
A
так нету же "повторного использования вычислений". Просто при движении окна 3х3 нахлест меньше выходит, чем в случае 5х5. Но умножать заново приходится (если не брать в расчет те самые матричные оптимизации)
A
веса одни и те же во всех операциях умножения, но на что множить - матрицы 5х5 или 3х3 - всегда разные. Та часть, которая одинаковая за счет того, что stride = 1, множится на другие веса - не те, что до смещения
YB
Да, верно, веса разные, тут я не прав, фильтры винограда работают за счёт другого принципа.
YB
там так же как с фурье -- мы сначала считаем что-то типа полусуммы и полуразности, а потом их складываем и вычитаем. это не переиспользование просто результатов в одной точке для другой.
YB
Для stride=2 и кернела 3х3 как раз подходит этот алгоритм:
Algorithms for F (m × m, r × r) can be used to compute convnet layers with r × r kernels. Each image channel is divided into tiles of size (m+r−1)×(m+r−1), with r− 1 elements of overlap between neighboring tiles
получается, для F(3x3, 2x2) , m=3, r=2, оверлап 1 и тайлы размера 4х4 , идут с шагом 3 .
Algorithms for F (m × m, r × r) can be used to compute convnet layers with r × r kernels. Each image channel is divided into tiles of size (m+r−1)×(m+r−1), with r− 1 elements of overlap between neighboring tiles
получается, для F(3x3, 2x2) , m=3, r=2, оверлап 1 и тайлы размера 4х4 , идут с шагом 3 .
YB
NK
Для stride=2 и кернела 3х3 как раз подходит этот алгоритм:
Algorithms for F (m × m, r × r) can be used to compute convnet layers with r × r kernels. Each image channel is divided into tiles of size (m+r−1)×(m+r−1), with r− 1 elements of overlap between neighboring tiles
получается, для F(3x3, 2x2) , m=3, r=2, оверлап 1 и тайлы размера 4х4 , идут с шагом 3 .
Algorithms for F (m × m, r × r) can be used to compute convnet layers with r × r kernels. Each image channel is divided into tiles of size (m+r−1)×(m+r−1), with r− 1 elements of overlap between neighboring tiles
получается, для F(3x3, 2x2) , m=3, r=2, оверлап 1 и тайлы размера 4х4 , идут с шагом 3 .
оверлап = stride = 1