Отсчётный скетч

Отсчётный скетч (англ. Count sketch) — метод уменьшения размерности, используемый в статистике, машинном обучении и алгоритмах обработки больших данных^[1]^[2]. Может быть использован для ускорения ядерного метода и билинейного пулинга в нейронных сетях, а также в численных алгоритмах линейной алгебры^[3].

Особенности[править]

В отличие от тензорного скетча отсчётный скетч оперирует так называемым внешним произведением векторов:

𝐚 \otimes 𝐛^{𝐓} \to [\begin{matrix} a_{1} \\ a_{2} \\ a_{3} \\ a_{4} \end{matrix}] [\begin{matrix} b_{1} & b_{2} & b_{3} \end{matrix}] = [\begin{matrix} a_{1} b_{1} & a_{1} b_{2} & a_{1} b_{3} \\ a_{2} b_{1} & a_{2} b_{2} & a_{2} b_{3} \\ a_{3} b_{1} & a_{3} b_{2} & a_{3} b_{3} \\ a_{4} b_{1} & a_{4} b_{2} & a_{4} b_{3} \end{matrix}]

где $\otimes$ означает произведение Кронекера.

Существенно, что отсчётный скетч от такого произведения двух векторов

C (x \otimes x^{T})

^[4]

эквивалентен векторной свёртке

C^{(1)} x * C^{(2)} x^{T}

гдe $C^{(1)}$ и $C^{(2)}$ являются независимыми матрицами.

Для сокращения вычислительных затрат на реализацию свёртки нескольких отсчётных скетчей может быть использовано быстрое преобразование Фурье.

Примечания[править]

↑ Faisal M. Algashaam; Kien Nguyen; Mohamed Alkanhal; Vinod Chandran; Wageeh Boles.Multispectral Periocular Classification WithMultimodal Compact Multi-Linear Pooling [1]. - IEEE Access, Vol. 5. 2017.
↑ Ahle, Thomas; Knudsen, Jakob. Almost Optimal Tensor Sketch (неопр.). Researchgate (3 сентября 2019). Дата обращения: 11 июля 2020. Архивировано 14 июля 2020 года.
↑ Woodruff, David P. "Sketching as a Tool for Numerical Linear Algebra." Theoretical Computer Science 10.1-2 (2014): 1–157.
↑ Fast and scalable polynomial kernels via explicit feature maps // (SIGKDD international conference on Knowledge discovery and data mining). — Association for Computing Machinery. — doi:10.1145/2487575.2487591.

Искусственный интеллект
История	История искусственного интеллекта Зима искусственного интеллекта Дартмутский семинар
Философия	Тест Тьюринга Китайская комната Сильный и слабый искусственные интеллекты Дружественный искусственный интеллект Этика искусственного интеллекта Проблема контроля
Направления	Агентный подход Адаптивное управление Инженерия знаний Модель жизнеспособной системы Машинное обучение Нейронная сеть Нечёткая логика Обработка естественного языка Распознавание образов Роевой интеллект Символический ИИ Эволюционные алгоритмы Экспертная система
Применение	Голосовое управление Задача классификации Классификация документов Кластеризация документов Кластерный анализ Локальный поиск Машинный перевод Оптическое распознавание символов Распознавание речи Распознавание рукописного ввода Игровой ИИ Промпт
Исследователи	Чарлз Бэббидж Владимир Вапник Джозеф Вейценбаум Норберт Винер Виктор Глушков Владимир Городецкий Ян ЛеКун Алексей Ляпунов Джон Маккарти Марвин Мински Аллен Ньюэлл Сеймур Пейперт Джуда Перл Гермоген Поспелов Дмитрий Поспелов Фрэнк Розенблатт Герберт Александер Саймон Алан Тьюринг Патрик Уинстон Виктор Финн Сергей Фомин Демис Хассабис Джеффри Хинтон Ноам Хомский Клод Шеннон Эндрю Ын Элиезер Юдковский

Машинное обучение и data mining
Задачи	Задача классификации Обучение без учителя Обучение с частичным привлечением учителя Регрессионный анализ AutoML Ассоциативные правила Выделение признаков Обучение признакам Обучение ранжированию Грамматический вывод Онлайновое обучение
Обучение с учителем	Метод k-ближайших соседей Наивный байесовский классификатор Дерево решений Метод опорных векторов Линейная регрессия Логистическая регрессия Перцептрон Ансамбли моделей Бэггинг Бустинг Random forest Метод релевантных векторов
Кластерный анализ	Метод k-средних Метод нечёткой кластеризации Иерархическая кластеризация EM-алгоритм BIRCH CURE DBSCAN OPTICS Mean-shift
Снижение размерности	Факторный анализ Метод главных компонент CCA ICA LDA Неотрицательное матричное разложение t-SNE
Структурное прогнозирование	Графовая вероятностная модель Байесовская сеть Скрытая марковская модель CRF
Выявление аномалий	Метод k-ближайших соседей Локальный уровень выброса
Графовые вероятностные модели	Байесовская сеть Марковская сеть Скрытая марковская модель
Нейронные сети	Ограниченная машина Больцмана Самоорганизующаяся карта Функция активации Сигмоида Softmax Радиально-базисная функция Метод обратного распространения ошибки Глубокое обучение Многослойный перцептрон Рекуррентная нейронная сеть Долгая краткосрочная память Управляемый рекуррентный блок Свёрточная нейронная сеть U-Net Автокодировщик
Обучение с подкреплением	Марковский процесс Уравнение Беллмана Жадный алгоритм Q-обучение SARSA Temporal difference (TD)
Теория	Теория Вапника — Червоненкиса Дилемма смещения–дисперсии Теория вычислительного обучения Минимизация эмпирического риска Оккамово обучение PAC learning Статистическая теория обучения
Журналы и конференции	NeurIPS ICML ML JMLR ArXiv:cs.LG