Алгоритм случайной проекции псевдокод

Question

Я пытаюсь применить метод случайных проекций к очень редкому набору данных.Я нашел статьи и учебные пособия по методу Джонсона Линденштраусса, но каждый из них полон уравнений, которые не дают мне значимого объяснения.Например, этот документ по Johnson-Lindenstrauss

К сожалению, из этого документа я не могу получить представление о шагах реализации алгоритма.Это длинный путь, но есть ли кто-нибудь, кто может сказать мне простую английскую версию или очень простой псевдокод алгоритма?Или где можно начать копать это уравнение?Какие-либо предложения?

Например, что я понял из алгоритма, прочитав этот документ, касающийся Джонсона-Линденштраусса , таков:

1. Предположим, у нас есть матрица AxB, гдеA - количество образцов, а B - количество измерений, например, 100x5000.И я хочу уменьшить его размер до 500, что даст матрицу 100x500.

Насколько я понимаю: сначала мне нужно построить матрицу 100x500 изаполнить записи случайным образом +1 и -1 (с вероятностью 50%).

Редактировать:
Ладно, думаю, я начал получать его.Таким образом, у нас есть матрица A, которая равна mxn.Мы хотим уменьшить его до E, что составляет mxk.

Нам нужно создать матрицу R, которая имеет размерность nxk, и заполнить ее 0, -1 или +1 относительно 2/3,1/6 и 1/6 вероятность.

После построения этого R мы просто сделаем умножение матрицы AxR, чтобы найти нашу уменьшенную матрицу E.Но нам не нужно делать полное матричное умножение, потому что, если элемент Ri равен 0, нам не нужно выполнять вычисления.Просто пропустите это.Но если мы столкнемся с 1, мы просто добавим столбец, или, если это -1, просто вычтем его из расчета.Поэтому мы просто будем использовать суммирование, а не умножение, чтобы найти E.И это то, что делает этот метод очень быстрым.

Он оказался очень аккуратным алгоритмом, хотя я чувствую себя слишком глупо, чтобы понять это.

Answer 1

Вы правильно поняли.Однако, как я понимаю случайный проект, строки вашей матрицы R должны иметь единичную длину.Я полагаю, что это примерно то, для чего предназначена нормализация на 1 / sqrt (k), чтобы нормализовать тот факт, что они не являются единичными векторами.

Это не проекция, а почти проекция;Строки R не являются ортонормированными, но в гораздо более многомерном пространстве они почти такие же.На самом деле скалярное произведение любых двух векторов, которые вы выберете, будет очень близко к 0. Вот почему это обычно хорошее приближение к нахождению правильной основы для проекции.

Answer 2

Если ваш набор данных разрежен, то разреженные случайные проекции не будут работать хорошо.У вас есть несколько вариантов:

Вариант A:

Шаг 1. Примените структурированную плотную случайную проекцию (обычно используется так называемое быстрое преобразование Адамара).Это специальная проекция, которую очень быстро вычислить, но в остальном она обладает свойствами обычной плотной случайной проекции

Шаг 2. Примените разреженную проекцию к «уплотненным данным» (разреженные случайные проекции полезны только для плотных данных)

Вариант B: применить SVD к разреженным данным.Если данные редки, но имеют некоторую структуру, лучше использовать SVD.Случайная проекция сохраняет расстояния между всеми точками.SVD лучше сохраняет расстояния между плотными областями - на практике это более значимо.Также люди используют случайные проекции для вычисления SVD на огромных наборах данных.Случайная проекция дает вам эффективность, но не обязательно наилучшее качество встраивания в низкое измерение.Если ваши данные не имеют структуры, используйте случайные проекции.

Опция C:

Для точек данных, для которых SVD имеет небольшую ошибку, используйте SVD;для остальных точек используйте случайную проекцию

Вариант D: используйте случайную проекцию, основанную на самих точках данных.Это очень легко понять, что происходит.Это выглядит примерно так:

create a n by k matrix (n number of data point, k new dimension)
for i from 0 to k do #generate k random projection vectors  
   randomized_combination = feature vector of zeros (number of zeros = number of features) 
   sample_point_ids = select a sample of point ids
   for each point_id in sample_point_ids do:
       random_sign = +1/-1 with prob. 1/2
       randomized_combination += random_sign*feature_vector[point_id] #this is a vector operation
    normalize the randomized combination
    #note that the normal random projection is:
    # randomized_combination = [+/-1, +/-1, ...] (k +/-1; if you want sparse randomly set a fraction to 0; also good to normalize by length]
    to project the data points on this random feature just do
    for each data point_id in dataset:
        scores[point_id, j] = dot_product(feature_vector[point_id], randomized_feature)

Если вы все еще хотите решить эту проблему, напишите здесь сообщение, я могу дать вам больше псевдокода.

Способ думать об этомчто случайная проекция - это просто случайный шаблон, а точечный продукт (т.е. проекция точки данных) между точкой данных и шаблоном дает вам перекрытие между ними.Таким образом, если две точки данных перекрываются со многими случайными образцами, эти точки будут похожими.Поэтому случайные проекции сохраняют сходство, используя меньше места, но они также добавляют случайные флуктуации в попарных сходствах.JLT говорит вам, что для флуктуации 0.1 (eps) вам нужно около 100 * log (n) измерений.

Удачи!

Answer 3

Отображение из многомерных данных A в низкоразмерные данные E приведено в формулировке теоремы 1.1 в последней статье - это просто скалярное умножение, за которым следует умножение матриц.Векторы данных - это строки матриц A и E. Как указывает автор в разделе 7.1, вам не нужно использовать алгоритм умножения полной матрицы.

Answer 4

Пакет R для выполнения случайной проекции с использованием леммы Джонсона-Линденштраусса RandPro