Слияние кода завершено, страница обновится автоматически
Далее будут использоваться два инструмента, которые обычно бывают полезны.
import psutil
process = psutil.Process(os.getpid())
t = process.memory_info()
t.vms, t.rss
# (19475513344, 17856520192)
def mem_usage():
process = psutil.Process(os.getpid())
return process.memory_info().rss / psutil.virtual_memory().total
mem_usage()
# 0.13217061955758594
from time import sleep
# Без использования TQDM
s = 0
for i in range(10):
s += i
sleep(0.2)
print(s)
# 45
# С использованием TQDM
from tqdm import tqdm
s = 0
for i in tqdm(range(10)):
s += i
sleep(0.2)
print(s)
'''
100%|██████████| 10/10 [00:02<00:00, 4.96it/s]
45
'''
Одно интересное применение SVD, с которым я недавно столкнулся, — это использование его для устранения предвзятости в Word2Vec, как описано в статье «Quantization and Reduction for Bias in Word Embeddings» (Bolukbasi et al.).
Word2Vec — это полезная библиотека от Google, которая представляет слова в виде векторов. Сходство между векторами отражает семантику, и можно найти аналогии, например, Париж: Франция :: Токио: Япония.
Источник: «Векторное представление слов» (https://www.tensorflow.org/versions/r0.10/tutorials/word2vec/).
Однако эти вложения могут неявно кодировать предвзятость, например, отец: врач :: мать: медсестра и мужчина: программист компьютера :: женщина: домохозяйка.
Один из способов устранить предвзятость в пространстве включает использование SVD для уменьшения размерности (статья Bolukbasi).
Вы можете прочитать больше о предвзятости во вложениях слов:
Обычно мы говорим об SVD с точки зрения матриц,
,
но мы также можем думать об этом с точки зрения векторов. SVD даёт нам набор ортогональных векторов 
и 
.
,
где 
— скаляр, называемый сингулярным значением.
Вопрос: О чём это вам напоминает?
Связь между SVD и разложением по собственным значениям: левые сингулярные векторы A являются собственными векторами 
. Правые сингулярные векторы A — собственные векторы 
. Неравные нулю сингулярные значения A равны квадратному корню из собственных значений (и ).
SVD является обобщением разложения по собственным значениям. Не все матрицы имеют собственные значения, но все матрицы имеют сингулярные значения.
Давайте забудем о SVD и поговорим о том, как найти собственные значения симметричной положительно определённой матрицы...
Лучший классический метод вычисления SVD — это вариант метода вычисления собственных значений. Помимо их связи с SVD, собственные значения также полезны сами по себе. Вот несколько практических применений разложения по собственным значениям:
Посмотрите видео 3 Blue 1 Brown: «Преобразование базиса» (https://www.youtube.com/watch?v=P2LTAUO1TdA) и «Собственные значения и собственные векторы» (https://www.youtube.com/watch?v=PFDu9oVAE-g).
«Собственные значения — это способ понять суть матрицы... все сложности матрицы исчезают» — Странг.
Терминология: матрица Эрмита — это матрица, равная своей эрмитово сопряжённой. В случае вещественных матриц (которые мы рассматриваем в этом курсе) эрмитовость эквивалентна симметрии.
Соответствующие теоремы:
.Начнём с метода возведения в степень, который находит собственный вектор. Зачем нужен только один собственный вектор? Возможно, вы задаётесь этим вопросом. На самом деле это основа PageRank (прочитайте статью «Ценность 25 миллиардов долларов: собственный вектор, стоящий за линейной алгеброй Google» (http://www.rose-hulman.edu/~bryan/googleFinalVersionFixed.pdf), чтобы узнать больше).
Мы будем использовать данные из набора данных DBpedia, взятые из Википедии, вместо того чтобы пытаться ранжировать важность всех веб-сайтов в Интернете. DBpedia предоставляет структурированные данные из Википедии на 125 языках.
«Полный набор данных DBpedia содержит 38 миллионов тегов и аннотаций, 25 миллионов ссылок на изображения и 29 миллионов внешних веб-страниц; 80 миллионов ссылок на категории Википедии, 41 миллион ссылок на категории YAGO» — (о наборе данных DBpedia). ``` import os, numpy as np, pickle from bz2 import BZ2File from datetime import datetime from pprint import pprint from time import time from tqdm import tqdm_notebook from scipy import sparse
from sklearn.decomposition import randomized_svd from sklearn.externals.joblib import Memory from urllib.request import urlopen
**Здесь и далее перевод кода не приводится, так как он содержит большое количество специальных символов.**
PATH = 'data/dbpedia/' URL_BASE = 'http://downloads.dbpedia.org/3.5.1/en/' filenames = ["redirects_en.nt.bz2", "page_links_en.nt.bz2"]
for filename in filenames: if not os.path.exists(PATH+filename): print("Downloading '%s', please wait..." % filename) open(PATH+filename, 'wb').write(urlopen(URL_BASE+filename).read())
redirects_filename = PATH+filenames[0] page_links_filename = PATH+filenames[1]
Мы будем строить матрицу смежности графа, которая будет показывать, какие страницы указывают на какие другие страницы.
Источник: «PageRank и HyperLink генерируемые тематические исследования» (https://www.slideshare.net/priyabrata232/page-rank-and-hyperlink)
Матрица смежности даст нам информацию о том, сколько существует путей длиной в две вершины от одной вершины до другой. Вы можете увидеть более подробные примеры в этих заметках, например, для авиаперелётов.
Мы хотим отслеживать, какие страницы указывают на какие другие. Мы сохраним эту информацию в квадратной матрице, где элемент $(r, c)$ равен 1, если строка $r$ указывает на столбец $c$.
Вы можете узнать больше о графах здесь.
def get_lines(filename): return (line.split() for line in BZ2File(filename))
Файлы содержат строки вида:
`<http://dbpedia.org/resource/AfghanistanHistory> <http://dbpedia.org/property/redirect> <http://dbpedia.org/resource/History_of_Afghanistan> .`
В следующем срезе `+1, -1` удаляются `<>`.
DBPEDIA_RESOURCE_PREFIX_LEN = len("http://dbpedia.org/resource/") SLICE = slice(DBPEDIA_RESOURCE_PREFIX_LEN + 1, -1)
Перебираем перенаправления и создаём словарь источника к цели.
def get_redirect(targ, redirects): seen = set() while True: transitive_targ = targ targ = redirects.get(targ) if targ is None or targ in seen: break seen.add(targ) return transitive_targ
def get_redirects(redirects_filename): redirects={} lines = get_lines(redirects_filename) return {src[SLICE]:get_redirect(targ[SLICE], redirects) for src,,targ, in tqdm_notebook(lines, leave=False)}
redirects = get_redirects(redirects_filename)
mem_usage()
Добавляем элементы в список, перенаправления, индексную карту, элемент.
limit=119077682 #5000000
index_map = dict() # ссылки->ID lines = get_lines(page_links_filename) source, destination, data = [],[],[] for l, split in tqdm_notebook(enumerate(lines), total=limit): if l >= limit: break add_item(source, redirects, index_map, split[0]) add_item(destination, redirects, index_map, split[2]) data.append(1)
n=len(data); n
### Просмотр наших данных
Следующие шаги предназначены только для иллюстрации информации и структуры наших данных. Они неэффективны.
Давайте посмотрим на тип элемента в `index_map`:
index_map.popitem()
Давайте взглянем на элемент в индексе `9991173` в индексной карте:
`1940_Cincinnati_Reds_Team_Issue` имеет индекс `9991173.` Он появляется только один раз в списке источников:
[i for i,x in enumerate(source) if x == 9991173]
source[119077649], destination[119077649]
Теперь мы хотим проверить, какая страница является источником (с индексом 9991050). Обратите внимание: обычно вы не должны обращаться к словарю по его значению. Это неэффективно и не является способом использования словаря.
for page_name, index in index_map.items(): if index == 9991050: print(page_name)
Мы можем видеть, что проблема с командой Цинциннати Редс 1940 года перенаправляется на W711–2 в Википедии:
test_inds = [i for i,x in enumerate(source) if x == 9991050]
len(test_inds)
test_inds[:5]
test_dests = [destination[i] for i in test_inds]
Теперь мы хотим проверить, какая страница является источником (с индексом 9991174):
for page_name, index in index_map.items(): if index in test_dests:
'''
CPU times: user 8min 40s, sys: 1min 20s, total: 10min 1s
Wall time: 5min 56s
'''
mem_usage()
# 28.353073152
# Согласно основным сингулярным векторам главной страницы Википедии
show_ex(U.T[0])
# List_of_World_War_II_air_aces, List_of_animated_feature-length_films, List_of_animated_feature_films:2000s, International_Swimming_Hall_of_Fame, List_of_museum_ships, List_of_linguists, List_of_television_programs_by_episode_count, List_of_game_show_hosts, List_of_astronomers
show_ex(U.T[1])
# List_of_former_United_States_senators, List_of_United_States_Representatives_from_New_York, List_of_United_States_Representatives_from_Pennsylvania, Members_of_the_110th_United_States_Congress, List_of_Justices_of_the_Ohio_Supreme_Court, Congressional_endorsements_for_the_2008_United_States_presidential_election, List_of_United_States_Representatives_in_the_110th_Congress_by_seniority, List_of_Members_of_the_United_States_House_of_Representatives_in_the_103rd_Congress_by_seniority, List_of_United_States_Representatives_in_the_111th_Congress_by_seniority
show_ex(V[0])
# United_States, Japan, United_Kingdom, Germany, Race_and_ethnicity_in_the_United_States_Census, France, United_States_Army_Air_Forces, Australia, Canada
show_ex(V[1])
# Democratic_Party_%28United_States%29, Republican_Party_%28United_States%29, Democratic-Republican_Party, United_States, Whig_Party_%28United_States%29, Federalist_Party, National_Republican_Party, Catholic_Church, Jacksonian_democracy
**Практика: различные способы нормализации данных. Не перекрывайте матрицу смежности, а создайте новую матрицу. Понимание различий в результатах.**
* Разложение по сингулярным значениям (SVD) включает две основы, разложение по собственным значениям включает одну основу.
* Основы SVD ортогональны, основы разложения по собственным значениям обычно не ортогональны.
* Все матрицы имеют SVD, но не все матрицы (даже не все квадратные матрицы) имеют разложение по собственным значениям.
## QR-алгоритм
Мы используем метод возведения в степень, чтобы найти собственный вектор, соответствующий наибольшему собственному значению матрицы Википедии. Этот собственный вектор даёт нам относительную важность каждой страницы Википедии (аналогично упрощённому PageRank).
Давайте теперь рассмотрим метод поиска всех собственных значений симметричной положительно определённой матрицы. Этот метод включает в себя два основных алгоритма числовой линейной алгебры и является основой для многих более сложных методов.
[Второе собственное значение матрицы Google](https://nlp.stanford.edu/pubs/secondeigenvalue.pdf): «имеет последствия для скорости сходимости стандартного алгоритма PageRank по мере масштабирования веб-сайта, для устойчивости PageRank к возмущениям структуры ссылок в Интернете, для обнаружения спамеров Google и для разработки алгоритмов для ускорения PageRank».
### Избегание путаницы: QR-алгоритм и QR-разложение
QR-алгоритм использует то, что называется QR-разложением. Оба они важны, поэтому не путайте их. QR-разложение разбивает матрицу A = QR на ортогональный столбец Q и треугольную матрицу R. Мы рассмотрим несколько методов вычисления QR-разложения в будущих курсах. Сейчас достаточно знать, что это даёт нам ортогональную матрицу и треугольную матрицу.
### Линейная алгебра
Если существует неособая матрица X:
тогда две матрицы A и B подобны.
Посмотрите это: [Базисная трансформация](https://www.youtube.com/watch?v=P2LTAUO1TdA&index=13&list=PLZHQObOWTQDPD3MizzM2xVFitgF8hE_ab)
Теорема: если X неособен, то A и  имеют одинаковые собственные значения.
### Больше линейной алгебры
Разложение Шура матрицы A представляет собой разложение:
где Q — унитарная матрица, T — верхняя треугольная.
Вопрос: Что вы думаете о собственных значениях A?
Теорема: Каждая квадратная матрица имеет разложение Шура.
### Другие ресурсы
Обзор: [Линейные комбинации, скаляры и базисные векторы](https://www.youtube.com/watch?v=k7RM-ot2NWY&index=3&list=PLZHQObOWTQDPD3MizzM2xVFitgF8hE_ab).
Доказательство этой теоремы (и многое другое!) см. в лекции 24.
### Алгоритм
Основная версия QR-алгоритма:
for k=1,2,... Q, R = A A = R @ Q
При соответствующих предположениях этот алгоритм сходится к форме Шура A!
### Как это работает
Напишите ещё раз, только с нижними индексами:
Для 
Это можно рассматривать как построение последовательности ,  и .
Итак:
Трефетен на страницах 216–217 доказывает следующее:
Ключевые моменты: QR-алгоритм строит ортогональный базис для последовательных степеней A. Помните о тесной связи между собственными значениями и разложением по собственным значениям.
Чтобы узнать больше, прочитайте о релятивистской энтропии.
### Чистый QR
```py
n = 6
A = np.random.rand(n,n)
AT = A @ A.T
def pure_qr(A, max_iter=1000):
Ak = np.copy(A)
n = A.shape[0]
QQ = np.eye(n)
for k in range(max_iter):
Q, R = np.linalg.qr(Ak)
Ak = R @ Q
В этом тексте используется язык программирования Python. **Перевод исходного текста на русский язык:**
Пусть $QQ = QQ @ Q$, если $k$ делится без остатка на 100, то выводим $Ak$ и переходим на новую строку. Затем возвращаем $Ak$ и $QQ$.
$A$ — это двумерный массив:
[[0.62878, 0.23258, 0.63909, 0.90223, 0.94772, 0.80247],
[0.64361, 0.52469, 0.92231, 0.32869, 0.58532, 0.75104],
[0.44363, 0.00427, 0.62418, 0.47093, 0.6762 , 0.28078],
[0.14629, 0.76324, 0.23316, 0.55208, 0.21712, 0.20255],
[0.56122, 0.08282, 0.12788, 0.10419, 0.40358, 0.69272],
[0.41172, 0.06411, 0.92162, 0.53139, 0.27901, 0.61592]]
Затем вычисляем $Ak$ и $Q$ с помощью функции `pure_qr(A)`.
Получаем следующий результат:
[[2.65646 0.21386 0.16765 0.75256 0.61251 0.93518]
[0.52744 0.47579 0.17052 -0.41086 -0.21182 -0.01876]
[0.29923 0.06964 0.11173 0.1879 -0.29101 0.60032]
[0.2274 0.46162 -0.26654 0.08899 0.24631 0.26447]
[-0.06093 0.02892 0.34162 0.07533 0.02393 -0.05456]
[-0.06025 0.02694 -0.11675 -0.00927 -0.11939 -0.00767]]
[[ 0 0.18624 -0.297 -0.07256 -0.04537 0.27907]
[ 0 -0.297 0.18624 0.07256 0.04537 -0.27907]]
[[ 0 0.69328 0.34105 -0.12198 0.11029 0.0992 ]
[ 0 -0.34105 0.69328 -0.11029 -0.12198 -0.0992 ]]
[[ 0 -0.0494 -0.02057 0.09461 0.59466 0.09115]
[ 0 0.0494 0.02057 -0.09461 -0.59466 -0.09115]]
[[ 0 0.00008 -0.02659 -0.40372 0.06542 0.38612]
[ 0 -0.00008 0.02659 0.40372 -0.06542 -0.38612]]
[[ 0 0 0 -0 -0 -0.11832]
[ 0 0 0 0 0 0.11832]]
и так далее.
В итоге получаем следующие результаты:
[[ 2.78023 -0.12185 -0.51401 0.17625 -0.07467 1.15184]
[ 0 0.2117 -0.70351 0.09974 -0.02986 0.00172]
[ 0 0.28284 0.32635 -0.0847 -0.08488 -0.29104]
[-0 -0.00068 -0.00088 -0.01282 0.54836 0.13447]
[-0 0 -0.00102 -0.45718 0.16208 -0.37726]
[-0 0 0 0 0 -0.11832]]
[[ 2.78023 0.35761 0.38941 0.07462 0.17493 1.15184]
[ 0 -0.0597 -0.55441 -0.0681 -0.04456 0.14084]
[ 0 0.43221 0.47853 -0.06068 0.12117 0.25519]
[-0 0 0 0.16206 0.45708 0.37724]
[-0 0 0 -0.54821 -0.01298 0.1336 ]
[ 0 0 0 0 0 -0.11832]]
[[ 2.78023 -0.52782 0.03045 -0.14389 -0.12436 1.15184]
[ 0 0.25091 -0.27593 0.08994 -0.06581 -0.28672]
[ 0 0.7107 0.28732 0.10154 0.04751 -0.05245]
[ 0 0 0 0.0297 -0.59054 -0.01234]
[ 0 0 0 -0.42642 0.01189 -0.34139]
[ 0 0 0 0 0 -0.11832]]
И так далее. Данный текст представляет собой фрагмент технического документа, связанного с областью разработки и тестирования программного обеспечения. В тексте приводятся числовые значения и математические формулы, но нет законченного смыслового содержания.
В тексте присутствуют числовые массивы:
* первый массив состоит из десяти чисел;
* второй массив состоит из пяти чисел.
Также в тексте есть математические функции и операции: np.linalg.eigvals(), np.diag(), @ (символ умножения матриц), np.allclose(), np.linalg.norm().
Текст содержит ссылки на другие источники и упоминает QR-разложение матриц, нахождение собственных значений и векторов матриц. Однако без контекста сложно понять, о чём именно идёт речь в данном фрагменте.
Вы можете оставить комментарий после Вход в систему
Неприемлемый контент может быть отображен здесь и не будет показан на странице. Вы можете проверить и изменить его с помощью соответствующей функции редактирования.
Если вы подтверждаете, что содержание не содержит непристойной лексики/перенаправления на рекламу/насилия/вульгарной порнографии/нарушений/пиратства/ложного/незначительного или незаконного контента, связанного с национальными законами и предписаниями, вы можете нажать «Отправить» для подачи апелляции, и мы обработаем ее как можно скорее.
Опубликовать ( 0 )