Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 18
Это для сжатия штоли используется?
можно и для сжатия, я использую это как препроцессинг перед подготовкой данных для обучения нейросетки
Это много для чего используется. PCA/SVD в машинном обучении (и всех прилегающих областях) — это почти как алгоритмы сортировки в обычных инженерных задачах. При решении какой-то не совсем тривиальной задачи (скажем, поиска дупликатов в массиве) в первую очередь нужно подумать, а нельзя ли применить сортировку и затем решить задачу для отсортированного массива, а потом уже искать способы оптимизировать алгоритм, сделав сложность меньше чем O(n*log n). Так и с SVD — во многих случаях выделение собственных векторов является первым шагом для решения задачи; затем это решение может быть соптимизировано и записано без использования SVD, но во многих случаях алгоритмы так и используют SVD.
SVD используется для уменьшения пространства признаков (грубо говоря, позволяет ворочать в памяти матрицы не 1e10 x 1e10, а, скажем, 1e3 x 1e3, при этом не сильно теряя точность), избавляться от шума (отбрасываются малозначительные вектора, не показывающие общего тренда), оптимизации (см. total least squares) и помогает в целой куче других математических техник. SVD/PCA является стандартной техникой, используемой чуть ли не во всех методах распознавания визуальных объектов, в некоторых методах рекоммендательных движков, классификации и кластеризации текста и т.д. и т.п. Вероятнее всего, ежедневно пользуясь стандартными сервисами типа Gmail или Amazon вы по несколько раз опосредованно используете SVD или алгоритмы, выведенные из него.
SVD используется для уменьшения пространства признаков (грубо говоря, позволяет ворочать в памяти матрицы не 1e10 x 1e10, а, скажем, 1e3 x 1e3, при этом не сильно теряя точность), избавляться от шума (отбрасываются малозначительные вектора, не показывающие общего тренда), оптимизации (см. total least squares) и помогает в целой куче других математических техник. SVD/PCA является стандартной техникой, используемой чуть ли не во всех методах распознавания визуальных объектов, в некоторых методах рекоммендательных движков, классификации и кластеризации текста и т.д. и т.п. Вероятнее всего, ежедневно пользуясь стандартными сервисами типа Gmail или Amazon вы по несколько раз опосредованно используете SVD или алгоритмы, выведенные из него.
Это для тонкого троллинга используется:)
Дайте пожалуйста точную формулировку этой замечательной теоремы (+источник) из которой: Другими словами, при стремлении количества итераций к бесконечности, произведение будет стремиться к точным значениям собственных векторов. В то же время последняя будет на главной диагонали содержать собственные числа матрицы, приближенные конечно. Напоминаю что этот алгоритм более менее точно работает только для симметричных матриц.
Более менее точно работает — страшнее фразы я не встречал.
Я смотрю Дж. Голуба «Матрицы и вычисления» в ее английском варианте (в русском переводе много ошибок), этот алгоритм рассматривается в контексте решения несимметричной проблемы собственных значений. Очень заинтересовало это ограничение на симметричность и упоминание про точность.
Упоминая симметричность матрицы — возможно, вы имеете ввиду что все собственные значения гарантированно вещественные? Но ведь в нессиметричном случае они могут быть и комплексными — в этом проблема?
Более менее точно работает — страшнее фразы я не встречал.
Я смотрю Дж. Голуба «Матрицы и вычисления» в ее английском варианте (в русском переводе много ошибок), этот алгоритм рассматривается в контексте решения несимметричной проблемы собственных значений. Очень заинтересовало это ограничение на симметричность и упоминание про точность.
Упоминая симметричность матрицы — возможно, вы имеете ввиду что все собственные значения гарантированно вещественные? Но ведь в нессиметричном случае они могут быть и комплексными — в этом проблема?
Упоминая симметричность матрицы — возможно, вы имеете ввиду что все собственные значения гарантированно вещественные?
Вообще да, могут быть и комплексные, ну это вы и так знаете. В статье по ссылке несколько раз делается упор на то что матрица должна быть с определенными свойствами: «allows the computation of all eigenvalues and eigenvectors of a real, symmetric, full rank matrix». Но т.к. имплементаци оперирует только реальными числами, то я не упоминал ничего про это требование к матрице.
После имплементации алгоритма я первым делом проверил его на реальных данных, параллельно прогоняя все те же данные на матлабе для сверки. Для симметричной матрицы данные совпадали в большинстве случаев вплоть до 10^(-9), далее не проверял. Но были случаи когда видно что значения где то рядом, но не те. Я пытался найти баг в коде, но безуспешно. Так что я отметил для себя, что этот алгоритм более-менее точный, но возможны редкие исключения, или пока не найденный баг.
Данные для тестов ассимитричной матрицы я уже генерил рандомно, комплексные числа не получились ни разу, и результат был прямо скажем не очень точный, но все же иногда ответ был где то рядом, особенно если симметрия нарушалась не значительно.
На счет необходимости точной формулировки, я с вами не соглашусь, т.к. я хотел передать суть процесса, а не доказывать его точность. Но думаю ее точную формулировку легко найти в книге Дж. Голуба «Матрицы и вычисления» =)
Спасибо. Нет там такой теоремы, не нашел я. Теорема мне нужна для того чтобы однозначно определить область применимости алгоритма для матриц определенного типа — там это точно есть. «комплексные числа не получились ни разу» дело в том, что из приведенного алгоритма, насколько я понимаю вы их и не могли получить — только с использованием eig функции смотреть получается.
Когда делали QR разложение — какой алгоритм поиска разложения использовался? Использовался выбор ведущего столбца? Если не использовался (что скорее всего) — то в этом проблема.
Смущает меня просто тема с симметричными матрицами — нужно разобраться основательно.
Когда делали QR разложение — какой алгоритм поиска разложения использовался? Использовался выбор ведущего столбца? Если не использовался (что скорее всего) — то в этом проблема.
Смущает меня просто тема с симметричными матрицами — нужно разобраться основательно.
для qr разложения я использовал процесс Грэма-Шмидта, но т.к. я не специалист в линейной алгебре, так что мне трудно сказать является ли этот метод, методом ведущего столбца -) я когда делал инверсию матрицы методом Гаусса-Жордана, то там вроде встречал упоминание про ведущий столбец, ну т.е. там цикл по столбцам и сначала матрица приводится в верхнюю треугольную, а затем в обратном порядке приводятся к нулю верхние элементы от главной диагонали
про требование к симметричности пишут в статье (там вверху ссылка и тут продублирую) из которой я взял итеративный метод поиска собственных векторов. там не объясняется почему такое требование (ну или я просто не понял), но пишут, что не гарантируется сходимость процесса к собственным векторам
про требование к симметричности пишут в статье (там вверху ссылка и тут продублирую) из которой я взял итеративный метод поиска собственных векторов. там не объясняется почему такое требование (ну или я просто не понял), но пишут, что не гарантируется сходимость процесса к собственным векторам
«более или менее точно», увы. Реальные матрицы могут иметь собственные значения, различающиеася на сотни порядков («плохо определенные матрицы»). И когда на диагонали начнут получаться так сильно разбросанные числа, станет понятно, что начиная с некоторого момента мы вместо собственных векторов будем видеть только шум. К счастью, на главные компоненты это не очень влияет.
И у симметрических матриц собственные значения действительно только вещественные. Беда в том, что многим реализациям QR не нравится, когда встречаются кратные значения, и с ними приходится как-то бороться (методы сдвига и т.п.).
В последний раз мне приходилось искать главные компоненты в 441-мерном пространстве. С первой попытки метод не справился, пришлось объяснить ему, что маленькие собственные значения меня не интересуют :)
И у симметрических матриц собственные значения действительно только вещественные. Беда в том, что многим реализациям QR не нравится, когда встречаются кратные значения, и с ними приходится как-то бороться (методы сдвига и т.п.).
В последний раз мне приходилось искать главные компоненты в 441-мерном пространстве. С первой попытки метод не справился, пришлось объяснить ему, что маленькие собственные значения меня не интересуют :)
Если транспонировать матрицу то в ней окажется столько же строк как и размерность входного вектора на предыдущем шаге.
А почему вы только восстанавливаете размерность, а не сами исходные векторы:
x=xreduced*U-1?
А почему вы только восстанавливаете размерность, а не сами исходные векторы:
x=xreduced*U-1?
это и есть восстановление исходного вектора, приведу пример
допустим a симметричная матрица, а вектор x — это тот который будет уменьшен (xr) и восстановлен (xn)
допустим a симметричная матрица, а вектор x — это тот который будет уменьшен (xr) и восстановлен (xn)
>> a = [1 2 3; 2 5 7; 3 7 9]
a =
1 2 3
2 5 7
3 7 9
>> [U S V] = svd(a)
U =
-0.245867 -0.394359 -0.885455
-0.581044 -0.671214 0.460282
-0.775846 0.627657 -0.064110
S =
Diagonal Matrix
15.19313 0 0
0 0.37069 0
0 0 0.17756
V =
-0.245867 0.394359 -0.885455
-0.581044 0.671214 0.460282
-0.775846 -0.627657 -0.064110
>> x = [3 4 5]
x =
3 4 5
>> Ur = U(:, 1:2)
Ur =
-0.24587 -0.39436
-0.58104 -0.67121
-0.77585 0.62766
>> xr = x*Ur
xr =
-6.94101 -0.72965
>> xn = xr*Ur'
xn =
1.9943 4.5228 4.9272
Удивительно, что во всем тексте не упоминается термин «трехдиагональная матрица». А ведь без приведения к трехдиагональному виду сложность QR-алгоритма возрастает на порядок.
Трехдиагонализация Хаусхолдера должна решить эту проблему. А так получается O(n^3) вроде?
действительно я про это не упоминал, про оптимизацию можно отдельный пост катать, но в статье из которой брался алгоритм это упоминается
For example, before applying the QR algorithm, it is common to reduce the matrix A into a simpler form, such as a tridiagonal matrix: performing QR decompositions on the new matrix then becomes much faster. It is also possible to improve the QR iteration method by incorporating shifts and Rayleigh quotients, just as these concepts helped improve the original power iteration method.
For example, before applying the QR algorithm, it is common to reduce the matrix A into a simpler form, such as a tridiagonal matrix: performing QR decompositions on the new matrix then becomes much faster. It is also possible to improve the QR iteration method by incorporating shifts and Rayleigh quotients, just as these concepts helped improve the original power iteration method.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Реализация метода главных компонент на C#