Не перестаю восхищаться JL леммой - случайная проекция из многомерного пространства в меньшее число измерений примерно сохраняет попарные расстояния между точками, это значит, ты можешь сжать данные, ускорить k-nn или получить примерный собственный спектр, если применить случайную проекцию сразу к колонкам и строчкам симметричной матрицы, что я и сделал.
В качестве примера взял 1.3 млн точек из множества Жюлиа (-0.123+0.745*j), каждую точку соединил с ближайшими 8 соседями - получился граф с симметричной матрицей смежности X, которую слева и справа умножил на случайную ортонормированную матрицу R размером 1.3M на 130 (R сначала заполняется гауссовским шумом, а затем пропускается через быструю QR декомпозицию для ортонормировки):
Y = (R^T)*X*R,
Так перешел от матрицы 1.3M х 1.3M к матрице 130 х 130. По теореме Пуанкаре собственные значения маленькой матрицы Y зажаты между собственными значениями большой X, примерно сохраняя их распределение. Значит можно взять несколько λ от Y (я взял первые 13 собственных значений) прогнать их итерациями через X и получить соответствующие им собственные вектора матрицы X, а дальше отправить в k-means или гауссовские смеси (выбрал этот вариант, потому-то k-means оказался более шумный). Получается такая кластеризация графа на случайных проекциях.
Y = (R^T)*X*R,
Так перешел от матрицы 1.3M х 1.3M к матрице 130 х 130. По теореме Пуанкаре собственные значения маленькой матрицы Y зажаты между собственными значениями большой X, примерно сохраняя их распределение. Значит можно взять несколько λ от Y (я взял первые 13 собственных значений) прогнать их итерациями через X и получить соответствующие им собственные вектора матрицы X, а дальше отправить в k-means или гауссовские смеси (выбрал этот вариант, потому-то k-means оказался более шумный). Получается такая кластеризация графа на случайных проекциях.
🔥2
Традиционно эмбеддинги получаем нейросетями. Если хотите "экологически чистые" эмбединги🌳, то ребята из Королёвского колледжа Лондона сделали "деревянный" автоэнкодер. В отличие от классического варианта, тут кодер и декодер учатся независимо.
Кодер работает как GAN: лес учится отличать реальные данные от синтетических, а из его листьев-ошибок семплируются всё более правдоподобные точки. После нескольких итераций лес перестает их различать. Так модель учит внутреннюю структуру данных. Затем для n точек строится матрица близости K (насколько часто пары точек попадают в один лист). В простом варианте первые d собственных векторов (V) и значений (Λ) этой матрицы формируют d-мерные эмбеддинги: Z = √n*V*Λ.
Декодер это просто k-nn в пространстве эмбеддингов: чтобы восстановить объект по эмбеддингу, берём k ближайших точек из обучающей выборки и усредняем их фичи (берём моду для категорий).
Что бы получить эмбеддинг новый точки из test набора ищем ее близость к тем же n точкам - K' и умножаем на собственные вектора: Z' = √n*K'*V.
Всё без градиентов, только 🌲🌳🪵!
Кодер работает как GAN: лес учится отличать реальные данные от синтетических, а из его листьев-ошибок семплируются всё более правдоподобные точки. После нескольких итераций лес перестает их различать. Так модель учит внутреннюю структуру данных. Затем для n точек строится матрица близости K (насколько часто пары точек попадают в один лист). В простом варианте первые d собственных векторов (V) и значений (Λ) этой матрицы формируют d-мерные эмбеддинги: Z = √n*V*Λ.
Декодер это просто k-nn в пространстве эмбеддингов: чтобы восстановить объект по эмбеддингу, берём k ближайших точек из обучающей выборки и усредняем их фичи (берём моду для категорий).
Что бы получить эмбеддинг новый точки из test набора ищем ее близость к тем же n точкам - K' и умножаем на собственные вектора: Z' = √n*K'*V.
Всё без градиентов, только 🌲🌳🪵!
🤯4🔥3