- Субквадратичные алгоритмы для матриц ядра с помощью оценки плотности ядра (arXiv)
Автор: Айнеш Бакши, Петр Индик, Пранит Качам, Сандип Силвал, Самсон Чжоу.
Аннотация: Матрицы ядра, а также представляемые ими взвешенные графы являются повсеместными объектами в машинном обучении, статистике и других смежных областях. Основным недостатком использования методов ядра (обучения и вывода с использованием матриц ядра) является эффективность — при наличии n входных точек большинству алгоритмов на основе ядра необходимо материализовать полную матрицу ядра n × n перед выполнением любых последующих вычислений, что приводит к Ω(n2) время выполнения. Таким образом, преодоление этого квадратичного барьера для различных задач стало предметом обширных исследований. Мы преодолеваем квадратичный барьер и получаем алгоритмы субквадратичного времени для нескольких фундаментальных примитивов линейной алгебры и обработки графов, включая аппроксимацию верхнего собственного значения и собственного вектора, спектральную разреженность, решение линейных систем, локальную кластеризацию, низкоранговую аппроксимацию, оценку древовидности и подсчет взвешенных треугольников. . Мы основываемся на недавнем фреймворке Kernel Density Estimation, который (после предварительной обработки во времени, субквадратичном по n) может возвращать оценки сумм строк и столбцов матрицы ядра. В частности, мы разрабатываем эффективные сокращения от взвешенной выборки вершин и взвешенных ребер на графах ядра, моделирования случайных блужданий на графах ядра и выборки важности на матрицах к оценке плотности ядра и показываем, что мы можем генерировать выборки из этих распределений в сублинейном (в поддержке раздачи) время. Наши сокращения являются центральным элементом каждого из наших приложений, и мы считаем, что они могут представлять самостоятельный интерес. Мы эмпирически демонстрируем эффективность наших алгоритмов в низкоранговой аппроксимации (LRA) и спектральном разрежении, где мы наблюдаем 9-кратное уменьшение количества вычислений ядра по сравнению с базовыми показателями для LRA и 41-кратное уменьшение размера графика для спектрального разрежения.
2. Проектирование надежных трансформаторов с использованием оценки плотности надежного ядра (arXiv)
Автор: Син Хань, Тунчжэн Рен, Тан Минь Нгуен, Кхай Нгуен, Джойдип Гош, Нхат Хо.
Абстрактный :
