Инфраструктура Python. Машинное обучение

Машинное обучение это построение по достаточно большому набору данных $(X, y)_{i=1}^n$ интерполяционной функции из некоторого достаточно богатого пространства, такой что $y \approx F(X)$. Это, например, часто позволяет «предсказывать» значение неизвестной, но полезной взаимосвязи для никогда не наблюдавшегося образца, скажем, распознать речь на впервые встреченном аудио в текст, после тренировки на большом массиве распознанных людьми аудиозаписей.

В машинном обучении выделяют:

  • задачу классификации — $y$ это некоторые категории, часто две, например, «болен» или «здоров», а $X$ данные медобследований
  • задачу регрессии — $y$ это некоторое вещественное число, например «цена», а $X$ характеристики домов
  • задачу кластеризации — unsupervised машинное обучение, $y$ неизвестны, но $X$ с одинаковыми $y$ в каком-то смысле близки. Мы можем сгруппировать похожие рукописные символы на чужом языке, даже если не знаем, какие символы подразумевались
  • поиск аномалий — $y$ неизвестны, но мы хотим опознавать, когда $X$ непохоже на все, виденное ранее, например, если система с многочисленными датчиками впервые начала разваливаться
  • снижение размерности — $y$ неизвестны, имеют значительно меньшую размерность, чем $X$, но тем не менее отображают значительную часть взаимосвязей в исходном $X$. Например, вектор координат помеченных точек лица имеет размерность порядка тысяч, но может быть сжат до 12 координат так, что по ним можно восстановить лицо с хорошей точностью.

Основной библиотекой машинного обучения в Python является sklearn (она же scikit-learn, входит в Anaconda). Для большинства задач она предполагает, что X это векторы фич, записанные построчно, а y вектор предсказываемых величин.

Пример задачи машинного обучения

Чаще всего в решении задачи классификации исследователь:

  • чистит, преобразовывает данные, добавляет ручками фичи
  • разбивает данные с известными ответами (обычно несколькими способами) на train и test подвыборку — кроссвалидация
  • на train выборке тренирует (fit) некоторый классификатор с некоторым набором гиперпараметров
  • на test выборке предсказывает (predict) ответы натренированным классификатором
  • сравнивает вычисленные и известные заранее ответы некоторой функцией качества, усредняя ее по разбиениям на train/test.
  • ориентируясь на функцию качества, меняет входные данные, кроссвалидацию, классификатор или гиперпараметры

В нарративах IPython важно, чтобы при перезапуске кода из нотебука получался тот же результат. Для этого в большинстве алгоритмов библиотек машинного обучения доступен параметр вроде random_state или seed, для того, чтобы выдача ГСЧ совпадала между запусками.

Библиотека sklearn содержит несколько небольших датасетов, которые можно использовать как образцы, например, небольшой датасет про вино: 178 образцов, 13 численных атрибутов для каждого, один из трех классов.

In [12]:
import sklearn.datasets

dataset = sklearn.datasets.load_wine()
print dataset['feature_names']
print dataset['data']
print dataset['target']
['alcohol', 'malic_acid', 'ash', 'alcalinity_of_ash', 'magnesium', 'total_phenols', 'flavanoids', 'nonflavanoid_phenols', 'proanthocyanins', 'color_intensity', 'hue', 'od280/od315_of_diluted_wines', 'proline']
[[  1.42300000e+01   1.71000000e+00   2.43000000e+00 ...,   1.04000000e+00
    3.92000000e+00   1.06500000e+03]
 [  1.32000000e+01   1.78000000e+00   2.14000000e+00 ...,   1.05000000e+00
    3.40000000e+00   1.05000000e+03]
 [  1.31600000e+01   2.36000000e+00   2.67000000e+00 ...,   1.03000000e+00
    3.17000000e+00   1.18500000e+03]
 ..., 
 [  1.32700000e+01   4.28000000e+00   2.26000000e+00 ...,   5.90000000e-01
    1.56000000e+00   8.35000000e+02]
 [  1.31700000e+01   2.59000000e+00   2.37000000e+00 ...,   6.00000000e-01
    1.62000000e+00   8.40000000e+02]
 [  1.41300000e+01   4.10000000e+00   2.74000000e+00 ...,   6.10000000e-01
    1.60000000e+00   5.60000000e+02]]
[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2]
In [8]:
%pylab inline
Populating the interactive namespace from numpy and matplotlib
WARNING: pylab import has clobbered these variables: ['test']
`%matplotlib` prevents importing * from pylab and numpy
In [17]:
xlabel('alcohol')
ylabel('hue')
scatter(
    dataset['data'][:, dataset['feature_names'].index('alcohol')],
    dataset['data'][:, dataset['feature_names'].index('hue')],
    c=dataset['target']
);

Фичи в 2D numpy-массиве, предсказываемая переменная в 1D.

In [28]:
X = dataset['data']
Y = dataset['target']
print X.shape, Y.shape
(178L, 13L) (178L,)

Разбиение данных на 3 примерно равных куска (fold) (на 2 тренируем, на 1 предсказываем), с примерно исходными долями классов (stratified), с перемешиванием

In [13]:
import sklearn.model_selection
import sklearn.ensemble
In [14]:
cv = sklearn.model_selection.StratifiedKFold(n_splits=3, shuffle=True, random_state=0)

В качестве классификатора — простой и безотказный случайный лес на 100 деревьях

In [15]:
rf = sklearn.ensemble.RandomForestClassifier(n_estimators=100, criterion='entropy', random_state=0)
In [18]:
for train, test in cv.split(X, Y):
    X_train = X[train]
    Y_train = Y[train]
    X_test = X[test]
    Y_test = Y[test]
    rf.fit(X_train, Y_train)
    Y_pred_proba = rf.predict_proba(X_test)
    Y_pred = rf.predict(X_test)
    print sklearn.metrics.accuracy_score(Y_test, Y_pred)
0.966666666667
0.983333333333
0.98275862069

Этот цикл по разбиениям кроссвалидации, с fit, predict, функцией качества можно записать в одну строчку

In [11]:
qs = sklearn.model_selection.cross_val_score(rf, X, Y, scoring='accuracy', cv=cv)
print qs
print mean(qs), '±', std(qs)
[ 0.96666667  0.98333333  0.98275862]
0.977586206897 ± 0.00772484488646

Натренированный случайный лес считает статистику о том, по какому признаку чаще всего ветвились деревья, что довольно неплохо соответствует тому, какие признаки важны, а какие нет.

In [15]:
sorted(zip(rf.feature_importances_, dataset['feature_names']), reverse=True)
Out[15]:
[(0.17702664133632834, 'flavanoids'),
 (0.16999140023532355, 'alcohol'),
 (0.15491658127652433, 'proline'),
 (0.13544688063922203, 'color_intensity'),
 (0.094188110714468781, 'od280/od315_of_diluted_wines'),
 (0.068970267741025562, 'total_phenols'),
 (0.06553220208373757, 'hue'),
 (0.045178197289937883, 'malic_acid'),
 (0.028022264615764483, 'magnesium'),
 (0.016848326507225814, 'nonflavanoid_phenols'),
 (0.016296799390085048, 'ash'),
 (0.015298515457697821, 'proanthocyanins'),
 (0.012283812712658942, 'alcalinity_of_ash')]
In [52]:
sklearn.metrics.confusion_matrix(Y, sklearn.model_selection.cross_val_predict(rf, X, Y, cv=cv))
Out[52]:
array([[58,  1,  0],
       [ 1, 68,  2],
       [ 0,  0, 48]], dtype=int64)

Видно, что всего 4 образца были классифицированы неправильно

Датасеты

todo

  • import skdata.iris.view
  • from mnist import load_dataset
  • datasets (fetch_mldata, fetch_olivetti_faces, load_boston, load_digits, load_iris, make_classification, make_blobs)

Подготовка данных

Данные можно шкалировать (линейно [min(x), max(x)] → [0, 1]), стандартизовать (линейно $\bar{x} \rightarrow 0$, $\bar{x} + \sigma \rightarrow 1$) или нормализовать (построчно! $\vec{v} \rightarrow \frac{\vec{v}}{\|\vec{v}\|}$).

In [131]:
import sklearn.preprocessing
data = array([[1, 2, 3, 4], [4, 5, 7, 7], [1, 1, 1, 1]], dtype=float)
print data
print
print sklearn.preprocessing.MinMaxScaler().fit_transform(data)
print sklearn.preprocessing.scale(data)
print sklearn.preprocessing.normalize(data)
[[ 1.  2.  3.  4.]
 [ 4.  5.  7.  7.]
 [ 1.  1.  1.  1.]]

[[ 0.          0.25        0.33333333  0.5       ]
 [ 1.          1.          1.          1.        ]
 [ 0.          0.          0.          0.        ]]
[[-0.70710678 -0.39223227 -0.26726124  0.        ]
 [ 1.41421356  1.37281295  1.33630621  1.22474487]
 [-0.70710678 -0.98058068 -1.06904497 -1.22474487]]
[[ 0.18257419  0.36514837  0.54772256  0.73029674]
 [ 0.33927557  0.42409446  0.59373225  0.59373225]
 [ 0.5         0.5         0.5         0.5       ]]

Подготовка данных

todo

  • preprocessing (Imputer, StandardScaler, scale, normalize/Normalizer, Binarizer, MinMaxScaler, LabelEncoder, PolynomialFeatures)

Извлечение фич

todo

  • feature_extraction.text (CountVectorizer)
  • nltk & K

Кроссвалидация

Зачем нужна странная схема (кроссвалидация): тренировать на одном поднаборе данных, а предсказывать результат на другом? Проблема в том, что чем сложнее классификатор, чем больше разных функций он может представить, тем проще ему просто запомнить тренировочную выборку, а не улавливать какие-то закономерности в аппроксимируемой функции. В таком случае качество на train растет, а на test с какого-то момента (при итеративном построении классификатора) начинает падать. Это явление называется переобучение.

todo bias+variance+noise

http://scikit-learn.org/stable/modules/classes.html#module-sklearn.model_selection

In [2]:
import sklearn.model_selection

Основной рабочей лошадкой в кроссвалидации является KFold, схема при которой данные разбиваются на n_splits примерно равных частей, в качестве test берется одна часть, в качестве train остальные, и так n_splits раз. Объекты кроссвалидации из sklearn выдают пары массивов индексов train, test генератором .split(X[, Y]).

In [31]:
cv = sklearn.model_selection.KFold(n_splits=3)
X_10 = random.random((10, 3))
for train, test in cv.split(X_10):
    print train, test
[4 5 6 7 8 9] [0 1 2 3]
[0 1 2 3 7 8 9] [4 5 6]
[0 1 2 3 4 5 6] [7 8 9]

Почти всегда KFold используется с shuffle=True и установленным random_state, чтобы объекты в части брались вперемешку, а не подряд.

In [32]:
cv = sklearn.model_selection.KFold(n_splits=3, shuffle=True, random_state=0)
for train, test in cv.split(X_10):
    print train, test
[0 1 3 5 6 7] [2 4 8 9]
[0 2 3 4 5 8 9] [1 6 7]
[1 2 4 6 7 8 9] [0 3 5]

Если на некоторый важный класс приходится не так много примеров (если классов много или мало данных), то стоит использовать StratifiedKFold, который пытается разбивать выборку так, чтобы объекты всех классов были представлены более-менее равномерно.

Процедуру KFold (или StratifiedKFold) можно повторять для уменьшения вероятности неожиданностей много (n_repeats) раз, используя RepeatedKFold (или RepeatedStratifiedKFold).

Другая популярная стратегия — разбивать выборку в определенном соотношении на две части n_split раз, она реализована в ShuffleSplit (+StratifiedShuffleSplit).

In [45]:
cv = sklearn.model_selection.ShuffleSplit(n_splits=4, test_size=0.4, random_state=0)
for train, test in cv.split(X_10):
    print train, test
[1 6 7 3 0 5] [2 8 4 9]
[9 8 0 6 7 4] [3 5 1 2]
[5 1 0 6 9 7] [2 3 8 4]
[7 5 8 0 3 4] [6 1 9 2]

Для предсказания временных рядов используют TimeSeriesSplit, при этом объекты должны быть упорядочены по времени. Ряд бьется на n_splits+1 часть (первая может быть длиннее за счет остатка), затем n_splits раз в качестве test выборки берется i+1-й фолд, а в качестве train все до нее.

In [54]:
cv = sklearn.model_selection.TimeSeriesSplit(n_splits=3)
for train, test in cv.split(range(16)):
    print train, test
[0 1 2 3] [4 5 6 7]
[0 1 2 3 4 5 6 7] [ 8  9 10 11]
[ 0  1  2  3  4  5  6  7  8  9 10 11] [12 13 14 15]

Цикл for train, test in cv.split(X, Y) можно не писать самостоятельно, используя функции-обертки cross_val_predict для получения предсказаний классификатора на test-фолдах (расставляемых в соответствии с порядком объектов в X), и cross_val_score для их качества.

In [57]:
cv = sklearn.model_selection.KFold(n_splits=4, shuffle=True, random_state=0)
In [61]:
sklearn.model_selection.cross_val_predict(rf, X, Y, cv=cv)
Out[61]:
array([0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
       0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0,
       0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
       1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1,
       1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
       1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2,
       2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
       2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2])

Вызов с параметром method='predict_proba' вернет 2D массив предсказаний [№ объекта, № класса] = вероятность.

In [59]:
sklearn.model_selection.cross_val_score(rf, X, Y, scoring='neg_log_loss', cv=cv)
Out[59]:
array([-0.12676593, -0.22558422, -0.09682255, -0.12924299])

Качество классификации

Посмотреть на сводную табличку истина—предсказание можно с помощью матрицы конфуза

In [73]:
Y_true = [0,0,0,0,0,0,0,0,0,0, 1,1,1,1,1,1,1,1,1,1]
Y_pred = [0,0,0,0,0,0,0,0,1,1, 1,1,1,1,1,1,1,1,1,0]
In [74]:
sklearn.metrics.confusion_matrix(Y_true, Y_pred)
Out[74]:
array([[8, 2],
       [1, 9]], dtype=int64)
In [76]:
print sklearn.metrics.classification_report(Y_true, Y_pred)
             precision    recall  f1-score   support

          0       0.89      0.80      0.84        10
          1       0.82      0.90      0.86        10

avg / total       0.85      0.85      0.85        20

Чтобы оценивать предсказания классификаторов относительно реальных классов объектов, sklearn предлагает ряд полезных вещественных метрик. Наиболее очевидная из них — accuracy_score, доля совпавших классов. Первым аргументом метрики принимают истинные классы, вторым предсказанные.

In [77]:
sklearn.metrics.accuracy_score(Y_true, Y_pred)
Out[77]:
0.84999999999999998

Например, в медицине часто встречается задача классификации на два класса, где «положительный» класс редок (пациент болен греговирусом), но заметно важнее не пропустить больного, чем лишний раз не обследовать здорового. В таком случае возникают понятия ошибок 1-го и 2-го рода и табличка связанных метрик. True/false относится к тому, угадал ли предиктор, positive/negative к его ответу.

Реальность
+ (болен)− (здоров)
Предсказание+ (болен)TP, true positiveFP, false positive, ошибка 1-го рода
лишние исследования
− (здоров)FN, false negative, ошибка 2-го рода
недиагностированный пациент мертв
TN, true negative

Рассматривают две связанные метрики: Precision = TP/(TP+FP) (сколько из положительных пациентов реально больны) и Recall = TP/(TP+FN) (какую долю больных алгоритм обнаружил).

todo Найти precision-recall анализа на ВИЧ?

In [78]:
sklearn.metrics.precision_score(Y_true, Y_pred)
Out[78]:
0.81818181818181823
In [79]:
sklearn.metrics.recall_score(Y_true, Y_pred)
Out[79]:
0.90000000000000002

Часто Precision и Recall объединяют в одну метрику, F1-score, равный их среднему гармоническому $\frac{2}{\frac{1}{\mathtt{precision}} + \frac{1}{\mathtt{recall}}}$.

In [80]:
sklearn.metrics.f1_score(Y_true, Y_pred)
Out[80]:
0.85714285714285721

Другой вариант двух связанных метрик: Sensitivity = Recall = TP/(TP+FN) (какую долю больных алгоритм обнаружил) и Specificity = TN/(FP+TN) (какой доле здоровых не трепали нервы). Самый взвешенный подход к качеству бинарной классификации — ROC AUC. Классификатор выдает вероятности классов, порог меняют с 0 до 1 и рисуют график FPR—TPR (1−Specificity—Sensitivity). График называется ROC curve (receiver operating characteristic curve), а площадь под ним ROC AUC (area under curve). Если классификатор идеальный, AUC = 1, а если выдает рандом, то 0.5.

In [88]:
Y_true = [0,0,0,0,0,0,0,0,0,0, 1,1,1,1,1,1,1,1,1,1]
Y_pred = [0.1,0.2,0.1,0.3,0.4,0.1,0.2,0.2,0.8,0.7, 0.9,0.7,0.7,0.8,0.95,0.9,0.6,0.8,0.9,0.3]
In [99]:
fpr, tpr, thresholds = sklearn.metrics.roc_curve(Y_true, Y_pred)

gca().set_aspect('equal')
xlabel('TPR')
ylabel('FPR')
xlim([-0.01,1])
ylim([0,1.01])
plot([0,1],[0,1], ls='--', c='gray')
plot(fpr, tpr);
In [90]:
sklearn.metrics.roc_auc_score(Y_true, Y_pred)
Out[90]:
0.90500000000000003

Если важно, чтобы классификатор возвращал как можно более точные значения вероятности принадлежности к классу, стоит оптимизировать $\mathtt{logloss} = -\frac1N\sum_{n=1}^N\ \bigg[y_n \log \hat y_n + (1 - y_n) \log (1 - \hat y_n)\bigg]$ ($y_n$ — реальность, $\hat y_n$ — предсказание вероятности).

In [100]:
sklearn.metrics.log_loss(Y_true, Y_pred)
Out[100]:
0.39541168726698539

todo make_scorer

Классификатор

todo (KNN, RF, SGD, SVC) (predict_proba)

  • dummy (DummyClassifier)
  • neighbors (DistanceMetric, KNeighborsClassifier, KNeighborsRegressor, NearestNeighbors)
    • картинку потому что 3 ваших соседа under age
  • linear_model (ElasticNet, SGDClassifier, Lasso, LinearRegression, LogisticRegression, Ridge!)
  • svm (LinearSVC, SVC)
  • naive_bayes (GaussianNB, MultinomialNB)
  • tree (DecisionTreeClassifier, DecisionTreeRegressor, export_graphviz, ExtraTreeClassifier)
  • ensemble (RandomForestClassifier, RandomForestRegressor, BaggingRegressor, GradientBoostingRegressor)
  • xgboost, lightgbm, catboost

Бустинг

Одним из наиболее успешных и универсальных алгоритмов машинного обучения является хорошо натюненный бустинг над деревьями. Помимо sklearn их реализацию содержат библиотеки xgboost от китайцев, lightgbm от MS и CatBoost от Яндекса, каждая со своими достоинствами.

todo

xgboost (0.40)

xgboost release 0.4
Open project in xgboost/windows with Visual Studio 2013
Visual Studio 2013, Release, x64
Rebuild xgboost, xgboost_wrapper
Copy all file in xgboost/windows/x64/Release folder to xgboost/wrapper
Go to xgboost/python-package, run command python setup.py install


xgboost-0.6
git clone --recursive https://github.com/dmlc/xgboost в какую-нибудь папку
cmake 3.5+, vs 2015 x64
build libxgboost Release -> /lib/libxgboost.dll
cd /python-package; python setup.py install


CatBoost


lightgbm https://github.com/Microsoft/LightGBM
    скачать, windows/LightGBM.sln DLL,x64 build
    python-package, python setup.py install
    https://github.com/Microsoft/LightGBM/blob/master/docs/Parameters.md

Factorization machines

Factorization machines доступны в Python благодаря библиотеке lightfm. Пример использует датасет MovieLens, предразбитый на train и test. В нем одни и те же 943 юзеров оценивают некоторые из 1682 фильмов и нужно предсказать их оценки некоторым другим фильмам (проставленные в test).

todo что он и как предсказывает, и как осмысленно считать и трактовать качество http://lyst.github.io/lightfm/docs/lightfm.html

pip install lightfm
In [30]:
from lightfm import LightFM
from lightfm.datasets import fetch_movielens
from lightfm.evaluation import precision_at_k

# Load the MovieLens 100k dataset. Only five star ratings are treated as positive.
data = fetch_movielens()

# Instantiate and train the model
model = LightFM(loss='warp')
model.fit(data['train'], epochs=30, num_threads=2)

# Evaluate the trained model
test_precision = precision_at_k(model, data['test'], k=5).mean()
In [79]:
indices = []
arr = data['test'].tocsr()
for i in range(943):
    for j in range(1682):
        if arr[i,j]:
            indices.append((i, j))
In [80]:
indices
Out[80]:
[(0, 19),
 (0, 32),
 (0, 60),
 (0, 116),
 (0, 154),
 (0, 159),
 (0, 170),
 (0, 188),
 (0, 201),
 (0, 264),
 (1, 12),
 (1, 49),
 (1, 250),
 (1, 279),
 (1, 280),
 (1, 289),
 (1, 291),
 (1, 296),
 (1, 311),
 (1, 313),
 (2, 244),
 (2, 293),
 (2, 322),
 (2, 327),
 (2, 330),
 (2, 331),
 (2, 333),
 (2, 334),
 (2, 336),
 (2, 342),
 (3, 49),
 (3, 259),
 (3, 263),
 (3, 287),
 (3, 293),
 (3, 302),
 (3, 353),
 (3, 355),
 (3, 356),
 (3, 360),
 (4, 0),
 (4, 1),
 (4, 16),
 (4, 97),
 (4, 109),
 (4, 224),
 (4, 362),
 (4, 423),
 (4, 438),
 (4, 453),
 (5, 13),
 (5, 22),
 (5, 68),
 (5, 85),
 (5, 97),
 (5, 257),
 (5, 300),
 (5, 462),
 (5, 491),
 (5, 516),
 (6, 31),
 (6, 162),
 (6, 381),
 (6, 429),
 (6, 454),
 (6, 478),
 (6, 491),
 (6, 496),
 (6, 647),
 (6, 660),
 (7, 21),
 (7, 49),
 (7, 78),
 (7, 88),
 (7, 181),
 (7, 293),
 (7, 337),
 (7, 384),
 (7, 456),
 (7, 549),
 (8, 5),
 (8, 285),
 (8, 297),
 (8, 339),
 (8, 478),
 (8, 486),
 (8, 506),
 (8, 520),
 (8, 526),
 (8, 690),
 (9, 6),
 (9, 15),
 (9, 99),
 (9, 174),
 (9, 284),
 (9, 460),
 (9, 485),
 (9, 487),
 (9, 503),
 (9, 610),
 (10, 37),
 (10, 109),
 (10, 110),
 (10, 226),
 (10, 424),
 (10, 557),
 (10, 722),
 (10, 724),
 (10, 731),
 (10, 739),
 (11, 81),
 (11, 95),
 (11, 96),
 (11, 131),
 (11, 142),
 (11, 171),
 (11, 203),
 (11, 299),
 (11, 470),
 (11, 734),
 (12, 55),
 (12, 97),
 (12, 185),
 (12, 197),
 (12, 214),
 (12, 271),
 (12, 343),
 (12, 359),
 (12, 525),
 (12, 835),
 (13, 21),
 (13, 97),
 (13, 110),
 (13, 173),
 (13, 212),
 (13, 268),
 (13, 356),
 (13, 473),
 (13, 529),
 (13, 708),
 (14, 24),
 (14, 126),
 (14, 221),
 (14, 330),
 (14, 404),
 (14, 472),
 (14, 677),
 (14, 684),
 (14, 748),
 (14, 931),
 (15, 7),
 (15, 54),
 (15, 63),
 (15, 88),
 (15, 177),
 (15, 193),
 (15, 196),
 (15, 208),
 (15, 704),
 (15, 943),
 (16, 0),
 (16, 8),
 (16, 12),
 (16, 116),
 (16, 124),
 (16, 150),
 (16, 236),
 (16, 244),
 (16, 507),
 (16, 743),
 (17, 25),
 (17, 85),
 (17, 112),
 (17, 181),
 (17, 201),
 (17, 407),
 (17, 442),
 (17, 495),
 (17, 728),
 (17, 949),
 (18, 3),
 (18, 152),
 (18, 200),
 (18, 257),
 (18, 309),
 (18, 312),
 (18, 381),
 (18, 434),
 (18, 654),
 (18, 691),
 (19, 10),
 (19, 117),
 (19, 171),
 (19, 175),
 (19, 185),
 (19, 193),
 (19, 207),
 (19, 287),
 (19, 404),
 (19, 677),
 (20, 102),
 (20, 128),
 (20, 163),
 (20, 221),
 (20, 323),
 (20, 369),
 (20, 439),
 (20, 446),
 (20, 557),
 (20, 947),
 (21, 78),
 (21, 79),
 (21, 127),
 (21, 240),
 (21, 257),
 (21, 375),
 (21, 376),
 (21, 509),
 (21, 510),
 (21, 790),
 (22, 169),
 (22, 171),
 (22, 195),
 (22, 257),
 (22, 322),
 (22, 380),
 (22, 384),
 (22, 403),
 (22, 462),
 (22, 1005),
 (23, 63),
 (23, 128),
 (23, 152),
 (23, 190),
 (23, 366),
 (23, 371),
 (23, 426),
 (23, 661),
 (23, 741),
 (23, 762),
 (24, 24),
 (24, 180),
 (24, 207),
 (24, 221),
 (24, 227),
 (24, 256),
 (24, 257),
 (24, 356),
 (24, 500),
 (24, 614),
 (25, 14),
 (25, 24),
 (25, 124),
 (25, 234),
 (25, 257),
 (25, 454),
 (25, 684),
 (25, 929),
 (25, 1014),
 (25, 1015),
 (26, 120),
 (26, 245),
 (26, 280),
 (26, 297),
 (26, 369),
 (26, 474),
 (26, 595),
 (26, 741),
 (26, 924),
 (26, 977),
 (27, 6),
 (27, 78),
 (27, 94),
 (27, 97),
 (27, 172),
 (27, 200),
 (27, 208),
 (27, 216),
 (27, 233),
 (27, 379),
 (28, 97),
 (28, 188),
 (28, 244),
 (28, 331),
 (28, 357),
 (28, 538),
 (28, 677),
 (28, 688),
 (28, 747),
 (28, 1017),
 (29, 81),
 (29, 180),
 (29, 254),
 (29, 285),
 (29, 288),
 (29, 434),
 (29, 538),
 (29, 677),
 (29, 687),
 (29, 1006),
 (30, 134),
 (30, 301),
 (30, 320),
 (30, 483),
 (30, 492),
 (30, 497),
 (30, 503),
 (30, 681),
 (30, 704),
 (30, 885),
 (31, 116),
 (31, 150),
 (31, 245),
 (31, 248),
 (31, 249),
 (31, 275),
 (31, 289),
 (31, 293),
 (31, 590),
 (31, 1011),
 (32, 257),
 (32, 291),
 (32, 306),
 (32, 312),
 (32, 327),
 (32, 332),
 (32, 342),
 (32, 750),
 (32, 871),
 (32, 894),
 (33, 241),
 (33, 244),
 (33, 258),
 (33, 285),
 (33, 298),
 (33, 309),
 (33, 311),
 (33, 328),
 (33, 331),
 (33, 689),
 (34, 241),
 (34, 242),
 (34, 258),
 (34, 260),
 (34, 321),
 (34, 331),
 (34, 679),
 (34, 876),
 (34, 880),
 (34, 1024),
 (35, 267),
 (35, 268),
 (35, 306),
 (35, 318),
 (35, 338),
 (35, 681),
 (35, 747),
 (35, 881),
 (35, 882),
 (35, 884),
 (36, 54),
 (36, 55),
 (36, 78),
 (36, 116),
 (36, 182),
 (36, 221),
 (36, 287),
 (36, 402),
 (36, 539),
 (36, 684),
 (37, 94),
 (37, 138),
 (37, 152),
 (37, 160),
 (37, 327),
 (37, 431),
 (37, 464),
 (37, 572),
 (37, 678),
 (37, 757),
 (38, 257),
 (38, 299),
 (38, 305),
 (38, 312),
 (38, 314),
 (38, 332),
 (38, 344),
 (38, 346),
 (38, 351),
 (38, 899),
 (39, 242),
 (39, 257),
 (39, 267),
 (39, 270),
 (39, 302),
 (39, 332),
 (39, 339),
 (39, 344),
 (39, 753),
 (39, 879),
 (40, 27),
 (40, 30),
 (40, 97),
 (40, 169),
 (40, 264),
 (40, 312),
 (40, 434),
 (40, 485),
 (40, 745),
 (40, 750),
 (41, 43),
 (41, 95),
 (41, 273),
 (41, 402),
 (41, 422),
 (41, 545),
 (41, 587),
 (41, 624),
 (41, 793),
 (41, 1027),
 (42, 4),
 (42, 13),
 (42, 39),
 (42, 119),
 (42, 136),
 (42, 150),
 (42, 202),
 (42, 203),
 (42, 322),
 (42, 814),
 (43, 14),
 (43, 194),
 (43, 239),
 (43, 257),
 (43, 293),
 (43, 442),
 (43, 448),
 (43, 506),
 (43, 643),
 (43, 659),
 (44, 24),
 (44, 108),
 (44, 117),
 (44, 120),
 (44, 126),
 (44, 471),
 (44, 472),
 (44, 475),
 (44, 762),
 (44, 1060),
 (45, 126),
 (45, 150),
 (45, 180),
 (45, 287),
 (45, 306),
 (45, 312),
 (45, 327),
 (45, 332),
 (45, 689),
 (45, 1061),
 (46, 267),
 (46, 291),
 (46, 301),
 (46, 305),
 (46, 320),
 (46, 322),
 (46, 323),
 (46, 339),
 (46, 682),
 (46, 994),
 (47, 173),
 (47, 209),
 (47, 258),
 (47, 307),
 (47, 308),
 (47, 602),
 (47, 608),
 (47, 660),
 (47, 679),
 (47, 689),
 (48, 46),
 (48, 67),
 (48, 301),
 (48, 546),
 (48, 558),
 (48, 580),
 (48, 624),
 (48, 958),
 (48, 994),
 (48, 1002),
 (49, 8),
 (49, 122),
 (49, 124),
 (49, 245),
 (49, 252),
 (49, 285),
 (49, 324),
 (49, 474),
 (49, 822),
 (49, 1083),
 (50, 63),
 (50, 82),
 (50, 131),
 (50, 147),
 (50, 181),
 (50, 202),
 (50, 484),
 (50, 495),
 (50, 602),
 (50, 678),
 (51, 94),
 (51, 115),
 (51, 249),
 (51, 256),
 (51, 279),
 (51, 404),
 (51, 497),
 (51, 747),
 (51, 1008),
 (51, 1085),
 (52, 23),
 (52, 99),
 (52, 173),
 (52, 180),
 (52, 198),
 (52, 227),
 (52, 249),
 (52, 280),
 (52, 844),
 (52, 923),
 (53, 105),
 (53, 267),
 (53, 297),
 (53, 301),
 (53, 312),
 (53, 594),
 (53, 675),
 (53, 684),
 (53, 741),
 (53, 819),
 (54, 55),
 (54, 88),
 (54, 143),
 (54, 253),
 (54, 256),
 (54, 404),
 (54, 677),
 (54, 684),
 (54, 1015),
 (54, 1088),
 (55, 70),
 (55, 90),
 (55, 120),
 (55, 221),
 (55, 446),
 (55, 448),
 (55, 545),
 (55, 754),
 (55, 868),
 (55, 1046),
 (56, 27),
 (56, 78),
 (56, 203),
 (56, 242),
 (56, 303),
 (56, 418),
 (56, 681),
 (56, 755),
 (56, 759),
 (56, 1046),
 (57, 8),
 (57, 99),
 (57, 108),
 (57, 143),
 (57, 172),
 (57, 213),
 (57, 267),
 (57, 708),
 (57, 1097),
 (57, 1098),
 (58, 22),
 (58, 91),
 (58, 195),
 (58, 234),
 (58, 322),
 (58, 467),
 (58, 484),
 (58, 714),
 (58, 741),
 (58, 950),
 (59, 59),
 (59, 161),
 (59, 207),
 (59, 221),
 (59, 402),
 (59, 426),
 (59, 429),
 (59, 524),
 (59, 603),
 (59, 1020),
 (60, 242),
 (60, 303),
 (60, 322),
 (60, 327),
 (60, 330),
 (60, 341),
 (60, 346),
 (60, 677),
 (60, 689),
 (60, 1126),
 (61, 11),
 (61, 20),
 (61, 64),
 (61, 67),
 (61, 256),
 (61, 381),
 (61, 497),
 (61, 664),
 (61, 711),
 (61, 1015),
 (62, 19),
 (62, 49),
 (62, 99),
 (62, 241),
 (62, 276),
 (62, 288),
 (62, 761),
 (62, 1006),
 (62, 1027),
 (62, 1066),
 (63, 159),
 (63, 175),
 (63, 380),
 (63, 391),
 (63, 432),
 (63, 515),
 (63, 683),
 (63, 735),
 (63, 777),
 (63, 1062),
 (64, 46),
 (64, 55),
 (64, 96),
 (64, 99),
 (64, 124),
 (64, 195),
 (64, 201),
 (64, 675),
 (64, 805),
 (64, 1141),
 (65, 0),
 (65, 6),
 (65, 116),
 (65, 180),
 (65, 248),
 (65, 257),
 (65, 297),
 (65, 470),
 (65, 596),
 (65, 876),
 (66, 0),
 (66, 63),
 (66, 120),
 (66, 146),
 (66, 150),
 (66, 239),
 (66, 404),
 (66, 742),
 (66, 1092),
 (66, 1094),
 (67, 6),
 (67, 116),
 (67, 117),
 (67, 177),
 (67, 236),
 (67, 244),
 (67, 404),
 (67, 410),
 (67, 741),
 (67, 1046),
 (68, 11),
 (68, 55),
 (68, 173),
 (68, 174),
 (68, 239),
 (68, 255),
 (68, 257),
 (68, 267),
 (68, 299),
 (68, 426),
 (69, 49),
 (69, 81),
 (69, 209),
 (69, 216),
 (69, 398),
 (69, 418),
 (69, 430),
 (69, 583),
 (69, 745),
 (69, 1132),
 (70, 55),
 (70, 88),
 (70, 133),
 (70, 221),
 (70, 275),
 (70, 284),
 (70, 345),
 (70, 461),
 (70, 474),
 (70, 922),
 (71, 47),
 (71, 53),
 (71, 181),
 (71, 194),
 (71, 233),
 (71, 567),
 (71, 678),
 (71, 698),
 (71, 865),
 (71, 1109),
 (72, 11),
 (72, 55),
 (72, 93),
 (72, 126),
 (72, 205),
 (72, 356),
 (72, 474),
 (72, 479),
 (72, 587),
 (72, 656),
 (73, 8),
 (73, 14),
 (73, 99),
 (73, 125),
 (73, 236),
 (73, 271),
 (73, 284),
 (73, 287),
 (73, 325),
 (73, 1083),
 (74, 120),
 (74, 146),
 (74, 236),
 (74, 239),
 (74, 283),
 (74, 408),
 (74, 475),
 (74, 495),
 (74, 545),
 (74, 1016),
 (75, 60),
 (75, 91),
 (75, 99),
 (75, 134),
 (75, 174),
 (75, 275),
 (75, 530),
 (75, 581),
 (75, 810),
 (75, 1128),
 (76, 22),
 (76, 90),
 (76, 124),
 (76, 167),
 (76, 171),
 (76, 194),
 (76, 237),
 (76, 473),
 (76, 483),
 (76, 517),
 (77, 254),
 (77, 256),
 (77, 268),
 (77, 288),
 (77, 297),
 (77, 300),
 (77, 322),
 (77, 411),
 (77, 1046),
 (77, 1159),
 (78, 49),
 (78, 99),
 (78, 123),
 (78, 245),
 (78, 268),
 (78, 287),
 (78, 302),
 (78, 507),
 (78, 936),
 (78, 1160),
 (79, 44),
 (79, 49),
 (79, 57),
 (79, 86),
 (79, 193),
 (79, 268),
 (79, 422),
 (79, 465),
 (79, 581),
 (79, 885),
 (80, 2),
 (80, 168),
 (80, 272),
 (80, 279),
 (80, 410),
 (80, 431),
 (80, 470),
 (80, 475),
 (80, 741),
 (80, 823),
 (81, 55),
 (81, 134),
 (81, 182),
 (81, 193),
 (81, 476),
 (81, 507),
 (81, 596),
 (81, 716),
 (81, 755),
 (81, 1133),
 (82, 77),
 (82, 96),
 (82, 209),
 (82, 214),
 (82, 233),
 (82, 280),
 (82, 384),
 (82, 575),
 (82, 622),
 (82, 659),
 (83, 11),
 (83, 120),
 (83, 288),
 (83, 321),
 (83, 404),
 (83, 527),
 (83, 528),
 (83, 741),
 (83, 747),
 (83, 1032),
 (84, 24),
 (84, 50),
 (84, 227),
 (84, 258),
 (84, 426),
 (84, 432),
 (84, 506),
 (84, 587),
 (84, 641),
 (84, 1064),
 (85, 257),
 (85, 285),
 (85, 299),
 (85, 318),
 (85, 326),
 (85, 871),
 (85, 878),
 (85, 880),
 (85, 888),
 (85, 1174),
 (86, 39),
 (86, 81),
 (86, 209),
 (86, 273),
 (86, 366),
 (86, 383),
 (86, 400),
 (86, 553),
 (86, 584),
 (86, 1015),
 (87, 260),
 (87, 300),
 (87, 301),
 (87, 314),
 (87, 320),
 (87, 689),
 (87, 749),
 (87, 880),
 (87, 885),
 (87, 903),
 (88, 116),
 (88, 126),
 (88, 196),
 (88, 215),
 (88, 220),
 (88, 245),
 (88, 380),
 (88, 731),
 (88, 935),
 (88, 1047),
 (89, 24),
 (89, 97),
 (89, 258),
 (89, 288),
 (89, 346),
 (89, 381),
 (89, 647),
 (89, 899),
 (89, 1085),
 (89, 1197),
 (90, 27),
 (90, 171),
 (90, 192),
 (90, 263),
 (90, 322),
 (90, 422),
 (90, 426),
 (90, 479),
 (90, 506),
 (90, 682),
 (91, 76),
 (91, 167),
 (91, 171),
 (91, 228),
 (91, 500),
 (91, 586),
 (91, 738),
 (91, 793),
 (91, 1048),
 (91, 1078),
 (92, 14),
 (92, 221),
 (92, 234),
 (92, 274),
 (92, 411),
 (92, 475),
 (92, 476),
 (92, 814),
 (92, 819),
 (92, 844),
 (93, 61),
 (93, 183),
 (93, 264),
 (93, 342),
 (93, 719),
 (93, 743),
 (93, 788),
 (93, 1216),
 (93, 1219),
 (93, 1223),
 (94, 0),
 (94, 67),
 (94, 134),
 (94, 171),
 (94, 232),
 (94, 526),
 (94, 545),
 (94, 624),
 (94, 786),
 (94, 1216),
 (95, 7),
 (95, 86),
 (95, 90),
 (95, 152),
 (95, 155),
 (95, 478),
 (95, 483),
 (95, 518),
 (95, 644),
 (95, 672),
 (96, 49),
 (96, 88),
 (96, 97),
 (96, 114),
 (96, 193),
 (96, 221),
 (96, 227),
 (96, 481),
 (96, 483),
 (96, 669),
 (97, 46),
 (97, 69),
 (97, 115),
 (97, 162),
 (97, 208),
 (97, 320),
 (97, 516),
 (97, 654),
 (97, 744),
 (97, 937),
 (98, 3),
 (98, 49),
 (98, 78),
 (98, 110),
 (98, 245),
 (98, 267),
 (98, 273),
 (98, 402),
 (98, 872),
 (98, 1015),
 (99, 265),
 (99, 267),
 (99, 287),
 (99, 301),
 (99, 320),
 (99, 339),
 (99, 343),
 (99, 353),
 (99, 354),
 (99, 749),
 ...]
In [78]:
data['test'].tocsr()[1,1]
Out[78]:
0
In [62]:
len(data['test'].data)
Out[62]:
9430
In [67]:
len(data['test'].tocsr().indices)
Out[67]:
9430
In [85]:
userids, movieids = zip(*indices)
In [107]:
len(userids), len(movieids)
Out[107]:
(9430, 9430)
In [89]:
model.predict(array(userids), array(movieids))
Out[89]:
array([-6.99811459, -6.43219757, -7.19871473, ..., -4.63822937,
       -4.38094759, -5.96341372])
In [102]:
print data['test'].tocsr()[userids, movieids].tolist()[0]
[4, 4, 4, 3, 2, 4, 5, 3, 5, 4, 4, 5, 5, 3, 3, 3, 4, 4, 3, 1, 1, 2, 2, 5, 4, 1, 3, 1, 1, 3, 5, 4, 3, 4, 5, 5, 5, 3, 4, 5, 4, 3, 4, 3, 1, 2, 3, 1, 1, 1, 5, 4, 3, 3, 5, 2, 2, 4, 5, 4, 4, 4, 4, 3, 4, 4, 5, 4, 5, 5, 5, 5, 4, 4, 5, 3, 4, 1, 1, 3, 5, 5, 5, 4, 4, 5, 4, 4, 3, 5, 4, 4, 5, 3, 5, 3, 4, 5, 5, 5, 3, 3, 4, 3, 4, 3, 5, 3, 3, 4, 4, 4, 5, 5, 5, 4, 5, 4, 5, 5, 5, 4, 4, 3, 5, 4, 2, 4, 3, 2, 3, 3, 3, 5, 5, 4, 2, 4, 5, 5, 3, 2, 3, 3, 2, 1, 1, 4, 1, 1, 5, 5, 5, 2, 5, 5, 5, 5, 5, 1, 4, 3, 3, 3, 1, 4, 2, 2, 3, 3, 4, 4, 5, 4, 3, 5, 3, 5, 3, 3, 4, 4, 3, 4, 4, 2, 3, 5, 3, 3, 2, 4, 3, 2, 3, 3, 2, 1, 3, 4, 1, 4, 5, 2, 4, 1, 1, 5, 5, 1, 4, 4, 5, 3, 5, 3, 1, 5, 4, 1, 4, 4, 2, 5, 2, 4, 4, 4, 4, 3, 5, 3, 4, 5, 2, 4, 5, 5, 4, 5, 5, 5, 4, 4, 4, 4, 5, 4, 3, 5, 4, 3, 4, 2, 3, 3, 3, 2, 3, 3, 4, 4, 3, 4, 4, 2, 2, 3, 3, 2, 5, 4, 3, 5, 3, 3, 4, 3, 4, 4, 4, 4, 3, 4, 2, 2, 3, 2, 2, 4, 4, 4, 4, 5, 2, 5, 3, 2, 3, 5, 4, 4, 4, 5, 5, 4, 5, 2, 5, 2, 3, 3, 4, 4, 4, 4, 3, 3, 3, 4, 4, 4, 3, 5, 4, 4, 4, 4, 3, 3, 5, 4, 2, 5, 5, 4, 4, 5, 5, 4, 2, 2, 4, 3, 3, 4, 4, 2, 2, 3, 2, 3, 4, 2, 5, 1, 4, 5, 5, 5, 3, 5, 4, 4, 4, 3, 4, 5, 2, 3, 5, 2, 5, 5, 4, 1, 5, 1, 5, 1, 4, 3, 3, 4, 4, 4, 3, 4, 5, 3, 2, 3, 4, 2, 4, 4, 2, 4, 4, 3, 4, 3, 4, 4, 3, 3, 3, 4, 3, 4, 3, 5, 5, 3, 5, 3, 5, 3, 3, 4, 4, 2, 3, 4, 4, 4, 4, 4, 3, 4, 4, 5, 4, 4, 4, 5, 5, 3, 3, 5, 4, 5, 4, 4, 5, 3, 3, 3, 2, 2, 5, 4, 4, 2, 3, 5, 4, 5, 5, 5, 4, 4, 5, 4, 4, 2, 3, 5, 3, 3, 5, 3, 4, 5, 3, 4, 4, 5, 3, 4, 5, 1, 4, 5, 2, 3, 3, 2, 3, 2, 4, 4, 2, 3, 5, 2, 1, 5, 3, 5, 4, 5, 4, 3, 3, 4, 1, 4, 3, 3, 4, 4, 3, 3, 3, 4, 5, 4, 5, 4, 3, 5, 5, 4, 5, 3, 2, 4, 3, 3, 3, 5, 4, 4, 4, 3, 5, 3, 5, 3, 4, 5, 5, 2, 3, 1, 3, 1, 1, 1, 4, 4, 5, 5, 4, 5, 3, 3, 3, 4, 4, 5, 4, 3, 5, 3, 3, 3, 2, 4, 4, 5, 4, 4, 5, 2, 5, 5, 4, 2, 5, 5, 5, 1, 4, 3, 2, 5, 3, 3, 5, 4, 5, 4, 3, 5, 5, 5, 4, 5, 2, 4, 3, 5, 2, 2, 5, 3, 2, 4, 4, 3, 4, 1, 2, 3, 4, 2, 4, 4, 3, 4, 5, 3, 4, 2, 3, 5, 3, 3, 4, 4, 4, 3, 2, 5, 4, 4, 5, 3, 2, 3, 5, 3, 4, 5, 4, 5, 4, 4, 3, 3, 3, 5, 4, 4, 4, 5, 3, 1, 3, 5, 4, 3, 4, 5, 5, 4, 5, 4, 3, 4, 2, 5, 5, 3, 3, 1, 1, 1, 5, 5, 5, 3, 3, 5, 4, 5, 3, 3, 4, 4, 4, 4, 4, 5, 3, 3, 3, 3, 5, 5, 3, 3, 4, 3, 4, 5, 5, 5, 4, 3, 5, 5, 4, 4, 2, 3, 4, 3, 5, 4, 1, 5, 3, 5, 4, 4, 2, 5, 4, 4, 4, 3, 4, 5, 3, 3, 4, 3, 4, 3, 2, 1, 2, 3, 1, 5, 3, 5, 4, 4, 5, 5, 4, 5, 4, 3, 4, 5, 4, 3, 3, 4, 3, 5, 5, 5, 5, 4, 4, 4, 3, 4, 3, 5, 1, 4, 1, 5, 4, 5, 5, 5, 5, 3, 4, 3, 2, 2, 4, 3, 4, 4, 3, 3, 3, 5, 3, 4, 4, 4, 4, 4, 2, 2, 3, 2, 2, 3, 3, 3, 3, 4, 3, 2, 3, 1, 1, 2, 2, 4, 5, 4, 4, 5, 4, 4, 4, 4, 5, 4, 5, 3, 3, 5, 5, 3, 4, 4, 2, 2, 3, 2, 3, 3, 4, 3, 4, 3, 5, 3, 3, 3, 4, 3, 2, 2, 5, 5, 3, 5, 5, 4, 4, 4, 2, 4, 4, 4, 5, 4, 3, 4, 1, 4, 2, 5, 5, 5, 5, 5, 5, 5, 1, 5, 4, 5, 5, 3, 5, 5, 2, 3, 4, 5, 4, 4, 4, 5, 4, 4, 3, 4, 2, 5, 4, 4, 4, 3, 3, 4, 4, 3, 2, 3, 2, 3, 1, 3, 5, 4, 4, 4, 2, 4, 5, 4, 3, 4, 3, 2, 4, 4, 1, 4, 4, 3, 3, 3, 5, 4, 3, 4, 4, 4, 2, 4, 2, 3, 5, 4, 5, 4, 4, 4, 5, 4, 5, 4, 5, 5, 4, 5, 3, 5, 5, 5, 3, 5, 4, 3, 5, 3, 2, 3, 5, 3, 3, 3, 5, 5, 4, 1, 3, 3, 1, 4, 1, 5, 2, 3, 2, 4, 1, 3, 4, 2, 4, 4, 3, 3, 2, 3, 3, 2, 4, 3, 3, 3, 3, 2, 3, 2, 3, 1, 3, 3, 2, 3, 4, 5, 4, 3, 5, 4, 4, 3, 3, 5, 2, 4, 2, 3, 3, 2, 2, 1, 1, 1, 5, 4, 5, 4, 4, 4, 2, 4, 3, 3, 4, 4, 3, 4, 4, 4, 3, 4, 4, 2, 4, 4, 5, 2, 1, 4, 4, 2, 3, 5, 3, 4, 4, 3, 3, 3, 3, 5, 3, 4, 4, 3, 3, 2, 3, 4, 1, 4, 3, 4, 3, 2, 4, 3, 3, 4, 1, 3, 2, 2, 5, 3, 4, 4, 3, 4, 4, 3, 2, 3, 5, 5, 4, 1, 4, 3, 4, 3, 4, 1, 4, 5, 2, 4, 3, 5, 5, 3, 5, 5, 2, 5, 5, 3, 4, 3, 4, 3, 3, 5, 5, 4, 3, 4, 5, 4, 5, 2, 4, 4, 2, 3, 4, 3, 4, 3, 3, 3, 3, 3, 5, 5, 4, 4, 5, 5, 5, 2, 3, 2, 5, 5, 5, 5, 4, 5, 5, 5, 5, 5, 5, 5, 5, 5, 4, 5, 4, 3, 5, 5, 4, 5, 3, 3, 2, 4, 5, 4, 2, 4, 5, 5, 1, 2, 3, 3, 2, 5, 3, 3, 5, 4, 4, 5, 3, 4, 4, 5, 5, 2, 3, 4, 5, 5, 5, 4, 3, 3, 3, 4, 5, 3, 3, 4, 2, 5, 4, 1, 4, 4, 4, 5, 5, 5, 2, 5, 1, 4, 3, 2, 3, 4, 4, 3, 3, 3, 2, 5, 5, 2, 4, 5, 5, 1, 1, 4, 5, 5, 4, 5, 4, 4, 4, 4, 1, 4, 3, 4, 5, 4, 4, 3, 4, 3, 2, 3, 2, 2, 1, 2, 4, 3, 4, 4, 4, 3, 3, 4, 3, 3, 4, 5, 4, 3, 3, 2, 5, 5, 4, 4, 4, 5, 4, 4, 4, 4, 3, 3, 4, 5, 5, 1, 5, 3, 3, 4, 4, 2, 3, 3, 4, 2, 3, 3, 5, 4, 2, 4, 5, 4, 4, 3, 3, 2, 3, 4, 2, 3, 3, 3, 5, 4, 4, 4, 5, 4, 2, 4, 4, 4, 5, 5, 5, 5, 4, 5, 5, 4, 5, 4, 5, 4, 4, 4, 5, 4, 4, 4, 4, 5, 5, 3, 4, 4, 4, 5, 4, 4, 4, 4, 3, 4, 4, 3, 4, 3, 3, 3, 2, 4, 5, 4, 3, 5, 5, 5, 5, 5, 2, 3, 4, 4, 3, 5, 5, 4, 1, 4, 3, 4, 4, 5, 3, 5, 4, 5, 5, 5, 3, 3, 3, 3, 4, 5, 3, 4, 4, 4, 4, 3, 2, 5, 5, 2, 3, 2, 2, 2, 1, 3, 4, 3, 4, 3, 4, 4, 3, 1, 5, 4, 4, 4, 5, 4, 5, 4, 4, 4, 2, 5, 4, 5, 5, 1, 5, 2, 1, 5, 4, 5, 5, 3, 4, 2, 2, 1, 2, 2, 2, 4, 4, 4, 2, 2, 4, 5, 4, 5, 4, 1, 5, 5, 3, 2, 5, 4, 3, 5, 5, 3, 3, 5, 5, 5, 3, 5, 3, 2, 5, 5, 2, 5, 5, 3, 1, 2, 3, 2, 3, 2, 3, 5, 3, 4, 2, 4, 4, 4, 4, 4, 4, 3, 3, 4, 2, 2, 2, 2, 2, 2, 3, 4, 3, 4, 4, 3, 3, 4, 5, 4, 3, 5, 5, 1, 5, 4, 4, 3, 2, 3, 4, 3, 2, 4, 4, 3, 2, 3, 5, 4, 4, 5, 4, 4, 4, 3, 4, 3, 5, 2, 5, 4, 4, 5, 5, 5, 5, 2, 4, 3, 4, 1, 4, 2, 1, 2, 5, 3, 1, 3, 4, 4, 4, 4, 2, 4, 3, 4, 4, 5, 4, 4, 4, 4, 3, 3, 3, 3, 4, 4, 5, 4, 4, 2, 4, 4, 3, 5, 5, 4, 3, 5, 4, 5, 2, 3, 4, 5, 4, 5, 4, 3, 5, 5, 5, 5, 4, 1, 2, 4, 1, 1, 3, 1, 3, 4, 4, 4, 1, 5, 5, 2, 1, 4, 2, 4, 4, 5, 5, 3, 4, 5, 4, 5, 1, 4, 3, 3, 5, 5, 5, 3, 5, 3, 5, 3, 4, 5, 3, 5, 3, 4, 4, 4, 4, 3, 4, 4, 3, 3, 4, 4, 3, 3, 3, 3, 4, 3, 3, 3, 5, 4, 5, 4, 5, 4, 4, 5, 5, 3, 1, 5, 4, 5, 1, 1, 5, 5, 5, 5, 4, 2, 4, 3, 5, 3, 4, 5, 3, 1, 4, 5, 3, 2, 3, 5, 5, 3, 1, 4, 5, 1, 4, 4, 4, 1, 4, 2, 4, 3, 4, 4, 4, 3, 4, 4, 4, 4, 3, 4, 5, 4, 5, 5, 1, 1, 4, 1, 5, 4, 1, 5, 3, 3, 4, 5, 5, 3, 4, 3, 2, 4, 2, 1, 1, 2, 1, 1, 1, 1, 5, 3, 3, 5, 3, 3, 5, 3, 3, 4, 3, 3, 1, 4, 2, 4, 5, 3, 4, 3, 4, 3, 4, 4, 3, 3, 5, 2, 3, 4, 4, 4, 5, 4, 4, 4, 5, 5, 4, 4, 4, 1, 3, 4, 3, 4, 5, 5, 4, 3, 4, 5, 4, 5, 4, 4, 3, 5, 3, 3, 4, 5, 5, 3, 5, 3, 4, 4, 5, 2, 5, 5, 5, 4, 5, 4, 3, 4, 4, 5, 4, 4, 3, 5, 1, 3, 3, 4, 2, 2, 4, 3, 4, 4, 3, 5, 3, 3, 3, 3, 4, 1, 4, 5, 4, 2, 3, 4, 4, 5, 1, 4, 3, 4, 4, 3, 3, 3, 4, 4, 3, 3, 4, 3, 3, 2, 2, 4, 2, 2, 3, 4, 4, 3, 4, 4, 4, 4, 4, 1, 5, 4, 4, 3, 3, 4, 4, 4, 5, 5, 3, 5, 3, 4, 3, 3, 4, 5, 5, 1, 4, 3, 1, 2, 5, 4, 3, 4, 3, 3, 4, 5, 4, 5, 1, 2, 1, 4, 1, 1, 5, 5, 5, 5, 5, 5, 5, 5, 5, 4, 1, 5, 4, 3, 3, 1, 4, 2, 2, 4, 3, 2, 3, 4, 3, 1, 3, 4, 1, 5, 4, 4, 3, 5, 1, 2, 3, 5, 3, 4, 3, 4, 4, 2, 3, 5, 1, 4, 5, 1, 3, 3, 4, 3, 3, 4, 4, 4, 1, 1, 1, 5, 5, 1, 4, 1, 1, 2, 4, 1, 3, 3, 2, 3, 4, 5, 2, 3, 3, 2, 5, 5, 4, 3, 5, 1, 4, 4, 4, 5, 4, 5, 2, 2, 2, 2, 4, 1, 3, 2, 3, 4, 4, 5, 5, 5, 5, 5, 4, 5, 4, 1, 5, 3, 4, 2, 3, 4, 3, 2, 1, 1, 3, 5, 4, 5, 4, 4, 4, 5, 4, 3, 5, 5, 4, 1, 5, 3, 4, 4, 4, 3, 4, 4, 3, 4, 3, 4, 4, 3, 4, 5, 4, 3, 4, 4, 4, 2, 4, 5, 5, 5, 2, 4, 5, 5, 3, 4, 3, 4, 3, 4, 5, 1, 5, 4, 2, 5, 4, 4, 4, 3, 3, 5, 3, 4, 3, 3, 5, 3, 1, 1, 5, 5, 5, 4, 1, 4, 3, 3, 5, 5, 4, 4, 4, 4, 1, 3, 3, 4, 5, 4, 4, 4, 4, 3, 4, 3, 4, 2, 4, 4, 4, 3, 2, 4, 3, 5, 4, 3, 2, 3, 4, 3, 1, 3, 3, 1, 2, 2, 3, 3, 4, 4, 4, 4, 3, 1, 3, 2, 4, 5, 2, 5, 4, 5, 5, 5, 4, 4, 4, 5, 4, 3, 5, 4, 5, 4, 2, 4, 3, 4, 2, 4, 3, 4, 3, 5, 5, 4, 1, 3, 4, 5, 4, 3, 3, 4, 4, 1, 1, 4, 2, 1, 1, 1, 4, 1, 2, 1, 3, 4, 4, 5, 5, 4, 4, 5, 5, 2, 4, 5, 3, 1, 4, 4, 4, 3, 4, 4, 4, 2, 5, 5, 5, 4, 2, 5, 3, 5, 5, 3, 4, 5, 4, 5, 4, 4, 4, 5, 3, 4, 4, 4, 3, 3, 4, 2, 3, 3, 5, 4, 4, 4, 5, 4, 5, 4, 4, 4, 5, 3, 4, 3, 2, 5, 4, 5, 3, 5, 4, 4, 5, 4, 4, 4, 2, 4, 5, 5, 4, 3, 3, 3, 3, 4, 3, 3, 2, 3, 5, 4, 5, 5, 3, 5, 5, 5, 5, 5, 5, 5, 4, 3, 5, 5, 3, 3, 3, 5, 4, 3, 4, 4, 3, 2, 2, 5, 5, 4, 4, 4, 3, 5, 5, 5, 5, 5, 5, 5, 4, 3, 2, 2, 4, 4, 3, 3, 4, 4, 2, 2, 3, 4, 4, 1, 3, 4, 2, 4, 3, 4, 2, 4, 4, 4, 1, 3, 2, 5, 2, 5, 3, 2, 3, 5, 1, 4, 4, 4, 4, 5, 5, 4, 4, 4, 2, 4, 5, 3, 5, 5, 3, 3, 4, 3, 2, 2, 5, 4, 5, 4, 4, 3, 5, 3, 4, 4, 5, 2, 4, 3, 4, 2, 4, 3, 4, 4, 4, 5, 3, 4, 4, 4, 5, 2, 3, 3, 2, 5, 4, 5, 5, 4, 5, 5, 4, 4, 3, 4, 4, 4, 5, 4, 4, 2, 5, 5, 3, 3, 3, 4, 1, 4, 4, 3, 3, 2, 4, 3, 4, 2, 4, 3, 1, 2, 3, 3, 1, 1, 5, 4, 3, 3, 4, 4, 5, 4, 5, 2, 5, 4, 4, 3, 5, 4, 4, 4, 4, 2, 3, 1, 5, 4, 5, 3, 4, 5, 5, 1, 4, 4, 4, 4, 3, 3, 4, 2, 4, 4, 3, 3, 2, 4, 5, 1, 4, 5, 5, 5, 4, 4, 4, 4, 5, 5, 4, 3, 5, 5, 3, 5, 3, 3, 3, 4, 3, 3, 2, 4, 4, 3, 5, 4, 5, 5, 4, 4, 3, 4, 3, 4, 5, 3, 2, 5, 5, 4, 5, 4, 2, 3, 4, 2, 2, 4, 3, 4, 3, 5, 3, 4, 4, 4, 3, 4, 4, 4, 3, 2, 4, 3, 4, 3, 4, 4, 3, 5, 4, 3, 2, 3, 1, 4, 2, 4, 3, 2, 2, 2, 1, 4, 4, 2, 5, 3, 4, 4, 5, 1, 5, 4, 4, 5, 5, 4, 5, 4, 5, 5, 3, 3, 5, 5, 4, 4, 4, 4, 3, 2, 4, 4, 5, 4, 5, 4, 5, 4, 5, 2, 4, 4, 4, 4, 4, 3, 3, 4, 3, 5, 5, 5, 2, 5, 4, 4, 3, 5, 5, 5, 3, 4, 3, 4, 2, 3, 3, 3, 3, 2, 4, 3, 3, 3, 3, 3, 3, 1, 4, 3, 4, 4, 3, 4, 3, 5, 4, 4, 3, 4, 5, 4, 5, 5, 2, 5, 4, 4, 5, 5, 4, 5, 4, 3, 4, 3, 4, 1, 1, 2, 4, 5, 3, 2, 3, 3, 5, 4, 3, 2, 2, 4, 4, 4, 2, 4, 3, 4, 2, 2, 5, 4, 3, 4, 4, 5, 3, 1, 5, 3, 4, 5, 4, 4, 5, 5, 4, 4, 4, 5, 4, 2, 4, 4, 4, 3, 3, 3, 3, 3, 5, 5, 4, 4, 3, 4, 5, 5, 5, 2, 4, 4, 5, 4, 4, 2, 5, 4, 5, 5, 5, 5, 5, 5, 1, 4, 5, 5, 4, 4, 5, 3, 5, 4, 5, 4, 3, 2, 3, 2, 3, 4, 4, 3, 2, 1, 4, 3, 4, 5, 5, 4, 4, 3, 5, 4, 3, 4, 3, 3, 5, 4, 2, 5, 3, 4, 5, 4, 4, 4, 4, 5, 4, 5, 5, 5, 3, 4, 4, 5, 3, 5, 3, 3, 2, 3, 3, 3, 3, 3, 4, 5, 5, 3, 4, 3, 3, 3, 2, 3, 4, 4, 4, 4, 4, 5, 4, 5, 4, 5, 5, 5, 4, 4, 5, 5, 5, 5, 5, 5, 4, 5, 2, 4, 4, 2, 3, 5, 4, 3, 2, 3, 4, 4, 3, 4, 4, 3, 4, 3, 4, 3, 4, 4, 3, 3, 3, 3, 4, 3, 3, 4, 4, 3, 4, 3, 4, 5, 5, 4, 4, 4, 5, 4, 3, 3, 4, 3, 4, 4, 2, 3, 2, 2, 4, 2, 2, 2, 3, 2, 5, 5, 5, 4, 3, 4, 3, 3, 2, 4, 5, 1, 4, 4, 3, 5, 4, 2, 3, 3, 3, 2, 2, 4, 5, 3, 4, 5, 4, 4, 5, 4, 5, 4, 4, 5, 4, 3, 3, 4, 5, 3, 3, 4, 3, 3, 3, 1, 4, 4, 4, 3, 5, 5, 3, 4, 4, 4, 4, 4, 4, 3, 2, 2, 3, 5, 5, 3, 4, 2, 5, 4, 5, 5, 3, 5, 4, 3, 1, 5, 4, 5, 3, 2, 3, 4, 2, 4, 3, 4, 4, 4, 3, 5, 2, 5, 5, 5, 4, 5, 3, 5, 4, 4, 3, 4, 3, 4, 5, 3, 5, 5, 1, 4, 4, 5, 4, 2, 2, 4, 3, 4, 1, 4, 4, 3, 5, 2, 3, 4, 1, 5, 5, 4, 4, 4, 5, 1, 4, 4, 4, 3, 3, 4, 2, 3, 4, 4, 5, 3, 2, 4, 5, 4, 4, 4, 4, 5, 4, 2, 4, 3, 4, 4, 5, 4, 2, 3, 5, 4, 4, 5, 4, 4, 5, 4, 4, 4, 3, 4, 4, 3, 3, 3, 3, 4, 2, 3, 5, 4, 5, 5, 3, 5, 5, 5, 5, 4, 5, 4, 2, 4, 4, 3, 5, 4, 2, 4, 4, 2, 4, 3, 5, 3, 5, 4, 5, 5, 4, 5, 3, 5, 1, 2, 5, 3, 3, 4, 4, 4, 4, 5, 2, 4, 3, 4, 2, 3, 4, 5, 4, 5, 3, 4, 2, 2, 3, 4, 2, 4, 4, 4, 3, 5, 4, 3, 3, 4, 4, 3, 4, 4, 4, 3, 3, 4, 3, 4, 4, 2, 4, 5, 4, 5, 5, 5, 4, 5, 3, 5, 4, 5, 5, 4, 3, 3, 3, 2, 3, 2, 5, 5, 5, 4, 5, 5, 4, 5, 3, 3, 5, 3, 5, 4, 1, 4, 5, 5, 4, 3, 4, 4, 3, 4, 2, 2, 4, 5, 2, 4, 4, 3, 4, 4, 4, 1, 3, 4, 5, 3, 3, 3, 3, 1, 2, 3, 1, 1, 3, 1, 2, 5, 3, 5, 3, 3, 4, 4, 5, 4, 3, 4, 3, 3, 4, 3, 3, 4, 4, 3, 3, 4, 3, 3, 5, 3, 4, 4, 5, 1, 5, 4, 4, 4, 5, 5, 5, 4, 5, 5, 4, 5, 3, 1, 4, 3, 5, 5, 3, 4, 5, 5, 3, 3, 3, 4, 1, 3, 4, 2, 3, 4, 3, 5, 5, 4, 2, 3, 4, 3, 3, 3, 5, 3, 3, 3, 5, 2, 4, 2, 5, 4, 4, 3, 4, 4, 4, 3, 3, 3, 4, 5, 3, 3, 3, 4, 3, 3, 1, 1, 5, 5, 5, 5, 4, 3, 3, 4, 4, 3, 4, 5, 3, 5, 4, 4, 4, 4, 4, 5, 2, 2, 2, 4, 1, 2, 4, 2, 4, 4, 4, 3, 5, 4, 4, 4, 4, 4, 4, 5, 4, 5, 1, 4, 4, 3, 5, 5, 4, 4, 3, 3, 1, 4, 1, 4, 5, 4, 4, 4, 5, 2, 5, 5, 3, 5, 2, 2, 5, 4, 5, 3, 4, 5, 3, 4, 3, 4, 5, 3, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 5, 3, 5, 4, 4, 5, 5, 4, 1, 2, 3, 5, 4, 4, 4, 4, 4, 4, 4, 4, 4, 5, 4, 2, 4, 2, 3, 4, 1, 3, 3, 4, 4, 4, 4, 3, 5, 4, 4, 3, 5, 3, 5, 3, 4, 4, 3, 2, 4, 5, 3, 1, 2, 4, 3, 4, 3, 4, 4, 2, 4, 2, 4, 3, 5, 5, 2, 2, 5, 2, 2, 4, 4, 3, 2, 4, 3, 2, 2, 5, 3, 4, 4, 3, 5, 2, 4, 3, 2, 5, 3, 2, 4, 4, 4, 5, 5, 1, 3, 4, 5, 5, 3, 5, 5, 5, 5, 5, 5, 2, 5, 5, 4, 5, 4, 3, 5, 4, 4, 4, 4, 3, 2, 3, 4, 2, 3, 4, 3, 2, 5, 5, 4, 3, 5, 5, 3, 5, 2, 3, 4, 3, 2, 3, 3, 5, 4, 5, 3, 3, 4, 4, 5, 4, 1, 4, 3, 5, 5, 4, 5, 5, 5, 5, 5, 4, 5, 5, 4, 3, 4, 4, 3, 5, 3, 3, 5, 4, 5, 3, 3, 5, 3, 2, 3, 2, 4, 4, 1, 3, 3, 3, 4, 4, 4, 4, 2, 4, 3, 2, 4, 5, 4, 3, 5, 3, 5, 3, 3, 4, 3, 5, 4, 3, 5, 2, 4, 4, 4, 3, 4, 5, 3, 3, 3, 4, 3, 3, 3, 2, 5, 4, 5, 3, 5, 4, 2, 2, 4, 5, 4, 3, 3, 3, 3, 2, 4, 5, 4, 4, 5, 4, 5, 5, 2, 4, 4, 5, 4, 2, 2, 3, 3, 3, 3, 4, 5, 3, 4, 2, 2, 5, 4, 4, 5, 2, 4, 5, 4, 5, 4, 5, 4, 3, 4, 4, 4, 4, 4, 4, 2, 3, 4, 5, 4, 4, 3, 5, 4, 5, 3, 4, 3, 4, 3, 3, 5, 2, 3, 4, 5, 4, 4, 4, 3, 4, 3, 4, 1, 3, 4, 3, 5, 4, 4, 5, 5, 5, 5, 4, 4, 3, 4, 4, 4, 4, 3, 5, 4, 3, 5, 4, 4, 5, 4, 2, 4, 4, 5, 4, 4, 5, 5, 4, 5, 3, 5, 1, 5, 3, 5, 5, 5, 5, 2, 4, 5, 4, 4, 4, 3, 4, 3, 3, 4, 2, 2, 3, 4, 3, 4, 5, 3, 4, 5, 4, 4, 5, 4, 3, 3, 3, 5, 5, 3, 5, 5, 5, 3, 4, 4, 4, 3, 4, 4, 3, 3, 4, 3, 4, 5, 4, 5, 3, 4, 3, 3, 1, 4, 3, 3, 5, 5, 4, 4, 2, 5, 3, 3, 4, 3, 3, 3, 2, 4, 3, 3, 3, 3, 3, 3, 4, 4, 3, 4, 4, 3, 3, 4, 4, 3, 1, 3, 2, 2, 4, 3, 4, 3, 4, 4, 3, 4, 4, 5, 4, 4, 4, 5, 3, 5, 4, 5, 3, 5, 4, 4, 3, 4, 4, 4, 4, 5, 2, 4, 2, 3, 3, 4, 2, 4, 1, 1, 1, 1, 3, 1, 1, 1, 1, 5, 5, 3, 5, 4, 4, 5, 2, 3, 4, 4, 4, 4, 4, 4, 3, 2, 3, 4, 3, 3, 3, 4, 3, 5, 5, 3, 3, 3, 5, 2, 5, 4, 3, 3, 2, 4, 1, 2, 1, 4, 1, 3, 2, 5, 3, 2, 3, 2, 3, 5, 5, 3, 4, 4, 4, 4, 4, 4, 3, 3, 4, 3, 4, 4, 3, 3, 5, 4, 4, 3, 5, 4, 3, 1, 4, 5, 3, 4, 4, 5, 5, 3, 3, 5, 2, 4, 4, 5, 1, 5, 4, 5, 5, 1, 5, 4, 3, 4, 5, 4, 5, 4, 5, 3, 5, 4, 4, 1, 3, 4, 5, 2, 4, 4, 3, 3, 3, 3, 3, 5, 5, 2, 2, 4, 3, 2, 3, 1, 1, 5, 4, 4, 4, 4, 5, 5, 4, 5, 4, 3, 4, 5, 5, 5, 3, 4, 4, 3, 5, 5, 4, 5, 4, 3, 5, 5, 4, 4, 4, 2, 4, 4, 4, 2, 3, 4, 4, 5, 4, 4, 4, 5, 3, 5, 3, 4, 3, 4, 4, 5, 4, 4, 3, 5, 5, 3, 1, 2, 4, 4, 3, 2, 3, 4, 5, 2, 2, 3, 2, 4, 5, 5, 4, 4, 5, 4, 4, 4, 4, 5, 4, 4, 3, 5, 5, 5, 5, 5, 5, 4, 4, 5, 4, 4, 4, 2, 5, 5, 4, 3, 4, 3, 5, 3, 5, 3, 4, 4, 3, 4, 5, 4, 5, 1, 4, 4, 2, 4, 3, 4, 4, 3, 4, 3, 4, 4, 3, 3, 2, 5, 4, 4, 5, 3, 3, 3, 3, 4, 4, 5, 5, 4, 5, 5, 2, 5, 2, 2, 4, 4, 5, 5, 3, 4, 3, 5, 2, 4, 3, 3, 4, 3, 3, 3, 5, 3, 3, 2, 2, 4, 1, 3, 4, 3, 3, 4, 5, 4, 5, 5, 4, 4, 3, 5, 4, 4, 5, 3, 2, 4, 4, 5, 5, 4, 5, 4, 5, 5, 2, 3, 5, 4, 3, 5, 4, 3, 3, 4, 3, 5, 1, 3, 4, 4, 3, 5, 5, 4, 4, 5, 4, 3, 3, 4, 3, 2, 3, 2, 4, 1, 3, 3, 3, 4, 4, 3, 3, 2, 2, 5, 5, 4, 5, 2, 4, 5, 3, 2, 3, 5, 5, 4, 4, 3, 4, 4, 4, 3, 2, 1, 2, 3, 3, 1, 1, 1, 1, 1, 4, 4, 2, 1, 2, 2, 3, 2, 2, 3, 1, 4, 3, 5, 5, 4, 4, 4, 4, 3, 2, 4, 3, 5, 4, 4, 1, 4, 4, 5, 1, 5, 5, 4, 3, 4, 2, 4, 4, 4, 4, 3, 4, 5, 5, 5, 5, 3, 3, 4, 4, 4, 1, 2, 1, 5, 4, 4, 3, 2, 1, 2, 3, 2, 5, 3, 4, 2, 3, 3, 2, 4, 4, 3, 5, 4, 2, 4, 4, 1, 2, 4, 4, 3, 3, 3, 3, 4, 2, 2, 4, 3, 5, 5, 3, 4, 3, 3, 3, 3, 3, 3, 4, 3, 3, 1, 3, 4, 3, 4, 3, 4, 5, 2, 4, 4, 5, 4, 4, 4, 3, 4, 4, 5, 4, 4, 4, 3, 4, 4, 4, 3, 3, 3, 4, 4, 2, 3, 3, 2, 1, 3, 4, 3, 2, 3, 4, 4, 3, 4, 3, 3, 2, 2, 2, 3, 3, 4, 3, 1, 5, 1, 5, 5, 5, 5, 5, 1, 3, 5, 4, 1, 3, 3, 2, 4, 1, 3, 1, 3, 1, 5, 5, 4, 4, 3, 4, 3, 5, 3, 5, 4, 3, 4, 2, 4, 3, 3, 3, 4, 4, 2, 4, 4, 3, 3, 1, 2, 5, 2, 2, 4, 5, 4, 3, 4, 2, 5, 4, 3, 2, 3, 4, 5, 2, 4, 3, 3, 3, 2, 4, 4, 4, 5, 5, 5, 5, 4, 4, 4, 4, 4, 2, 3, 4, 3, 4, 4, 3, 3, 3, 4, 5, 4, 2, 5, 3, 5, 1, 1, 2, 5, 5, 5, 4, 5, 4, 5, 3, 3, 4, 3, 4, 5, 4, 4, 2, 3, 3, 4, 5, 5, 3, 5, 2, 5, 4, 5, 3, 3, 3, 4, 5, 5, 2, 2, 4, 5, 4, 4, 5, 4, 4, 3, 3, 4, 4, 4, 4, 1, 2, 4, 5, 4, 5, 5, 4, 5, 4, 4, 5, 3, 2, 5, 5, 5, 3, 5, 3, 4, 1, 4, 4, 5, 5, 4, 4, 1, 4, 3, 2, 3, 5, 3, 4, 5, 4, 4, 3, 3, 4, 3, 3, 4, 4, 1, 5, 4, 5, 4, 3, 4, 4, 3, 3, 4, 4, 4, 3, 3, 4, 2, 4, 3, 2, 3, 3, 2, 3, 3, 3, 3, 5, 5, 4, 5, 2, 4, 4, 4, 4, 3, 3, 3, 1, 3, 4, 3, 4, 2, 3, 3, 2, 4, 5, 3, 2, 2, 4, 2, 3, 4, 4, 5, 2, 5, 4, 4, 3, 3, 3, 2, 3, 3, 4, 3, 4, 3, 4, 3, 4, 4, 2, 4, 4, 3, 3, 3, 2, 4, 5, 3, 4, 1, 2, 2, 3, 3, 3, 1, 1, 4, 5, 4, 5, 5, 4, 4, 5, 5, 3, 3, 3, 4, 5, 3, 5, 2, 4, 5, 3, 4, 5, 5, 5, 3, 4, 4, 5, 5, 4, 3, 5, 5, 4, 4, 5, 4, 4, 4, 4, 5, 3, 2, 5, 4, 5, 5, 4, 3, 3, 3, 1, 3, 2, 3, 2, 4, 3, 3, 2, 3, 2, 2, 1, 2, 3, 2, 3, 3, 1, 2, 4, 2, 4, 4, 5, 5, 4, 3, 3, 3, 3, 2, 4, 4, 2, 5, 5, 3, 3, 4, 2, 3, 3, 3, 3, 5, 5, 4, 3, 3, 5, 4, 3, 4, 4, 4, 4, 3, 4, 3, 1, 4, 4, 4, 3, 3, 3, 2, 2, 4, 5, 5, 3, 5, 5, 4, 5, 5, 1, 4, 4, 4, 1, 3, 4, 4, 4, 4, 4, 4, 4, 1, 3, 4, 5, 4, 3, 1, 1, 4, 3, 4, 2, 4, 4, 4, 5, 3, 4, 3, 5, 5, 5, 5, 5, 5, 5, 5, 5, 3, 3, 5, 5, 4, 3, 4, 4, 4, 4, 5, 2, 5, 3, 1, 2, 1, 1, 3, 1, 2, 3, 2, 3, 1, 2, 1, 4, 2, 2, 5, 5, 4, 2, 5, 4, 4, 2, 1, 4, 4, 5, 4, 5, 4, 5, 4, 3, 5, 4, 5, 4, 4, 5, 5, 3, 5, 3, 4, 4, 4, 4, 5, 4, 5, 5, 3, 4, 4, 5, 3, 4, 3, 4, 4, 2, 2, 4, 2, 1, 5, 5, 4, 4, 3, 4, 4, 3, 4, 5, 3, 3, 5, 4, 2, 5, 5, 4, 3, 1, 3, 5, 3, 4, 3, 3, 1, 5, 3, 4, 1, 4, 5, 5, 5, 5, 5, 5, 5, 5, 4, 5, 3, 4, 4, 4, 4, 2, 1, 3, 3, 3, 1, 3, 4, 4, 4, 3, 3, 3, 3, 3, 5, 4, 3, 4, 5, 4, 5, 5, 5, 5, 4, 4, 3, 5, 5, 5, 5, 4, 5, 1, 5, 5, 3, 1, 2, 2, 5, 3, 4, 4, 3, 4, 3, 4, 4, 3, 2, 2, 4, 4, 5, 3, 3, 2, 5, 3, 2, 3, 3, 3, 5, 2, 5, 4, 4, 5, 4, 4, 5, 4, 5, 3, 2, 1, 4, 2, 3, 4, 3, 4, 4, 4, 3, 4, 1, 4, 4, 4, 4, 4, 2, 4, 4, 4, 4, 4, 4, 2, 1, 3, 5, 5, 3, 4, 1, 1, 4, 5, 4, 4, 5, 5, 5, 4, 3, 3, 5, 5, 5, 3, 4, 2, 4, 4, 2, 2, 4, 1, 5, 5, 4, 5, 5, 4, 4, 5, 3, 4, 3, 4, 3, 2, 5, 3, 3, 2, 5, 4, 4, 2, 5, 5, 4, 5, 5, 4, 2, 3, 3, 3, 3, 4, 3, 3, 3, 3, 1, 1, 3, 5, 4, 4, 4, 4, 3, 5, 3, 4, 5, 3, 4, 5, 4, 5, 3, 5, 5, 5, 3, 4, 5, 5, 4, 3, 3, 3, 3, 4, 4, 5, 3, 4, 3, 3, 5, 4, 4, 5, 3, 2, 3, 4, 4, 4, 2, 3, 4, 4, 4, 4, 3, 5, 4, 4, 3, 4, 4, 3, 3, 4, 2, 2, 1, 3, 3, 2, 4, 3, 2, 4, 4, 4, 5, 4, 5, 4, 3, 3, 4, 5, 5, 2, 4, 5, 4, 5, 3, 4, 4, 3, 2, 4, 5, 4, 3, 4, 4, 4, 5, 4, 4, 5, 3, 4, 4, 3, 4, 4, 5, 4, 3, 3, 4, 3, 5, 3, 4, 3, 1, 3, 2, 4, 5, 4, 5, 2, 2, 4, 1, 4, 5, 3, 3, 5, 5, 5, 1, 5, 3, 4, 3, 3, 2, 4, 3, 3, 3, 3, 5, 3, 5, 3, 4, 4, 5, 5, 4, 4, 4, 4, 5, 4, 5, 3, 4, 3, 3, 3, 4, 4, 4, 5, 4, 5, 4, 5, 3, 3, 5, 5, 4, 5, 2, 5, 5, 5, 5, 5, 5, 4, 4, 4, 2, 2, 4, 3, 4, 4, 4, 5, 5, 5, 4, 5, 5, 4, 5, 2, 4, 4, 5, 3, 1, 5, 2, 4, 3, 4, 3, 1, 3, 2, 4, 1, 4, 2, 3, 3, 5, 5, 3, 1, 2, 2, 3, 4, 3, 3, 1, 1, 5, 5, 5, 5, 4, 5, 2, 4, 5, 4, 4, 5, 3, 4, 4, 2, 5, 4, 4, 4, 3, 3, 4, 4, 4, 3, 3, 2, 5, 5, 5, 5, 5, 5, 4, 5, 5, 5, 4, 2, 2, 4, 4, 1, 2, 4, 5, 2, 4, 1, 4, 5, 4, 4, 4, 5, 4, 5, 1, 4, 3, 4, 4, 5, 4, 3, 2, 4, 4, 1, 4, 5, 3, 5, 5, 3, 4, 3, 1, 1, 2, 3, 4, 5, 5, 2, 1, 3, 3, 4, 4, 4, 3, 4, 3, 3, 4, 4, 4, 2, 5, 1, 3, 4, 4, 2, 3, 3, 4, 4, 2, 4, 4, 5, 4, 4, 4, 4, 5, 5, 4, 4, 4, 3, 1, 1, 3, 4, 2, 5, 2, 4, 3, 3, 4, 3, 2, 2, 3, 3, 5, 4, 4, 2, 5, 3, 4, 4, 5, 4, 3, 4, 4, 4, 3, 4, 4, 3, 2, 1, 3, 3, 2, 1, 3, 3, 2, 3, 4, 5, 3, 4, 4, 3, 3, 4, 4, 3, 3, 4, 4, 2, 4, 3, 3, 4, 4, 3, 5, 4, 5, 3, 2, 4, 2, 5, 3, 5, 5, 4, 4, 4, 3, 4, 3, 5, 3, 1, 5, 4, 5, 4, 4, 2, 4, 5, 4, 4, 4, 3, 4, 4, 1, 4, 3, 4, 5, 2, 3, 5, 3, 3, 5, 3, 2, 4, 5, 3, 4, 3, 4, 3, 3, 3, 5, 3, 3, 1, 3, 4, 3, 3, 3, 1, 1, 1, 2, 3, 3, 4, 3, 5, 2, 3, 5, 4, 5, 3, 5, 1, 5, 3, 5, 3, 1, 4, 5, 1, 5, 5, 5, 4, 3, 4, 5, 3, 1, 4, 4, 5, 4, 4, 2, 4, 4, 3, 3, 5, 4, 5, 4, 5, 5, 5, 1, 4, 5, 4, 4, 4, 4, 2, 4, 2, 3, 5, 3, 3, 4, 3, 3, 3, 4, 3, 3, 3, 3, 2, 4, 2, 3, 2, 3, 4, 4, 3, 5, 2, 2, 2, 4, 3, 4, 4, 5, 4, 3, 4, 5, 4, 5, 5, 5, 4, 3, 3, 1, 4, 5, 4, 4, 5, 4, 2, 4, 4, 5, 4, 3, 5, 4, 4, 5, 4, 3, 4, 4, 4, 3, 3, 5, 4, 3, 4, 3, 3, 2, 2, 4, 2, 5, 2, 4, 4, 1, 3, 1, 2, 5, 4, 5, 4, 5, 4, 4, 3, 3, 4, 5, 3, 4, 1, 5, 4, 3, 5, 4, 2, 2, 4, 3, 2, 1, 3, 5, 3, 2, 5, 5, 5, 5, 3, 4, 2, 4, 4, 4, 5, 5, 5, 3, 5, 5, 3, 5, 4, 4, 2, 4, 4, 4, 2, 4, 3, 4, 4, 4, 4, 4, 5, 4, 3, 2, 4, 3, 4, 3, 5, 4, 3, 5, 2, 5, 1, 1, 1, 1, 1, 4, 4, 4, 5, 5, 4, 4, 4, 4, 3, 5, 5, 1, 5, 3, 4, 5, 4, 4, 3, 3, 4, 3, 3, 3, 4, 2, 5, 2, 5, 4, 3, 5, 5, 4, 5, 5, 4, 3, 4, 4, 1, 5, 3, 4, 3, 3, 2, 3, 1, 4, 4, 1, 2, 5, 4, 3, 2, 5, 4, 4, 5, 3, 4, 4, 4, 2, 4, 5, 4, 3, 1, 2, 1, 1, 1, 4, 3, 3, 1, 2, 4, 3, 3, 4, 4, 5, 3, 3, 3, 2, 1, 5, 5, 5, 4, 1, 4, 5, 1, 5, 2, 4, 5, 3, 4, 4, 5, 2, 4, 4, 5, 3, 1, 3, 4, 2, 3, 4, 3, 4, 2, 1, 4, 4, 4, 3, 2, 3, 4, 5, 4, 5, 5, 5, 4, 3, 3, 3, 2, 5, 4, 3, 5, 4, 3, 4, 4, 3, 3, 5, 3, 3, 4, 4, 5, 3, 3, 3, 3, 1, 5, 3, 1, 3, 4, 1, 3, 1, 1, 3, 2, 5, 3, 3, 2, 5, 1, 4, 4, 4, 5, 5, 5, 5, 5, 5, 5, 5, 5, 4, 4, 5, 5, 5, 3, 4, 4, 5, 4, 5, 2, 4, 4, 5, 3, 3, 2, 3, 4, 4, 3, 4, 4, 4, 4, 2, 2, 4, 2, 1, 3, 3, 4, 4, 4, 4, 3, 4, 4, 4, 5, 4, 3, 4, 2, 2, 4, 2, 2, 5, 3, 5, 5, 4, 4, 3, 2, 3, 2, 2, 5, 5, 3, 3, 3, 2, 3, 2, 4, 3, 3, 5, 5, 5, 5, 5, 5, 4, 5, 4, 3, 2, 4, 2, 3, 5, 2, 1, 1, 4, 2, 4, 4, 5, 4, 3, 4, 3, 3, 3, 3, 4, 4, 4, 5, 5, 4, 3, 3, 4, 4, 4, 5, 5, 5, 5, 4, 5, 5, 4, 4, 4, 4, 4, 3, 4, 5, 4, 5, 4, 2, 3, 5, 4, 3, 5, 3, 5, 4, 5, 4, 4, 4, 3, 4, 3, 4, 3, 3, 4, 4, 5, 4, 5, 4, 5, 5, 4, 4, 4, 5, 5, 5, 5, 5, 4, 4, 1, 3, 3, 3, 3, 3, 2, 2, 3, 3, 3, 3, 3, 4, 3, 3, 4, 4, 4, 4, 4, 4, 5, 3, 5, 5, 4, 2, 5, 3, 3, 3, 5, 4, 4, 4, 2, 5, 3, 4, 3, 2, 5, 4, 3, 3, 3, 4, 5, 3, 2, 3, 2, 5, 2, 4, 4, 2, 1, 5, 4, 3, 4, 2, 4, 2, 2, 1, 3, 3, 4, 5, 5, 3, 3, 3, 4, 1, 1, 5, 1, 1, 4, 4, 5, 1, 4, 5, 4, 4, 3, 3, 2, 2, 2, 4, 3, 3, 3, 3, 3, 3, 1, 1, 4, 3, 2, 4, 4, 2, 2, 2, 3, 4, 4, 2, 4, 4, 3, 4, 4, 4, 4, 5, 4, 4, 3, 4, 4, 4, 3, 3, 4, 4, 4, 4, 5, 2, 3, 4, 5, 4, 2, 3, 2, 3, 2, 2, 2, 3, 3, 2, 4, 4, 3, 5, 4, 4, 4, 4, 5, 4, 5, 3, 5, 5, 3, 2, 3, 4, 4, 3, 4, 5, 4, 4, 4, 3, 4, 4, 4, 4, 2, 5, 3, 4, 5, 3, 3, 5, 5, 1, 4, 3, 4, 3, 2, 4, 3, 3, 4, 4, 4, 2, 4, 4, 5, 4, 3, 3, 3, 4, 5, 5, 2, 5, 1, 4, 5, 3, 5, 3, 3, 2, 2, 4, 3, 4, 2, 4, 4, 3, 4, 3, 3, 1, 4, 5, 3, 4, 3, 1, 4, 4, 5, 3, 5, 5, 3, 2, 4, 4, 4, 2, 5, 4, 5, 5, 2, 3, 3, 3, 3, 4, 2, 3, 5, 2, 3, 1, 4, 4, 4, 4, 4, 4, 5, 4, 4, 5, 4, 5, 4, 4, 5, 3, 5, 5, 3, 4, 4, 3, 4, 5, 4, 5, 5, 5, 4, 4, 1, 5, 5, 5, 3, 4, 5, 4, 4, 1, 4, 4, 4, 1, 4, 3, 4, 1, 5, 4, 4, 3, 5, 4, 2, 4, 4, 4, 3, 3, 3, 2, 4, 2, 3, 3, 5, 4, 4, 5, 3, 4, 4, 4, 3, 4, 3, 5, 5, 4, 3, 2, 1, 2, 5, 1, 5, 3, 4, 4, 4, 4, 5, 5, 4, 3, 4, 4, 1, 3, 4, 5, 4, 2, 4, 2, 2, 2, 5, 3, 2, 3, 3, 4, 4, 4, 2, 3, 1, 3, 4, 4, 3, 1, 3, 2, 3, 2, 1, 2, 2, 1, 4, 5, 4, 5, 5, 4, 5, 5, 5, 5, 3, 3, 4, 4, 2, 4, 4, 3, 4, 3, 5, 5, 5, 5, 5, 2, 5, 5, 5, 5, 5, 3, 3, 3, 5, 5, 3, 4, 4, 2, 3, 4, 3, 1, 3, 5, 3, 3, 3, 3, 5, 2, 4, 4, 4, 5, 4, 4, 5, 5, 3, 4, 3, 3, 3, 4, 3, 2, 2, 2, 3, 4, 3, 3, 3, 3, 4, 4, 3, 3, 5, 4, 4, 5, 4, 4, 4, 4, 4, 3, 4, 1, 3, 4, 2, 5, 2, 4, 4, 5, 4, 4, 4, 4, 5, 5, 5, 1, 4, 4, 5, 5, 4, 4, 5, 5, 3, 3, 1, 5, 5, 5, 3, 3, 4, 3, 4, 5, 2, 2, 3, 3, 4, 3, 4, 1, 2, 3, 3, 3, 3, 5, 3, 4, 4, 3, 3, 5, 3, 4, 5, 3, 4, 5, 4, 4, 5, 5, 3, 5, 5, 4, 3, 1, 1, 3, 5, 1, 1, 2, 4, 4, 3, 5, 4, 4, 4, 2, 3, 3, 2, 5, 3, 5, 2, 4, 4, 3, 3, 5, 2, 4, 5, 4, 2, 2, 3, 4, 4, 5, 4, 3, 4, 5, 1, 3, 3, 5, 1, 4, 3, 3, 4, 4, 1, 2, 4, 4, 2, 2, 5, 3, 4, 3, 4, 4, 2, 1, 3, 4, 5, 3, 5, 5, 4, 2, 3, 1, 3, 3, 3, 4, 4, 4, 4, 2, 4, 3, 4, 3, 4, 4, 3, 5, 3, 4, 4, 3, 3, 3, 4, 5, 5, 5, 5, 5, 4, 3, 4, 4, 3, 4, 3, 3, 3, 3, 3, 3, 3, 2, 4, 5, 3, 3, 2, 4, 2, 2, 3, 3, 3, 4, 5, 4, 3, 3, 4, 4, 2, 2, 5, 2, 5, 4, 5, 5, 2, 5, 5, 5, 5, 4, 5, 5, 5, 3, 5, 3, 4, 3, 4, 4, 1, 5, 4, 4, 5, 4, 2, 2, 2, 3, 2, 5, 3, 3, 4, 4, 5, 3, 4, 3, 4, 4, 4, 2, 3, 4, 4, 5, 3, 3, 3, 4, 3, 4, 3, 3, 4, 3, 4, 4, 3, 4, 3, 5, 4, 3, 2, 3, 3, 3, 3, 4, 4, 3, 3, 4, 2, 2, 1, 1, 3, 3, 1, 3, 1, 1, 1, 3, 4, 5, 4, 4, 4, 1, 4, 2, 3, 3, 1, 3, 4, 4, 3, 3, 3, 1, 2, 5, 4, 1, 3, 3, 4, 3, 2, 3, 2, 3, 4, 5, 4, 4, 4, 4, 4, 2, 4, 2, 2, 3, 4, 5, 2, 4, 2, 4, 3, 1, 4, 4, 4, 3, 4, 4, 3, 3, 4, 3, 1, 1, 5, 5, 5, 5, 1, 5, 4, 1, 4, 5, 4, 2, 2, 5, 5, 1, 5, 1, 3, 1, 3, 2, 2, 4, 3, 2, 4, 4, 4, 4, 4, 3, 4, 1, 4, 4, 4, 5, 4, 4, 4, 4, 4, 3, 4, 2, 3, 4, 3, 2, 4, 4, 1, 3, 4, 5, 4, 5, 4, 3, 4, 5, 5, 4, 5, 3, 3, 4, 4, 5, 5, 3, 4, 4, 5, 5, 3, 4, 5, 4, 5, 5, 4, 4, 2, 5, 1, 5, 4, 5, 4, 4, 4, 4, 3, 3, 3, 1, 3, 3, 4, 3, 2, 2, 4, 3, 1, 1, 4, 1, 2, 3, 2, 3, 5, 3, 4, 4, 3, 5, 5, 4, 3, 2, 5, 4, 5, 2, 3, 5, 4, 4, 3, 5, 5, 2, 5, 3, 4, 3, 3, 5, 3, 1, 4, 5, 5, 3, 3, 4, 4, 3, 4, 4, 2, 3, 3, 4, 5, 3, 5, 4, 5, 5, 4, 5, 5, 3, 4, 4, 4, 3, 3, 5, 3, 4, 3, 4, 4, 4, 4, 2, 5, 4, 3, 4, 3, 4, 4, 4, 4, 4, 4, 3, 4, 4, 2, 4, 5, 5, 3, 5, 2, 4, 5, 2, 5, 3, 5, 4, 1, 5, 3, 1, 3, 4, 4, 3, 4, 1, 3, 4, 5, 5, 4, 5, 1, 4, 4, 3, 3, 4, 4, 3, 3, 3, 3, 4, 3, 5, 3, 4, 4, 3, 3, 3, 5, 1, 3, 3, 4, 5, 4, 3, 3, 3, 2, 5, 4, 4, 3, 3, 4, 3, 3, 3, 4, 2, 5, 5, 5, 4, 4, 4, 3, 3, 4, 2, 5, 5, 5, 4, 4, 5, 4, 2, 5, 5, 2, 3, 2, 2, 3, 2, 4, 4, 2, 1, 4, 5, 1, 4, 2, 3, 5, 2, 4, 3, 1, 5, 3, 4, 5, 5, 5, 5, 5, 1, 4, 3, 4, 4, 3, 4, 4, 3, 4, 4, 5, 3, 3, 3, 5, 3, 4, 1, 3, 3, 2, 4, 5, 3, 5, 2, 5, 5, 5, 4, 4, 2, 3, 1, 3, 4, 2, 3, 3, 2, 4, 5, 5, 4, 4, 5, 4, 4, 4, 4, 4, 4, 5, 4, 2, 4, 2, 3, 2, 2, 3, 3, 5, 2, 4, 2, 2, 1, 4, 3, 5, 5, 4, 4, 4, 4, 5, 4, 4, 5, 5, 5, 4, 1, 2, 5, 4, 5, 4, 2, 4, 4, 4, 5, 5, 4, 4, 4, 4, 3, 1, 4, 3, 4, 5, 3, 4, 2, 4, 4, 2, 3, 1, 3, 1, 1, 2, 2, 1, 1, 4, 4, 4, 2, 4, 4, 3, 4, 4, 3, 5, 5, 5, 2, 4, 2, 2, 3, 3, 3, 4, 5, 1, 1, 5, 4, 4, 2, 5, 4, 4, 1, 2, 4, 2, 4, 4, 4, 1, 3, 4, 4, 5, 4, 4, 4, 3, 3, 3, 4, 2, 1, 5, 5, 4, 3, 1, 3, 4, 5, 4, 5, 5, 5, 4, 2, 2, 4, 5, 5, 2, 4, 4, 3, 1, 3, 2, 3, 2, 3, 4, 4, 3, 4, 4, 3, 3, 4, 5, 4, 5, 3, 3, 4, 4, 4, 3, 3, 4, 3, 4, 4, 4, 4, 5, 4, 3, 4, 2, 3, 4, 4, 4, 1, 4, 4, 4, 2, 4, 4, 3, 3, 4, 5, 4, 4, 3, 4, 3, 3, 3, 4, 4, 3, 3, 3, 3, 3, 3, 4, 5, 5, 4, 5, 1, 4, 3, 5, 4, 3, 2, 4, 2, 4, 4, 4, 4, 5, 3, 2, 5, 4, 3, 3, 4, 2, 5, 2, 5, 4, 3, 3, 3, 4, 3, 3, 4, 3, 3, 4, 3, 4, 3, 5, 4, 3, 3, 4, 4, 5, 5, 5, 2, 4, 5, 5, 5, 5, 4, 4, 4, 5, 4, 3, 3, 3, 3, 3, 3, 2, 5, 3, 1, 3, 3, 4, 2, 4, 4, 1, 5, 4, 5, 2, 2, 2, 2, 5, 1, 1, 4, 3, 3, 3, 4, 5, 1, 3, 3, 3, 4, 4, 5, 5, 4, 5, 3, 4, 5, 3, 3, 3, 4, 4, 3, 2, 4, 4, 4, 3, 3, 5, 5, 5, 4, 4, 5, 4, 2, 5, 4, 2, 4, 4, 5, 2, 3, 4, 2, 4, 1, 4, 2, 5, 5, 1, 4, 1, 2, 5, 4, 4, 5, 5, 4, 5, 4, 3, 4, 3, 4, 4, 2, 3, 3, 5, 3, 4, 3, 3, 2, 3, 5, 4, 2, 3, 3, 3, 5, 4, 4, 4, 4, 4, 4, 5, 4, 4, 4, 3, 4, 5, 3, 4, 5, 5, 5, 1, 4, 5, 3, 5, 4, 1, 5, 5, 4, 5, 2, 3, 3, 5, 5, 4, 5, 5, 5, 4, 5, 5, 5, 2, 3, 4, 5, 5, 5, 5, 3, 4, 2, 1, 2, 4, 5, 4, 3, 4, 5, 3, 2, 4, 1, 2, 1, 3, 3, 1, 1, 3, 4, 3, 4, 3, 3, 3, 3, 2, 3, 3, 5, 3, 5, 4, 3, 5, 2, 5, 4, 3, 3, 2, 4, 5, 5, 5, 4, 4, 4, 2, 4, 3, 3, 4, 4, 3, 4, 4, 4, 4, 4, 5, 4, 2, 4, 3, 5, 4, 3, 1, 4, 5, 4, 4, 5, 4, 5, 2, 4, 5, 3, 2, 5, 2, 2, 3, 3, 4, 3, 1, 5, 5, 3, 5, 5, 5, 4, 5, 4, 5, 3, 3, 4, 5, 1, 3, 2, 1, 4, 3, 5, 4, 2, 5, 4, 5, 5, 4, 4, 1, 4, 2, 2, 3, 3, 3, 2, 4, 3, 3, 2, 3, 1, 2, 4, 3, 5, 3, 5, 3, 3, 5, 4, 5, 4, 4, 5, 4, 5, 4, 3, 4, 4, 4, 3, 3, 3, 3, 3, 3, 5, 3, 3, 4, 2, 4, 4, 4, 4, 4, 4, 5, 3, 4, 1, 5, 2, 4, 2, 4, 5, 3, 5, 3, 3, 1, 4, 1, 5, 4, 4, 5, 5, 2, 3, 4, 4, 4, 2, 4, 2, 3, 3, 4, 4, 3, 2, 4, 2, 3, 1, 3, 4, 1, 5, 3, 4, 1, 2, 4, 4, 4, 4, 5, 3, 4, 3, 5, 4, 4, 3, 5, 4, 4, 5, 5, 3, 5, 4, 5, 5, 4, 5, 4, 3, 4, 4, 1, 4, 3, 4, 4, 3, 4, 5, 3, 1, 3, 3, 4, 4, 4, 5, 5, 3, 5, 5, 5, 4, 3, 3, 3, 3, 3, 2, 3, 3, 5, 4, 1, 5, 4, 5, 4, 3, 4, 4, 5, 3, 5, 4, 4, 5, 3, 3, 5, 1, 4, 4, 3, 5, 5, 5, 4, 1, 3, 4, 1, 4, 2, 3, 2, 3, 2, 2, 4, 2, 3, 4, 3, 4, 3, 3, 3, 3, 3, 3, 3, 4, 3, 4, 3, 4, 4, 3, 2, 4, 4, 1, 3, 2, 4, 2, 4, 2, 3, 5, 4, 3, 2, 2, 2, 4, 4, 3, 3, 1, 3, 3, 1, 5, 2, 5, 5, 5, 3, 5, 3, 5, 5, 5, 5, 5, 5, 5, 5, 5, 4, 5, 5, 5, 1, 5, 4, 5, 5, 5, 5, 5, 5, 5, 4, 3, 5, 3, 4, 5, 1, 2, 4, 4, 4, 4, 4, 3, 5, 3, 4, 3, 3, 3, 4, 1, 4, 2, 2, 2, 3, 4, 4, 4, 3, 3, 3, 4, 2, 4, 4, 4, 3, 3, 3, 2, 4, 3, 4, 3, 4, 3, 3, 4, 3, 5, 5, 2, 3, 2, 3, 5, 3, 4, 4, 3, 3, 4, 1, 1, 5, 1, 5, 3, 2, 4, 4, 3, 3, 3, 3, 4, 3, 4, 4, 5, 4, 5, 5, 5, 4, 4, 2, 4, 3, 3, 4, 3, 2, 3, 5, 4, 3, 5, 5, 5, 5, 5, 3, 4, 4, 4, 4, 5, 5, 4, 4, 4, 4, 5, 3, 3, 4, 3, 3, 4, 5, 1, 3, 4, 5, 4, 4, 5, 4, 3, 4, 4, 5, 5, 3, 3, 3, 5, 3, 5, 3, 1, 2, 1, 1, 2, 1, 3, 3, 1, 2, 2, 4, 4, 3, 3, 2, 5, 4, 5, 5, 3, 3, 5, 5, 4, 4, 4, 2, 5, 1, 2, 1, 2, 2, 1, 1, 4, 1, 3, 4, 1, 4, 2, 5, 2, 1, 2, 4, 4, 4, 3, 2, 3, 2, 4, 3, 2, 5, 5, 3, 3, 4, 3, 3, 3, 3, 3, 3, 4, 4, 4, 2, 3, 4, 4, 4, 3, 2, 2, 5, 4, 4, 5, 1, 3, 2, 4, 4, 4, 4, 4, 4, 4, 3, 3, 3, 4, 5, 5, 4, 4, 5, 5, 5, 5, 5, 5, 5, 4, 4, 4, 4, 3, 4, 4, 4, 4, 5, 4, 4, 4, 4, 2, 3, 5, 3, 4, 3, 5, 4, 4, 3, 3, 4, 4, 3, 4, 4, 5, 3, 4, 4, 4, 3, 5, 3, 4, 4, 4, 4, 3, 3, 5, 2, 3, 4, 5, 2, 4, 4, 5, 4, 3, 5, 3, 3, 5, 3, 5, 5, 5, 5, 5, 4, 5, 4, 5, 4, 4, 3, 5, 4, 4, 3, 3, 4, 5, 4, 4, 3, 3, 5, 5, 4, 3, 1, 5, 5, 4, 5, 4, 4, 4, 4, 3, 2, 3, 3, 5, 1, 4, 3, 3, 4, 4, 1, 5, 5, 1, 5, 5, 4, 3, 5, 1, 5, 4, 4, 4, 5, 5, 5, 4, 5, 5, 4, 3, 4, 3, 4, 4, 4, 4, 3, 4, 3, 4, 4, 2, 3, 5, 4, 3, 4, 4, 4, 4, 3, 4, 3, 5, 5, 4, 3, 4, 3, 5, 5, 4, 3, 4, 3, 5, 4, 2, 2, 5, 5, 4, 3, 3, 3, 3, 5, 4, 4, 3, 4, 4, 3, 4, 4, 4, 3, 3, 4, 5, 5, 3, 5, 5, 3, 4, 2, 3, 3, 2, 3, 5, 2, 2, 4, 1, 5, 1, 2, 5, 5, 5, 5, 3, 4, 5, 3, 5, 5, 4, 4, 2, 4, 2, 5, 4, 3, 4, 3, 5, 3, 5, 5, 1, 4, 4, 3, 5, 4, 2, 1, 3, 3, 2, 2, 2, 4, 2, 5, 3, 5, 4, 3, 3, 4, 4, 4, 4, 3, 5, 3, 4, 3, 2, 5, 3, 3, 5, 3, 5, 5, 4, 3, 5, 4, 4, 2, 3, 3, 4, 4, 4, 5, 2, 5, 3, 3, 4, 3, 4, 4, 3, 3, 3, 4, 4, 3, 3, 1, 3, 4, 4, 4, 3, 4, 3, 5, 4, 4, 5, 4, 5, 2, 5, 2, 5, 5, 5, 3, 3, 4, 5, 3, 3, 2, 4, 3, 4, 4, 5, 5, 4, 4, 5, 5, 4, 5, 3, 5, 4, 4, 4, 4, 4, 2, 3, 4, 4, 4, 2, 4, 4, 5, 4, 5, 5, 3, 3, 4, 5, 5, 4, 3, 2, 4, 5, 5, 4, 4, 2, 4, 5, 4, 4, 1, 1, 5, 5, 1, 2, 1, 5, 4, 4, 3, 2, 3, 3, 1, 5, 3, 2, 3, 3, 3, 4, 2, 3, 2, 5, 3, 3, 3, 3, 3, 3, 3, 2, 3, 4, 3, 5, 5, 3, 4, 4, 4, 5, 2, 3, 5, 1, 3, 5, 3, 3, 4, 4, 4, 4, 3, 3, 4, 4, 3, 3, 3, 3, 5, 3, 3, 2, 3, 3, 4, 4, 4, 3, 4, 3, 3, 3, 4, 2, 5, 4, 3, 1, 2, 4, 5, 4, 3, 3, 3, 3, 4, 2, 3, 4, 5, 4, 5, 3, 4, 4, 4, 3, 4, 4, 4, 2, 3, 5, 5, 3, 5, 2, 4, 4, 3, 4, 4, 3, 4, 4, 3, 4, 2, 4, 4, 3, 3, 3, 3, 4, 2, 1, 4, 3, 5, 3, 4, 5, 5, 5, 5, 2, 4, 5, 5, 5, 3, 5, 5, 5, 5, 5, 5, 3, 2, 5, 4, 4, 3, 4, 4, 5, 5, 3, 4, 1, 2, 3, 4, 1, 1, 3, 3, 3, 2, 3, 4, 4, 3, 3, 3, 3, 4, 4, 3, 2, 5, 5, 4, 4, 4, 5, 5, 4, 5, 5, 4, 4, 4, 2, 4, 1, 3, 4, 5, 3, 3, 5, 5, 5, 3, 2, 1, 3, 4, 4, 2, 4, 4, 4, 4, 5, 4, 3, 4, 5, 4, 4, 4, 4, 4, 4, 2, 5, 4, 4, 3, 1, 4, 4, 4, 4, 5, 1, 3, 2, 5, 4, 1, 4, 4, 3, 2, 3, 5, 4, 4, 5, 5, 2, 4, 4, 5, 3, 4, 3, 3, 4, 3, 4, 3, 4, 3, 4, 4, 5, 5, 4, 5, 4, 4, 4, 4, 4, 4, 4, 3, 5, 5, 4, 4, 4, 3, 4, 4, 4, 5, 5, 4, 4, 1, 4, 2]
In [106]:
scatter(
    array(data['test'].tocsr()[userids, movieids].tolist()[0]) + randn(9430) * 0.1,
    model.predict(array(userids), array(movieids)),
    alpha=0.2
);
In [47]:
Counter((data['test'] * 10 + data['train']).toarray().ravel())
Out[47]:
Counter({0.0: 1486126,
         1.0: 5568,
         2.0: 10375,
         3.0: 24721,
         4.0: 30858,
         5.0: 19048,
         10.0: 542,
         20.0: 995,
         30.0: 2424,
         40.0: 3316,
         50.0: 2153})
In [31]:
test_precision
Out[31]:
0.12576883
In [32]:
data
Out[32]:
{'item_feature_labels': array([u'Toy Story (1995)', u'GoldenEye (1995)', u'Four Rooms (1995)', ...,
        u'Sliding Doors (1998)', u'You So Crazy (1994)',
        u'Scream of Stone (Schrei aus Stein) (1991)'], dtype=object),
 'item_features': <1682x1682 sparse matrix of type '<type 'numpy.float32'>'
 	with 1682 stored elements in Compressed Sparse Row format>,
 'item_labels': array([u'Toy Story (1995)', u'GoldenEye (1995)', u'Four Rooms (1995)', ...,
        u'Sliding Doors (1998)', u'You So Crazy (1994)',
        u'Scream of Stone (Schrei aus Stein) (1991)'], dtype=object),
 'test': <943x1682 sparse matrix of type '<type 'numpy.int32'>'
 	with 9430 stored elements in COOrdinate format>,
 'train': <943x1682 sparse matrix of type '<type 'numpy.float32'>'
 	with 90570 stored elements in COOrdinate format>}
data['item_feature_labels'] == data['item_labels'] data['item_features'][i,j] = i == j
In [65]:
figure(figsize=(16,6))
subplot(121)
imshow(data['train'].toarray());
subplot(122)
imshow(data['test'].toarray());
colorbar();
In [16]:
len(data['item_labels'])
Out[16]:
1682
In [36]:
Counter(data['item_features'].toarray().ravel())
Out[36]:
Counter({0.0: 2827442, 1.0: 1682})
In [37]:
Counter(data['test'].toarray().ravel())
Out[37]:
Counter({0: 1576696, 1: 542, 2: 995, 3: 2424, 4: 3316, 5: 2153})
In [38]:
Counter(data['train'].toarray().ravel())
Out[38]:
Counter({0.0: 1495556,
         1.0: 5568,
         2.0: 10375,
         3.0: 24721,
         4.0: 30858,
         5.0: 19048})

Регрессия

todo

  • Качество регрессии: mean_absolute_error, mean_squared_error, r2_score

Временные ряды

todo

  • scikit-timeseries

  • metrics.pairwise (linear_kernel, polynomial_kernel, rbf_kernel)

Калибровка

todo

  • calibration (CalibratedClassifierCV)

Кластеризация

Задача кластеризации возникает, когда классы объектов неизвестны (unsupervised learning), но телепатия говорит нам, что есть несколько сильно отличающихся по свойствам групп объектов. Для ее решения существует много методов, но наиболее популярны K-Means (тупой и прямолинейный) и DBSCAN (хитрый и долгий).

В качестве датасета используем избитый набор про морфологию трех видов ирисов.

In [103]:
dataset = sklearn.datasets.load_iris()
In [104]:
dataset['feature_names']
Out[104]:
['sepal length (cm)',
 'sepal width (cm)',
 'petal length (cm)',
 'petal width (cm)']
In [105]:
dataset.keys()
Out[105]:
['target_names', 'data', 'target', 'DESCR', 'feature_names']
In [107]:
X = dataset['data']
In [120]:
scatter(X[:,2], X[:,3], c=dataset['target']);
In [121]:
import sklearn.cluster

K-Means случайно выбирает центры n_clusters кластеров, а затем итеративно уточняет их положения, то относя точки к ближайшему центру, то смещая центр в их центр тяжести.

In [143]:
kmeans = sklearn.cluster.KMeans(n_clusters=5, random_state=0)
components = kmeans.fit_predict(X)
kmeans.cluster_centers_
Out[143]:
array([[ 5.006     ,  3.418     ,  1.464     ,  0.244     ],
       [ 6.52916667,  3.05833333,  5.50833333,  2.1625    ],
       [ 5.53214286,  2.63571429,  3.96071429,  1.22857143],
       [ 7.475     ,  3.125     ,  6.3       ,  2.05      ],
       [ 6.24722222,  2.84722222,  4.775     ,  1.575     ]])
In [144]:
figure(figsize=(16,5))
subplot(121)
scatter(X[:,2], X[:,3], c=dataset['target']);
scatter(kmeans.cluster_centers_[:,2], kmeans.cluster_centers_[:,3], marker='^', c='r', s=100);

subplot(122)
scatter(X[:,2], X[:,3], c=components);

K-Means примерно равномерно расположил центры кластеров по облаку точек, и за счет удачного выбора числа кластеров их номера примерно соответствуют реальным классам (показаны цветом на скаттере слева).

In [147]:
dbscan = sklearn.cluster.DBSCAN()
components = dbscan.fit_predict(X)
In [149]:
figure(figsize=(16,5))
subplot(121)
scatter(X[:,2], X[:,3], c=components);

subplot(122)
scatter(X[:,0], X[:,1], c=components);

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

Качество кластеризации

Качество кластеризации можно оценивать, имея на руках настоящие метки классов или не имея.

https://github.com/scikit-learn/scikit-learn/blob/master/sklearn/metrics/cluster/supervised.py

In [155]:
Y_true = [0,0,0,0,0, 0,1,1,1,1]
Y_pred = [1,1,1,2,2, 2,3,3,3,3]
In [156]:
sklearn.metrics.homogeneity_score(Y_true, Y_pred)
Out[156]:
1.0
In [157]:
sklearn.metrics.completeness_score(Y_true, Y_pred)
Out[157]:
0.61806564629215444

todo Понять, как считалось

Их среднее гармоническое — v_measure_score.

In [158]:
sklearn.metrics.v_measure_score(Y_true, Y_pred)
Out[158]:
0.76395620623733063

todo adjusted_rand_score? Ward metric?

Снижение размерности

todo

  • decomposition (PCA, RandomizedPCA, TruncatedSVD, FastICA, NMF, LatentDirichletAllocation)
  • manifold (Isomap, MDS, LocallyLinearEmbedding, TSNE)
  • discriminant_analysis.LinearDiscriminantAnalysis
  • discriminant_analysis.QuadraticDiscriminantAnalysis
  • сети Кохонена

Поиск аномалий

todo

  • IsolationForest
  • OneClassSVM

Пайплайн

todo

  • from skdata.base import SklearnClassifier
  • base (BaseEstimator, ClassifierMixin, TransformerMixin)
  • pipeline (FeatureUnion, Pipeline)

Подбор гиперпараметров

todo

  • feature_selection (RFECV)
  • grid_search (GridSearchCV, RandomizedSearchCV)
  • hyperopt
pip install git+git://github.com/hyperopt/hyperopt.git

hyperopt (0.0.3.dev0)

from hpsklearn import any_classifier, components
import hpsklearn.demo_support
from hpsklearn.components import svc, pca
from hpsklearn.estimator import HyperoptEstimatorFactory, hyperopt_estimator

from hyperopt import anneal, base, criteria, fmin, plotting, rand, tpe, hp, Trials, Domain, exceptions, space_eval, STATUS_FAIL, STATUS_OK

Обработка естественного языка (NLP)

todo

https://habr.com/company/mailru/blog/358736/

nltk, bigARTM, gensim, artm
    import nltk.classify.util
    from nltk import bigrams, trigrams
    from nltk.classify import NaiveBayesClassifier
    from nltk.collocations import BigramCollocationFinder
    from nltk.corpus import brown, conll2000, movie_reviews, names, stopwords
    from nltk.metrics.scores import precision, recall
    from nltk.probability import FreqDist, KneserNeyProbDist
    from nltk.stem.porter import PorterStemmer
    from nltk.tokenize import word_tokenize

    pip install gensim

    from gensim import corpora, models, similarities
    from gensim.corpora import WikiCorpus
    from gensim.models.word2vec import Word2Vec

    pymorphy2 Morphological analyzer (POS tagger + inflection engine) for Russian language
In [5]:
import inflect
engine = inflect.engine()
print engine.plural('ass')
print engine.number_to_words(11345)
asses
eleven thousand, three hundred and forty-five

Делает запросы к api.wordnik.com

In [14]:
from vocabulary.vocabulary import Vocabulary
import json
In [41]:
Vocabulary.synonym('fire', format='list')
Out[41]:
[u'hit',
 u'dismiss',
 u'give forth',
 u'sack',
 u'break wind',
 u'lay off',
 u'discharge',
 u'emit']
In [31]:
from nltk.corpus import wordnet
In [39]:
for syn in wordnet.synsets('fire'):
    print syn.name(), ':',
    for lemma in syn.lemmas():
        print lemma.name(),
    print
fire.n.01 : fire
fire.n.02 : fire firing
fire.n.03 : fire flame flaming
fire.n.04 : fire
fire.n.05 : fire
ardor.n.03 : ardor ardour fervor fervour fervency fire fervidness
fire.n.07 : fire
fire.n.08 : fire
fire.n.09 : fire attack flak flack blast
open_fire.v.01 : open_fire fire
fire.v.02 : fire discharge
fire.v.03 : fire
displace.v.03 : displace fire give_notice can dismiss give_the_axe send_away sack force_out give_the_sack terminate
fire.v.05 : fire discharge go_off
fire.v.06 : fire
arouse.v.01 : arouse elicit enkindle kindle evoke fire raise provoke
burn.v.01 : burn fire burn_down
fuel.v.02 : fuel fire
In [42]:
Vocabulary.antonym('fire', format='list')
Out[42]:
[u'hire']
In [43]:
Vocabulary.hyphenation('innocence', format='list')
Out[43]:
[[u'in', u'stress'], u'no', u'cence']
In [48]:
Vocabulary.pronunciation('acceptance', format='dict')
Out[48]:
{0: {u'raw': u'(\u0103k-s\u0115p\u02c8t\u0259ns)', u'rawType': u'ahd-legacy'},
 1: {u'raw': u'AE0 K S EH1 P T AH0 N S', u'rawType': u'arpabet'},
 2: {u'raw': u'AH0 K S EH1 P T AH0 N S', u'rawType': u'arpabet'}}
In [50]:
print Vocabulary.pronunciation('acceptance', format='dict')[0]['raw']
(ăk-sĕpˈtəns)
In [51]:
Vocabulary.meaning('lasagne', format='list')
Out[51]:
[u'very wide flat strips of pasta',
 u'baked dish of layers of lasagna pasta with sauce and cheese and meat or vegetables',
 u'Variant of lasagna',
 u'<i>Synonym of [i]lasagna</i>[/i]',
 u'<i>plural of [i]lasagna</i>[/i]']
In [57]:
Vocabulary.part_of_speech('according', format='dict')
Out[57]:
{0: {'example': u'Present participle of accord.', 'text': u'verb'},
 1: {'example': u'Agreeing; in agreement or harmony; harmonious.',
  'text': u'adjective'}}
In [56]:
for res in Vocabulary.translate('unbelievable', 'en', 'ru', format='list'):
    print res
невероятный
неправдоподобный
неимоверный
невероятно
pip install pymorphy2
In [8]:
import pymorphy2

morph = pymorphy2.MorphAnalyzer()
for p in morph.parse(u'защищающихся'):
    print p
    print p.normal_form
Parse(word=u'\u0437\u0430\u0449\u0438\u0449\u0430\u044e\u0449\u0438\u0445\u0441\u044f', tag=OpencorporaTag('PRTF,impf,intr,pres,actv plur,gent'), normal_form=u'\u0437\u0430\u0449\u0438\u0449\u0430\u0442\u044c\u0441\u044f', score=0.3333333333333333, methods_stack=((<DictionaryAnalyzer>, u'\u0437\u0430\u0449\u0438\u0449\u0430\u044e\u0449\u0438\u0445\u0441\u044f', 224, 34),))
защищаться
Parse(word=u'\u0437\u0430\u0449\u0438\u0449\u0430\u044e\u0449\u0438\u0445\u0441\u044f', tag=OpencorporaTag('PRTF,impf,intr,pres,actv anim,plur,accs'), normal_form=u'\u0437\u0430\u0449\u0438\u0449\u0430\u0442\u044c\u0441\u044f', score=0.3333333333333333, methods_stack=((<DictionaryAnalyzer>, u'\u0437\u0430\u0449\u0438\u0449\u0430\u044e\u0449\u0438\u0445\u0441\u044f', 224, 36),))
защищаться
Parse(word=u'\u0437\u0430\u0449\u0438\u0449\u0430\u044e\u0449\u0438\u0445\u0441\u044f', tag=OpencorporaTag('PRTF,impf,intr,pres,actv plur,loct'), normal_form=u'\u0437\u0430\u0449\u0438\u0449\u0430\u0442\u044c\u0441\u044f', score=0.3333333333333333, methods_stack=((<DictionaryAnalyzer>, u'\u0437\u0430\u0449\u0438\u0449\u0430\u044e\u0449\u0438\u0445\u0441\u044f', 224, 39),))
защищаться

todo POS-tagging

In [ ]:
p.tag.POS == 'NOUN'
In [17]:
text = u'''
Явились даже опасные мечтатели. Руководимые не столько разумом, сколько движениями
благодарного сердца, они утверждали, что при новом градоначальнике процветет торговля,
и что, под наблюдением квартальных надзирателей, возникнут науки и искусства.
Не удержались и от сравнений. Вспомнили только что выехавшего из города старого градоначальника,
и находили, что хотя он тоже был красавчик и умница, но что, за всем тем, новому правителю
уже по тому одному должно быть отдано преимущество, что он новый. Одним словом, при этом случае,
как и при других подобных, вполне выразились: и обычная глуповская восторженность,
и обычное глуповское легкомыслие.'''
for w in text.split():
    print '|'.join(set(pymorphy2.MorphAnalyzer().normal_forms(w))),
явиться даже опасный мечтатели. руководимый не столько разумом, сколько движение благодарный|благодарное сердца, они утверждали, что пря|при|переть новый|новое градоначальник процвести торговля, и|исполняющий что, под наблюдение квартальный надзирателей, возникнуть наука и|исполняющий искусства. не удержаться и|исполняющий от сравнений. вспомнить только что выехать из|иза город старое|старый градоначальника, и|исполняющий находили, что хотя|хотеть он тоже быть красавчик и|исполняющий умница, но что, за весь тем, новый|новое правитель уже|узкий|уж по тома|тот|том один должно|должный быть отдать преимущество, что он новый. один словом, пря|при|переть это|этот случае, как и|исполняющий пря|при|переть другой подобных, вполне выразились: и|исполняющий обычный глуповский восторженность, и|исполняющий обычный глуповское|глуповский легкомыслие.

Перевод

Враппером над онлайн-сервисом перевода может послужить библиотека yandex-translater. Для ее использования нужно получить бесплатный ключ по адресу https://translate.yandex.com/developers/keys . Перевод ограничен 1кк символами в день и 10кк в месяц.

todo Еще есть https://github.com/matheuss/google-translate-api/blob/master/index.js

pip install yandex-translater
In [5]:
import os, locale
from ultra import file_get
locale.setlocale(locale.LC_ALL, '')
os.environ['HTTPS_PROXY'] = 'socks5h://127.0.0.1:9050'
In [1]:
text = '''
— А что, отец, — спросил молодой человек, затянувшись, — невесты у вас в городе есть? Старик дворник ничуть не удивился.
— Кому и кобыла невеста, — ответил он, охотно ввязываясь в разговор.
— Больше вопросов не имею, — быстро проговорил молодой человек.
'''
In [6]:
from yandex import Translater
tr = Translater(
    key=file_get('yandex-translater-key.txt'),
    text=text,
    from_lang='ru', to_lang='en')
print tr.translate()
— And what, father, ' asked the young man, inhaled, bride in your city have? The old man janitor I was not surprised.
— To whom and Mare bride, he answered, willingly engaging in conversation.
— I have no more questions, young man said.

Нейронные сети

Если данные для машинного обучения имеют ярко выраженную пространственную зависимость между соседними элементами, как, например, пиксели в изображении, интенсивности звука в аудио или буквы в тексте, хорошие результаты могут показать нейронные сети. Поскольку задачи с такими данными достаточно хорошо (но дорого) решаются и людьми, а еще потому, что вычисления для тренировки этого алгоритма машинного обучения хорошо и быстро проводятся на современных GPU, область переживает свой расцвет (2017).

GPGPU и CUDA

На видеокартах от nVidia произвольные вычисления (General-purpose computing on GPU) возможны с использованием библиотеки и тулсета CUDA. Для ее использования установите https://developer.nvidia.com/cuda-downloads?target_os=Windows&target_arch=x86_64&target_version=7&target_type=exelocal (1.5 ГБ).

Затем следует воспользоваться библиотекой-враппером pycuda. Документация https://documen.tician.de/pycuda/ . Она позволяет немного удобнее писать на C++ (на самом деле сильно урезанном диалекте CUDA C, который компилируется программой nvcc из библиотеки CUDA) вычислительные ядра.

Архитектура GPU включает в себя иерархию вычислительных блоков и доступных им блоков памяти; она заточена под быстрое умножение матриц, но даже это делать на ней очень неудобно и требует заката байтиков по вычислительным блокам вручную.

Примеры https://docs.nvidia.com/cuda/cuda-samples/index.html

В консоли VC++2008 for Python:
pip install pycuda --global-option build_ext --global-option --compiler=msvc
In [1]:
import pycuda.driver
import pycuda.compiler

import numpy

pycuda.driver.init()

ndevices = pycuda.driver.Device.count()
print ndevices, 'устройств доступно'
for i in range(ndevices):
    dev = pycuda.driver.Device(i)
    print i, ':', dev.name()
    print '\tcompute capability version:', dev.compute_capability()
    print '\ttotal memory:', dev.total_memory()
    print '\tattributes:', dev.get_attributes()
1 устройств доступно
0 : GeForce GTX 1060
	compute capability version: (6, 1)
	total memory: 6442450944
	attributes: {pycuda._driver.device_attribute.MAX_THREADS_PER_BLOCK: 1024, pycuda._driver.device_attribute.MAX_BLOCK_DIM_X: 1024, pycuda._driver.device_attribute.MAX_BLOCK_DIM_Y: 1024, pycuda._driver.device_attribute.MAX_BLOCK_DIM_Z: 64, pycuda._driver.device_attribute.MAX_GRID_DIM_X: 2147483647, pycuda._driver.device_attribute.MAX_GRID_DIM_Y: 65535, pycuda._driver.device_attribute.MAX_GRID_DIM_Z: 65535, pycuda._driver.device_attribute.MAX_SHARED_MEMORY_PER_BLOCK: 49152, pycuda._driver.device_attribute.TOTAL_CONSTANT_MEMORY: 65536, pycuda._driver.device_attribute.WARP_SIZE: 32, pycuda._driver.device_attribute.MAX_PITCH: 2147483647, pycuda._driver.device_attribute.MAX_REGISTERS_PER_BLOCK: 65536, pycuda._driver.device_attribute.CLOCK_RATE: 1670500, pycuda._driver.device_attribute.TEXTURE_ALIGNMENT: 512, pycuda._driver.device_attribute.GPU_OVERLAP: 1, pycuda._driver.device_attribute.MULTIPROCESSOR_COUNT: 10, pycuda._driver.device_attribute.KERNEL_EXEC_TIMEOUT: 1, pycuda._driver.device_attribute.INTEGRATED: 0, pycuda._driver.device_attribute.CAN_MAP_HOST_MEMORY: 1, pycuda._driver.device_attribute.COMPUTE_MODE: pycuda._driver.compute_mode.DEFAULT, pycuda._driver.device_attribute.MAXIMUM_TEXTURE1D_WIDTH: 131072, pycuda._driver.device_attribute.MAXIMUM_TEXTURE2D_WIDTH: 131072, pycuda._driver.device_attribute.MAXIMUM_TEXTURE2D_HEIGHT: 65536, pycuda._driver.device_attribute.MAXIMUM_TEXTURE3D_WIDTH: 16384, pycuda._driver.device_attribute.MAXIMUM_TEXTURE3D_HEIGHT: 16384, pycuda._driver.device_attribute.MAXIMUM_TEXTURE3D_DEPTH: 16384, pycuda._driver.device_attribute.MAXIMUM_TEXTURE2D_ARRAY_WIDTH: 32768, pycuda._driver.device_attribute.MAXIMUM_TEXTURE2D_ARRAY_HEIGHT: 32768, pycuda._driver.device_attribute.MAXIMUM_TEXTURE2D_ARRAY_NUMSLICES: 2048, pycuda._driver.device_attribute.SURFACE_ALIGNMENT: 512, pycuda._driver.device_attribute.CONCURRENT_KERNELS: 1, pycuda._driver.device_attribute.ECC_ENABLED: 0, pycuda._driver.device_attribute.PCI_BUS_ID: 1, pycuda._driver.device_attribute.PCI_DEVICE_ID: 0, pycuda._driver.device_attribute.TCC_DRIVER: 0, pycuda._driver.device_attribute.MEMORY_CLOCK_RATE: 4004000, pycuda._driver.device_attribute.GLOBAL_MEMORY_BUS_WIDTH: 192, pycuda._driver.device_attribute.L2_CACHE_SIZE: 1572864, pycuda._driver.device_attribute.MAX_THREADS_PER_MULTIPROCESSOR: 2048, pycuda._driver.device_attribute.ASYNC_ENGINE_COUNT: 2, pycuda._driver.device_attribute.UNIFIED_ADDRESSING: 1, pycuda._driver.device_attribute.MAXIMUM_TEXTURE1D_LAYERED_WIDTH: 32768, pycuda._driver.device_attribute.MAXIMUM_TEXTURE1D_LAYERED_LAYERS: 2048, pycuda._driver.device_attribute.MAXIMUM_TEXTURE2D_GATHER_WIDTH: 32768, pycuda._driver.device_attribute.MAXIMUM_TEXTURE2D_GATHER_HEIGHT: 32768, pycuda._driver.device_attribute.MAXIMUM_TEXTURE3D_WIDTH_ALTERNATE: 8192, pycuda._driver.device_attribute.MAXIMUM_TEXTURE3D_HEIGHT_ALTERNATE: 8192, pycuda._driver.device_attribute.MAXIMUM_TEXTURE3D_DEPTH_ALTERNATE: 32768, pycuda._driver.device_attribute.PCI_DOMAIN_ID: 0, pycuda._driver.device_attribute.TEXTURE_PITCH_ALIGNMENT: 32, pycuda._driver.device_attribute.MAXIMUM_TEXTURECUBEMAP_WIDTH: 32768, pycuda._driver.device_attribute.MAXIMUM_TEXTURECUBEMAP_LAYERED_WIDTH: 32768, pycuda._driver.device_attribute.MAXIMUM_TEXTURECUBEMAP_LAYERED_LAYERS: 2046, pycuda._driver.device_attribute.MAXIMUM_SURFACE1D_WIDTH: 32768, pycuda._driver.device_attribute.MAXIMUM_SURFACE2D_WIDTH: 131072, pycuda._driver.device_attribute.MAXIMUM_SURFACE2D_HEIGHT: 65536, pycuda._driver.device_attribute.MAXIMUM_SURFACE3D_WIDTH: 16384, pycuda._driver.device_attribute.MAXIMUM_SURFACE3D_HEIGHT: 16384, pycuda._driver.device_attribute.MAXIMUM_SURFACE3D_DEPTH: 16384, pycuda._driver.device_attribute.MAXIMUM_SURFACE1D_LAYERED_WIDTH: 32768, pycuda._driver.device_attribute.MAXIMUM_SURFACE1D_LAYERED_LAYERS: 2048, pycuda._driver.device_attribute.MAXIMUM_SURFACE2D_LAYERED_WIDTH: 32768, pycuda._driver.device_attribute.MAXIMUM_SURFACE2D_LAYERED_HEIGHT: 32768, pycuda._driver.device_attribute.MAXIMUM_SURFACE2D_LAYERED_LAYERS: 2048, pycuda._driver.device_attribute.MAXIMUM_SURFACECUBEMAP_WIDTH: 32768, pycuda._driver.device_attribute.MAXIMUM_SURFACECUBEMAP_LAYERED_WIDTH: 32768, pycuda._driver.device_attribute.MAXIMUM_SURFACECUBEMAP_LAYERED_LAYERS: 2046, pycuda._driver.device_attribute.MAXIMUM_TEXTURE1D_LINEAR_WIDTH: 134217728, pycuda._driver.device_attribute.MAXIMUM_TEXTURE2D_LINEAR_WIDTH: 131072, pycuda._driver.device_attribute.MAXIMUM_TEXTURE2D_LINEAR_HEIGHT: 65000, pycuda._driver.device_attribute.MAXIMUM_TEXTURE2D_LINEAR_PITCH: 2097120, pycuda._driver.device_attribute.MAXIMUM_TEXTURE2D_MIPMAPPED_WIDTH: 32768, pycuda._driver.device_attribute.MAXIMUM_TEXTURE2D_MIPMAPPED_HEIGHT: 32768, pycuda._driver.device_attribute.COMPUTE_CAPABILITY_MAJOR: 6, pycuda._driver.device_attribute.COMPUTE_CAPABILITY_MINOR: 1, pycuda._driver.device_attribute.MAXIMUM_TEXTURE1D_MIPMAPPED_WIDTH: 16384, pycuda._driver.device_attribute.STREAM_PRIORITIES_SUPPORTED: 1, pycuda._driver.device_attribute.GLOBAL_L1_CACHE_SUPPORTED: 1, pycuda._driver.device_attribute.LOCAL_L1_CACHE_SUPPORTED: 1, pycuda._driver.device_attribute.MAX_SHARED_MEMORY_PER_MULTIPROCESSOR: 98304, pycuda._driver.device_attribute.MAX_REGISTERS_PER_MULTIPROCESSOR: 65536, pycuda._driver.device_attribute.MANAGED_MEMORY: 1, pycuda._driver.device_attribute.MULTI_GPU_BOARD: 0, pycuda._driver.device_attribute.MULTI_GPU_BOARD_GROUP_ID: 0}

Shader Processors : Texture mapping units : Render output units = 1280:80:48

In [2]:
def get_cuda_cores_count(dev):
    mpc = dev.get_attribute(pycuda.driver.device_attribute.MULTIPROCESSOR_COUNT)
    major, minor = dev.compute_capability()
    if major == 2: # Fermi
        return mpc * 48 if minor == 1 else mpc * 32
    if major == 3: # Kepler
        return mpc * 192
    if major == 5: # Maxwell
        return mpc * 128
    if major == 6: # Pascal
        if minor == 1:
            return mpc * 128
        elif minor == 0:
            return mpc * 64
In [3]:
get_cuda_cores_count(dev)
Out[3]:
1280
In [7]:
dev = pycuda.driver.Device(0)
ctx = dev.make_context()
In [59]:
mod = pycuda.compiler.SourceModule("""
__global__ void brute_md5(char *out)
{
  const int tid = blockIdx.x * blockDim.x + threadIdx.x;
  if (tid % 2 == 0) {
      out[tid] = tid;
  }
}
""")
C:\Users\User\Anaconda2\lib\site-packages\ipykernel\__main__.py:9: UserWarning: The CUDA compiler succeeded, but said the following:
kernel.cu

In [33]:
mod = pycuda.compiler.SourceModule(
"""
#define UINT4 uint
#define uint unsigned int
//#include <stdio.h>
//#include <cuda.h>
""" +
md5_code + 
"""
__device__ unsigned long long int finished = 0;

__constant__ char hex[] = "0123456789abcdef";

__device__ void print_int(char *out, int val, int len)
{
    for (int i = 0; i < len; ++i) {
        out[len - 1 - i] = '0' + val % 10;
        val /= 10;
    }
}

__global__ void brute_md5(char *out)
{
    int tid = 0;
        blockIdx.x * gridDim.y * gridDim.z * blockDim.x +
        blockIdx.y * gridDim.z * blockDim.x +
        blockIdx.z * blockDim.x +
        threadIdx.x;
    int val = tid;

    char buff[64] = {0};
    int len = 10;
    print_int(buff, val, len);
    buff[len] = 0x80;
    buff[56] = len * 8;
    
    union {
        uint outi[4];
        char bytes[16];
    } hash;
    md5((uint *) &buff[0], hash.outi);

    int foo = 42;

    char outhex[32];
    for (int i = 0; i < 16; ++i) {
        outhex[2 * i + 0] = hash.bytes[i] / 16;
        outhex[2 * i + 1] = hash.bytes[i] % 0xF;
    }
    
    int digits = 0, es = 0;
    for (int i = 0; i < 32; ++i) {
        digits += outhex[i] <= 9;
        es += outhex[i] == 14;
    }

    if (1 || digits + es == 32 && es <= 1) {
        unsigned long long int old = atomicCAS(&finished, 0, 1);

        if (!old) {

            for (int i = 0; i < len; ++i) {
                out[i] = buff[i];
            }

            for (int i = 0; i < 32; ++i) {
                out[16 + i] = outhex[i]; //hex[outhex[i]];
            }

        }
    }
}


""")
C:\Users\User\Anaconda2\lib\site-packages\ipykernel\__main__.py:75: UserWarning: The CUDA compiler succeeded, but said the following:
kernel.cu
kernel.cu(159): warning: expression has no effect

kernel.cu(177): warning: variable "foo" was declared but never referenced


In [34]:
brute_md5 = mod.get_function("brute_md5")

result = numpy.zeros((48), numpy.uint8)
brute_md5(pycuda.driver.Out(result), grid=(100,100,100), block=(1000,1,1), time_kernel=True)
Out[34]:
0.8010001182556152
In [35]:
''.join(map(chr, result))
Out[35]:
'0000000000\x00\x00\x00\x00\x00\x00\x00\x00\xfc\xf3\x00\x08\xfc\xf7\xfb\xfb\x07\x07\x01\r\xff\xf8\x04\x0c\xfe\xfa\xfa\x00\xfa\xf9\x04\x02\x07\x07\xfa\xfb\xfc\xf8'
In [18]:
''.join(map(chr, result)).encode('hex')
Out[18]:
'303035303030303433330000000000003930303433363639333834333131353036373632346534363432373038313530'
In [25]:
md5('0' * 10)
Out[25]:
'f1b708bba17f1ce948dc979f4d7092bc'
In [21]:
md5('0050000433')
Out[21]:
'091b0c9c4a21b0f51ed4a56da277b705'
In [261]:
md5('0123456789')
Out[261]:
'781e5e245d69b566979b86e28d23f2c7'
In [266]:
md5('0879049425')
Out[266]:
'781e5e242089f7e1692c684d7ad5418e'
In [203]:
md5('00464') == 'fcf2cbb450285857bdfdf61a71ff4d67'
Out[203]:
True
In [163]:
md5('00063')
Out[163]:
'8da131d0e5a369d7bbbc9d41a5728a47'
In [127]:
md5('\0' * 5)
Out[127]:
'ca9c491ac66b2c62500882e93f3719a8'
In [157]:
md5('\0')
Out[157]:
'93b885adfe0da089cdf634904fd59f71'
In [158]:
md5('?')
Out[158]:
'd1457b72c3fb323a2671125aef3eab5d'
In [ ]:
 
In [117]:
''.join(map(chr, result[:16])).encode('hex')
Out[117]:
'dc271beef3243c93a5c11b3fadf4ac36'
In [104]:
md5('')
Out[104]:
'd41d8cd98f00b204e9800998ecf8427e'
In [108]:
md5('0')
Out[108]:
'cfcd208495d565ef66e7dff9f98764da'
In [89]:
ord('0')
Out[89]:
48
In [88]:
md5('00000')
Out[88]:
'dcddb75469b4b4875094e14561e573d8'
In [20]:
from ultra import md5
In [31]:
md5('12345')
Out[31]:
'827ccb0eea8a706c4c34a16891f84e7b'
In [ ]:
 
In [5]:
md5_code = """
/* F, G and H are basic MD5 functions: selection, majority, parity */

#define F(x, y, z) (((x) & (y)) | ((~x) & (z)))
#define G(x, y, z) (((x) & (z)) | ((y) & (~z)))
#define H(x, y, z) ((x) ^ (y) ^ (z))
#define I(x, y, z) ((y) ^ ((x) | (~z))) 

/* ROTATE_LEFT rotates x left n bits */
#define ROTATE_LEFT(x, n) (((x) << (n)) | ((x) >> (32-(n))))

/* FF, GG, HH, and II transformations for rounds 1, 2, 3, and 4 */
/* Rotation is separate from addition to prevent recomputation */
#define FF(a, b, c, d, x, s, ac) \
  {(a) += F ((b), (c), (d)) + (x) + (UINT4)(ac); \
   (a) = ROTATE_LEFT ((a), (s)); \
   (a) += (b); \
  }

#define GG(a, b, c, d, x, s, ac) \
  {(a) += G ((b), (c), (d)) + (x) + (UINT4)(ac); \
   (a) = ROTATE_LEFT ((a), (s)); \
   (a) += (b); \
  }

#define HH(a, b, c, d, x, s, ac) \
  {(a) += H ((b), (c), (d)) + (x) + (UINT4)(ac); \
   (a) = ROTATE_LEFT ((a), (s)); \
   (a) += (b); \
  }

#define II(a, b, c, d, x, s, ac) \
  {(a) += I ((b), (c), (d)) + (x) + (UINT4)(ac); \
   (a) = ROTATE_LEFT ((a), (s)); \
   (a) += (b); \
  }


__device__ void md5(uint *in, uint *hash) {

  uint a, b, c, d;
  
  const uint a0 = 0x67452301;
  const uint b0 = 0xEFCDAB89;
  const uint c0 = 0x98BADCFE;
  const uint d0 = 0x10325476;

  a = a0;
  b = b0;
  c = c0;
  d = d0;

  /* Round 1 */
#define S11 7
#define S12 12
#define S13 17
#define S14 22
  FF ( a, b, c, d, in[ 0], S11, 3614090360); /* 1 */
  FF ( d, a, b, c, in[ 1], S12, 3905402710); /* 2 */
  FF ( c, d, a, b, in[ 2], S13,  606105819); /* 3 */
  FF ( b, c, d, a, in[ 3], S14, 3250441966); /* 4 */
  FF ( a, b, c, d, in[ 4], S11, 4118548399); /* 5 */
  FF ( d, a, b, c, in[ 5], S12, 1200080426); /* 6 */
  FF ( c, d, a, b, in[ 6], S13, 2821735955); /* 7 */
  FF ( b, c, d, a, in[ 7], S14, 4249261313); /* 8 */
  FF ( a, b, c, d, in[ 8], S11, 1770035416); /* 9 */
  FF ( d, a, b, c, in[ 9], S12, 2336552879); /* 10 */
  FF ( c, d, a, b, in[10], S13, 4294925233); /* 11 */
  FF ( b, c, d, a, in[11], S14, 2304563134); /* 12 */
  FF ( a, b, c, d, in[12], S11, 1804603682); /* 13 */
  FF ( d, a, b, c, in[13], S12, 4254626195); /* 14 */
  FF ( c, d, a, b, in[14], S13, 2792965006); /* 15 */
  FF ( b, c, d, a, in[15], S14, 1236535329); /* 16 */

  /* Round 2 */
#define S21 5
#define S22 9
#define S23 14
#define S24 20
  GG ( a, b, c, d, in[ 1], S21, 4129170786); /* 17 */
  GG ( d, a, b, c, in[ 6], S22, 3225465664); /* 18 */
  GG ( c, d, a, b, in[11], S23,  643717713); /* 19 */
  GG ( b, c, d, a, in[ 0], S24, 3921069994); /* 20 */
  GG ( a, b, c, d, in[ 5], S21, 3593408605); /* 21 */
  GG ( d, a, b, c, in[10], S22,   38016083); /* 22 */
  GG ( c, d, a, b, in[15], S23, 3634488961); /* 23 */
  GG ( b, c, d, a, in[ 4], S24, 3889429448); /* 24 */
  GG ( a, b, c, d, in[ 9], S21,  568446438); /* 25 */
  GG ( d, a, b, c, in[14], S22, 3275163606); /* 26 */
  GG ( c, d, a, b, in[ 3], S23, 4107603335); /* 27 */
  GG ( b, c, d, a, in[ 8], S24, 1163531501); /* 28 */
  GG ( a, b, c, d, in[13], S21, 2850285829); /* 29 */
  GG ( d, a, b, c, in[ 2], S22, 4243563512); /* 30 */
  GG ( c, d, a, b, in[ 7], S23, 1735328473); /* 31 */
  GG ( b, c, d, a, in[12], S24, 2368359562); /* 32 */

  /* Round 3 */
#define S31 4
#define S32 11
#define S33 16
#define S34 23
  HH ( a, b, c, d, in[ 5], S31, 4294588738); /* 33 */
  HH ( d, a, b, c, in[ 8], S32, 2272392833); /* 34 */
  HH ( c, d, a, b, in[11], S33, 1839030562); /* 35 */
  HH ( b, c, d, a, in[14], S34, 4259657740); /* 36 */
  HH ( a, b, c, d, in[ 1], S31, 2763975236); /* 37 */
  HH ( d, a, b, c, in[ 4], S32, 1272893353); /* 38 */
  HH ( c, d, a, b, in[ 7], S33, 4139469664); /* 39 */
  HH ( b, c, d, a, in[10], S34, 3200236656); /* 40 */
  HH ( a, b, c, d, in[13], S31,  681279174); /* 41 */
  HH ( d, a, b, c, in[ 0], S32, 3936430074); /* 42 */
  HH ( c, d, a, b, in[ 3], S33, 3572445317); /* 43 */
  HH ( b, c, d, a, in[ 6], S34,   76029189); /* 44 */
  HH ( a, b, c, d, in[ 9], S31, 3654602809); /* 45 */
  HH ( d, a, b, c, in[12], S32, 3873151461); /* 46 */
  HH ( c, d, a, b, in[15], S33,  530742520); /* 47 */
  HH ( b, c, d, a, in[ 2], S34, 3299628645); /* 48 */

  /* Round 4 */
#define S41 6
#define S42 10
#define S43 15
#define S44 21
  II ( a, b, c, d, in[ 0], S41, 4096336452); /* 49 */
  II ( d, a, b, c, in[ 7], S42, 1126891415); /* 50 */
  II ( c, d, a, b, in[14], S43, 2878612391); /* 51 */
  II ( b, c, d, a, in[ 5], S44, 4237533241); /* 52 */
  II ( a, b, c, d, in[12], S41, 1700485571); /* 53 */
  II ( d, a, b, c, in[ 3], S42, 2399980690); /* 54 */
  II ( c, d, a, b, in[10], S43, 4293915773); /* 55 */
  II ( b, c, d, a, in[ 1], S44, 2240044497); /* 56 */
  II ( a, b, c, d, in[ 8], S41, 1873313359); /* 57 */
  II ( d, a, b, c, in[15], S42, 4264355552); /* 58 */
  II ( c, d, a, b, in[ 6], S43, 2734768916); /* 59 */
  II ( b, c, d, a, in[13], S44, 1309151649); /* 60 */
  II ( a, b, c, d, in[ 4], S41, 4149444226); /* 61 */
  II ( d, a, b, c, in[11], S42, 3174756917); /* 62 */
  II ( c, d, a, b, in[ 2], S43,  718787259); /* 63 */
  II ( b, c, d, a, in[ 9], S44, 3951481745); /* 64 */

  a += a0;
  b += b0;
  c += c0;
  d += d0;
  
  hash[0] = a;
  hash[1] = b;
  hash[2] = c;
  hash[3] = d;
  
  return;
}
"""
In [ ]:
 
In [21]:
mod = pycuda.compiler.SourceModule("""
__global__ void multiply_them(float *dest, float *a, float *b)
{
  const int i = threadIdx.x;
  dest[i] = a[i] * b[i];
}
""")

multiply_them = mod.get_function("multiply_them")

a = numpy.random.randn(400).astype(numpy.float32)
b = numpy.random.randn(400).astype(numpy.float32)

dest = numpy.zeros_like(a)
multiply_them(pycuda.driver.Out(dest), pycuda.driver.In(a), pycuda.driver.In(b), block=(400,1,1))

print numpy.allclose(dest, a*b)
1 устройств доступно
0 : GeForce GTX 1060
	compute capability version: (6, 1)
	total memory: 6442450944
	attributes: {pycuda._driver.device_attribute.MAX_THREADS_PER_BLOCK: 1024, pycuda._driver.device_attribute.MAX_BLOCK_DIM_X: 1024, pycuda._driver.device_attribute.MAX_BLOCK_DIM_Y: 1024, pycuda._driver.device_attribute.MAX_BLOCK_DIM_Z: 64, pycuda._driver.device_attribute.MAX_GRID_DIM_X: 2147483647, pycuda._driver.device_attribute.MAX_GRID_DIM_Y: 65535, pycuda._driver.device_attribute.MAX_GRID_DIM_Z: 65535, pycuda._driver.device_attribute.MAX_SHARED_MEMORY_PER_BLOCK: 49152, pycuda._driver.device_attribute.TOTAL_CONSTANT_MEMORY: 65536, pycuda._driver.device_attribute.WARP_SIZE: 32, pycuda._driver.device_attribute.MAX_PITCH: 2147483647, pycuda._driver.device_attribute.MAX_REGISTERS_PER_BLOCK: 65536, pycuda._driver.device_attribute.CLOCK_RATE: 1670500, pycuda._driver.device_attribute.TEXTURE_ALIGNMENT: 512, pycuda._driver.device_attribute.GPU_OVERLAP: 1, pycuda._driver.device_attribute.MULTIPROCESSOR_COUNT: 10, pycuda._driver.device_attribute.KERNEL_EXEC_TIMEOUT: 1, pycuda._driver.device_attribute.INTEGRATED: 0, pycuda._driver.device_attribute.CAN_MAP_HOST_MEMORY: 1, pycuda._driver.device_attribute.COMPUTE_MODE: pycuda._driver.compute_mode.DEFAULT, pycuda._driver.device_attribute.MAXIMUM_TEXTURE1D_WIDTH: 131072, pycuda._driver.device_attribute.MAXIMUM_TEXTURE2D_WIDTH: 131072, pycuda._driver.device_attribute.MAXIMUM_TEXTURE2D_HEIGHT: 65536, pycuda._driver.device_attribute.MAXIMUM_TEXTURE3D_WIDTH: 16384, pycuda._driver.device_attribute.MAXIMUM_TEXTURE3D_HEIGHT: 16384, pycuda._driver.device_attribute.MAXIMUM_TEXTURE3D_DEPTH: 16384, pycuda._driver.device_attribute.MAXIMUM_TEXTURE2D_ARRAY_WIDTH: 32768, pycuda._driver.device_attribute.MAXIMUM_TEXTURE2D_ARRAY_HEIGHT: 32768, pycuda._driver.device_attribute.MAXIMUM_TEXTURE2D_ARRAY_NUMSLICES: 2048, pycuda._driver.device_attribute.SURFACE_ALIGNMENT: 512, pycuda._driver.device_attribute.CONCURRENT_KERNELS: 1, pycuda._driver.device_attribute.ECC_ENABLED: 0, pycuda._driver.device_attribute.PCI_BUS_ID: 1, pycuda._driver.device_attribute.PCI_DEVICE_ID: 0, pycuda._driver.device_attribute.TCC_DRIVER: 0, pycuda._driver.device_attribute.MEMORY_CLOCK_RATE: 4004000, pycuda._driver.device_attribute.GLOBAL_MEMORY_BUS_WIDTH: 192, pycuda._driver.device_attribute.L2_CACHE_SIZE: 1572864, pycuda._driver.device_attribute.MAX_THREADS_PER_MULTIPROCESSOR: 2048, pycuda._driver.device_attribute.ASYNC_ENGINE_COUNT: 2, pycuda._driver.device_attribute.UNIFIED_ADDRESSING: 1, pycuda._driver.device_attribute.MAXIMUM_TEXTURE1D_LAYERED_WIDTH: 32768, pycuda._driver.device_attribute.MAXIMUM_TEXTURE1D_LAYERED_LAYERS: 2048, pycuda._driver.device_attribute.MAXIMUM_TEXTURE2D_GATHER_WIDTH: 32768, pycuda._driver.device_attribute.MAXIMUM_TEXTURE2D_GATHER_HEIGHT: 32768, pycuda._driver.device_attribute.MAXIMUM_TEXTURE3D_WIDTH_ALTERNATE: 8192, pycuda._driver.device_attribute.MAXIMUM_TEXTURE3D_HEIGHT_ALTERNATE: 8192, pycuda._driver.device_attribute.MAXIMUM_TEXTURE3D_DEPTH_ALTERNATE: 32768, pycuda._driver.device_attribute.PCI_DOMAIN_ID: 0, pycuda._driver.device_attribute.TEXTURE_PITCH_ALIGNMENT: 32, pycuda._driver.device_attribute.MAXIMUM_TEXTURECUBEMAP_WIDTH: 32768, pycuda._driver.device_attribute.MAXIMUM_TEXTURECUBEMAP_LAYERED_WIDTH: 32768, pycuda._driver.device_attribute.MAXIMUM_TEXTURECUBEMAP_LAYERED_LAYERS: 2046, pycuda._driver.device_attribute.MAXIMUM_SURFACE1D_WIDTH: 32768, pycuda._driver.device_attribute.MAXIMUM_SURFACE2D_WIDTH: 131072, pycuda._driver.device_attribute.MAXIMUM_SURFACE2D_HEIGHT: 65536, pycuda._driver.device_attribute.MAXIMUM_SURFACE3D_WIDTH: 16384, pycuda._driver.device_attribute.MAXIMUM_SURFACE3D_HEIGHT: 16384, pycuda._driver.device_attribute.MAXIMUM_SURFACE3D_DEPTH: 16384, pycuda._driver.device_attribute.MAXIMUM_SURFACE1D_LAYERED_WIDTH: 32768, pycuda._driver.device_attribute.MAXIMUM_SURFACE1D_LAYERED_LAYERS: 2048, pycuda._driver.device_attribute.MAXIMUM_SURFACE2D_LAYERED_WIDTH: 32768, pycuda._driver.device_attribute.MAXIMUM_SURFACE2D_LAYERED_HEIGHT: 32768, pycuda._driver.device_attribute.MAXIMUM_SURFACE2D_LAYERED_LAYERS: 2048, pycuda._driver.device_attribute.MAXIMUM_SURFACECUBEMAP_WIDTH: 32768, pycuda._driver.device_attribute.MAXIMUM_SURFACECUBEMAP_LAYERED_WIDTH: 32768, pycuda._driver.device_attribute.MAXIMUM_SURFACECUBEMAP_LAYERED_LAYERS: 2046, pycuda._driver.device_attribute.MAXIMUM_TEXTURE1D_LINEAR_WIDTH: 134217728, pycuda._driver.device_attribute.MAXIMUM_TEXTURE2D_LINEAR_WIDTH: 131072, pycuda._driver.device_attribute.MAXIMUM_TEXTURE2D_LINEAR_HEIGHT: 65000, pycuda._driver.device_attribute.MAXIMUM_TEXTURE2D_LINEAR_PITCH: 2097120, pycuda._driver.device_attribute.MAXIMUM_TEXTURE2D_MIPMAPPED_WIDTH: 32768, pycuda._driver.device_attribute.MAXIMUM_TEXTURE2D_MIPMAPPED_HEIGHT: 32768, pycuda._driver.device_attribute.COMPUTE_CAPABILITY_MAJOR: 6, pycuda._driver.device_attribute.COMPUTE_CAPABILITY_MINOR: 1, pycuda._driver.device_attribute.MAXIMUM_TEXTURE1D_MIPMAPPED_WIDTH: 16384, pycuda._driver.device_attribute.STREAM_PRIORITIES_SUPPORTED: 1, pycuda._driver.device_attribute.GLOBAL_L1_CACHE_SUPPORTED: 1, pycuda._driver.device_attribute.LOCAL_L1_CACHE_SUPPORTED: 1, pycuda._driver.device_attribute.MAX_SHARED_MEMORY_PER_MULTIPROCESSOR: 98304, pycuda._driver.device_attribute.MAX_REGISTERS_PER_MULTIPROCESSOR: 65536, pycuda._driver.device_attribute.MANAGED_MEMORY: 1, pycuda._driver.device_attribute.MULTI_GPU_BOARD: 0, pycuda._driver.device_attribute.MULTI_GPU_BOARD_GROUP_ID: 0}
True
In [ ]:
 

todo распознавание лиц, объектов, сегментация, распознавание речи, ImageNet

  • Тензорная операция, нелинейность, sigmoid, ReLU, обратное распространение ошибки по слоям
  • Фреймворк DL, параллелизация на GPU, автодифференцирование
  • Кирпичи conv, maxpool, dropout, batchnorm
  • Дообучение, расписание обучения, NAG, ADAM
  • Репозитории с претренированными моделями, AlexNet, VGG, ResNet
  • CNN, R-CNN, artistic style transfer
  • Генерация батчей: шум, аффинные трансформации
  • autoencoder, word2vec
  • GAN
  • LSTM, RNN

todo Deep learning

CUDA 9.0 требует Visual Studio 2017
CuDNN https://developer.nvidia.com/cudnn
надо ли? в Path:
c:\Program Files (x86)\Microsoft Visual Studio\2017\Enterprise\VC\Tools\MSVC\14.10.25017\bin\HostX64\x64\

pycuda? или OpenCL
pytorch? tensorflow?

Tensorflow это Ким Кардашьян машинного обучения.

todo

Theano (0.8.0)
Lasagne (0.2.dev1)
pip install --upgrade https://github.com/Theano/Theano/archive/master.zip
pip install --upgrade https://github.com/Lasagne/Lasagne/archive/master.zip

conda install mingw libpython
pip install --upgrade --no-deps git+git://github.com/Theano/Theano.git
    убедиться, чтобы он вызывал для компиляции свой, mingwшный gcc (x64, 4.7.0)
        иначе может быть sorry, unimplemented: 64-bit mode not compiled in
    если Theano не скомпилит, что ему там нужно, выдаст Can not import gof

Добавить системную переменную окружения THEANO_FLAGS со значением “floatX=float32,device=gpu,nvcc.fastmath=True”
Using gpu device 0: GeForce GT 540M (CNMeM is disabled, CuDNN not available)
    CNMeM (a faster CUDA memory allocator) -- стоит использовать
theano.config.device должен вывести gpu
Можно os.environ.update({'THEANO_FLAGS': '...'})

theano.printing.pydotprint(f, outfile="f.png", var_with_name_simple=True)

todo

[под админом] pip install protobuf
скачать https://github.com/Microsoft/caffe и следовать инструкциям по установке
/windows/CommonSettings.props.example -> /windows/CommonSettings.props
    <UseCuDNN>false</UseCuDNN>
    <PythonSupport>true</PythonSupport>
    <CudaArchitecture>compute_20,sm_20</CudaArchitecture>
    <PythonDir>c:\Users\User\Anaconda2</PythonDir>
открыть /windows/Caffe.sln в VS 2013 и сбилдить
скопировать /Build/x64/Release/pycaffe/caffe/ -> c:\Users\User\Anaconda2\Lib\site-packages\caffe\
переименовать папку со скачанным caffe-master, иначе тот почему там начинает искать файлы

todo Составить табличку зоопарков Theano, Keras, Lasagne, Caffe, Torch, Tensorflow, CNTK, еще?

todo

CNTK
https://docs.microsoft.com/en-us/cognitive-toolkit/setup-windows-python?tabs=cntkpy22
https://docs.microsoft.com/en-us/cognitive-toolkit/using-cntk-with-keras

pip install cntk-gpu

todo

Keras (0.3.2)
    https://github.com/fchollet/hualos Keras Total Visualization project
pip install keras
    from keras.datasets import mnist, boston_housing, cifar10, imdb
    from keras.layers.convolutional import Convolution2D, MaxPooling2D
    from keras.layers.core import Dense, Activation, Dropout, Flatten, TimeDistributedDense
    from keras.layers.embeddings import Embedding
    from keras.layers.recurrent import LSTM, SimpleRNN
    from keras.models import Graph, Sequential
    from keras.optimizers import SGD, Adam
    from keras.utils import np_utils
In [ ]:
from keras.model import Sequential
from keras.layers import Dense

data = random((1000,100))
labels = randint(2, size=(1000,1))

model = Sequential()
model.add(Dense(32, activation='relu', input_dim=100, kernel_initializer='uniform'))
model.add(Dense(2, activation='sigmoid'))
model.compile(optimizer='rmsprop', loss='binary_crossentropy', metrics=['accuracy'])
model.fit(data, labels, epochs=10, batch_size=32, verbose=1, validation_data=(X_test, Y_test))
predictions = model.predict(data)
In [ ]:
keras.preprocessing.sequence.pad_sequences(x_train, maxlen=80)
keras.utils.to_categorical(y_train, num_classes)
Dropout(0.2)
activatoin='softmax'
Conv2D(32, (3,3), padding='same', input_shape=...)
Activation('relu')
MaxPooling2D(pool_size=(2,2))
Flatten()

Embedding(20000, 128)
LSTM(128, dropout=0.2, recurrent_dropout=0.2)

optimizer='adam'
optimizer=keras.optimizers.RMSprop(lr=0.0001, decay=1e-6)
loss='mse'
In [ ]:
model.output_shape
model.summary()
model.get_config()
model.get_weights()
model.save('model.h5')
model = keras.models.load_model('model.h5')

model.evaluate(X_test, Y_test, batch_size=32)
model.predict_classes(X_test, batch_size=32)
In [ ]:
model.fit(..., callbacks=[keras.callbacks.EarlyStopping(patience=2)])

todo

LSH lshash
sklearn:
    multiclass (OneVsRestClassifier)
    neural_network
    utils (resample)

todo обучение с подкреплением UCB1

todo sentiment analysis?

todo метод отжига

todo

rpy2, R.arima

statsmodel, minepy (http://minepy.sourceforge.net/docs/1.0.0/install.html) -- для MIC, "корреляции 21-го века"
    import statsmodels.graphics.mosaicplot
    from statsmodels.tsa.arima_model import ARIMA