Xamarin University

• самообучение;
• онлайн-классы.

Самообучение

Онлайн-занятия

• методичка в виде веб-файлов;
• проекты для каждого задания;
• проект, который должен получится в итоге.

Не забываем про сертификационный трек

Время занятий

Офисный час

Переходим к практике: как я проходил лекции и сертификацию

Сертификационный экзамен

Попытка №2

• ссылку на форму для отправки мне подарка;
• предложение зарегистрироваться в DevConnect – сеть разработчиков Xamarin;
• ссылку на официальную LinkedIn группу сертифицированных разработчиков;
• ссылку на сертификат в формате PDF;
• ссылку на проверку статуса Xamarin Certified Developer.

Итог

1. Получил 3 предложения о работе в течении недели с HeadHunter.
2. Одну заявку на Upwork.
3. 1 письмо с DevConnect о консультации.
4. 2 предложения о менторстве.

Об авторе

• представленный продукт хорошо проработан (наличие приложений для Windows и Mac, отдельное — для стримера, мобильное приложение и веб-форма для зрителя);
• хорошее понимание целевой аудитории и проблематики продукта;
• качество презентации идеи на финальной части конкурса;
• выбор подходящих методов API QIWI Кошелька для пользовательских задач;
• YouTube — новый телевизор, а стримеры — новые телеведущие. Выбор перспективного направления с долгосрочным трендом на рост интереса.

Почётные упоминания

В целом о QIWI API Contest

Чуть менее чем самая быстрая, переносимая, 64-битная хэш-функция, с достойным качеством.
Да, вжух и в дамки, примерно так. Читаем дальше?

Опуская цитирование доказательств и прочие выкладки можно констатировать:

• Надлежащее выполнение всех пунктов, одновременно с обеспечением производительности, является достаточно трудной задачей, решение которой даёт хорошую криптографическую хэш-функцию. Но мы пока заниматься этим не будем.
• Обеспечение базового качества требует достаточно большого количества операций АЛУ. Проще говоря, качество всегда конфликтует со скоростью.
• Получение качественного результата с разрядностью больше разрядности операций АЛУ требует более чем кратного увеличения количества перемешиваний, а следовательно базовых операций АЛУ.
• В целом, создание быстрой кэш-функции предполагает достижения взвешенного компромисса между скоростью, качеством и разрядностью результата.

Так вот, можно сказать, что t1ha появилась в результате поиска компромисса между качеством и скоростью, одновременно с учетом возможностей современных процессоров и уже найденных способов (арифметико-логических комбинаций) перемешивания и распространения зависимостей (лавинного эффекта).

Базовый вариант t1ha является (самой) быстрой переносимой хэш-функцией для построения хэш-таблиц и других родственных применений. Поэтому базовый вариант t1ha ориентирован на 64-битные little-endian архитектуры, принимает 64-битное подсаливающее значение (seed) и выдает 64-битный результат, который включает усиление длиной ключа и seed-ом. Стоит отметить, t1ha намеренно сконструирована так, чтобы возвращать 0 при нулевых входных данных (ключ нулевого размера и нулевой seed).

Оценить качество хэш-функции во всех аспектах достаточно сложно. Можно идти аналитическим путем, либо проводить различные статистические испытания. К сожалению, аналитический подход малоэффективен для оценки хэш-функций с компромиссом между качеством и скоростью. Причем сравнительная аналитическая оценка таких функций стремиться к субъективной.

Напротив, для статистических испытаний легко получить прозрачные количественные оценки. При этом есть хорошо зарекомендовавшие себя тестовые пакеты, например SMHasher. Для t1ha результаты просты — все варианты t1ha проходят все тесты без каких-либо замечаний. С другой стороны, не следует считать, что у t1ha есть какие-либо свойства сверх тех, что необходимы для целевого применения (построение хэш-таблиц).

Читатели наверняка оценили бы тщательный и глубокий анализ качественности и/или стойкости t1ha. Однако, исходя из целевых областей применения t1ha это представляется излишним. Проще говоря, нам была важнее скорость, в том числе для коротких ключей. Поэтому много-раундовое перемешивание не рассматривалось. Представляемый вариант t1ha экономит на спичках тактах и выдает 64-битный результат — практически бессмысленно измерять найденный компромисс иначе как статистически, а эти результаты просто хороши.

Бенчмарки

Стоит пояснить наличие в заголовке словосочетания «самая быстрая». Действительно, крайне маловероятно, что существует хэш-функция, которая будет полезной и одновременно самой быстрой на всех платформах/архитектурах. На разных процессорах доступны разные наборы инструкций, а схожие инструкции выполняются с разной эффективностью. Очевидно, что «всеобщая самая быстрая» функция, скорее всего, не может быть создана. Однако, представляется допустимым использовать «самая быстрая» для функции, которая является переносимой и одновременно самой быстрой как минимум на самой распространенной платформе (x86_64), при этом имея мало шансов проиграть на любом современном процессоре с достойным оптимизирующим компилятором.

В состав исходных текстов проекта входить тест, который проверяет как корректность результата, так и замеряет скорость работы каждого реализованного варианта. При этом на x86, в зависимости от возможностей процессора (и компилятора) могут проверяться дополнительные варианты функций, а замеры производится в тактах процессора.

Кроме этого, на сайте проекта приведены таблицы с результатам замеров производительности посредством доработанной версии SMHasher от Reini Urban. Соответственно, все цифры можно перепроверить и/или получить результаты на конкретном процессоре при использовании конкретного компилятора.

Здесь же можно привести сопоставление с некоторыми ближайшими конкурентами t1ha.

Хэширование коротких ключей (среднее для 1..31 байта).
Смотрим на правую колонку «Cycles/Hash» (чем меньше значение, тем быстрее):

Хэширование длинных ключей (256 Кб).
Смотрим на среднюю колонку «MiB/Second» (чем больше значение, тем быстрее):

Варианты t1ha

Разработка t1ha преследовала сугубо практические цели. Первой такой целью было получение быстрой переносимой и достаточно качественной функции для построения хеш-таблиц.

Затем потребовалась максимально быстрый вариант хэш-функции, который давал-бы сравнимый по качеству результат, но был максимально адаптирован на целевую платформу. Например, базовый вариант t1ha работает с little-endian порядком байт, из-за чего на big-endian архитектурах требуется конвертация с неизбежной потерей производительности. Так почему-бы не избавиться от лишних операций на конкретной целевой платформе? Таким же образом было добавлено ещё несколько вариантов:

• Упрощенный вариант для 32-битных платформ, как little, так и big-endian.
• Вариант с использованием инструкций AES-NI для процессоров без AVX.
• Два варианта с использованием инструкций AES-NI с использованием AVX.

Чуть позже стало понятно что потребуются ещё варианты, сконструированные для различных применений, включая разную разрядность результата, требования к качеству и стойкости. Такое многообразие потребовало наведения порядка. Что выразилось в смене схемы именования, в которой цифровой суффикс обозначает «уровень» функции:

• t1ha0() — максимально быстрый вариант для текущего процессора.
• t1ha1() — базовый переносимый 64-битный вариант t1ha.
• t1ha2() — переносимый 64-битный вариант с чуть большей заботой о качестве.
• t1ha3() — быстрый переносимый 128-битный вариант для получения отпечатков.
• и т.д.

В этой схеме предполагается, что t1ha0() является диспетчером, который реализует перенаправление в зависимости от платформы и возможностей текущего процессора. Кроме этого, не исключается использование суффиксов «_le» и «_be» для явного выбора между little-endian и big-endian вариантами. Таким образом, под «вывеской» t1ha сейчас находиться несколько хеш-функций и это семейство будет пополняться, в том числе с прицелом на отечественный E2K «Эльбрус».

Представление о текущем наборе функций и их свойствах можно получить из вывода теста. Стоит лишь отметить, что все функции проходят все тесты SMHasher, а производительность вариантов AES-NI сильно варьируется в зависимости от модели процессора:

Simple bench for x86 (large keys, 262144 bytes):
              t1ha1_64le:   47151 ticks,  0.1799 clk/byte,  16.679 Gb/s @3GHz
              t1ha1_64be:   61602 ticks,  0.2350 clk/byte,  12.766 Gb/s @3GHz
              t1ha0_32le:   94101 ticks,  0.3590 clk/byte,   8.357 Gb/s @3GHz
              t1ha0_32be:   99804 ticks,  0.3807 clk/byte,   7.880 Gb/s @3GHz

Simple bench for x86 (small keys, 31 bytes):
              t1ha1_64le:      39 ticks,  1.2581 clk/byte,   2.385 Gb/s @3GHz
              t1ha1_64be:      42 ticks,  1.3548 clk/byte,   2.214 Gb/s @3GHz
              t1ha0_32le:      51 ticks,  1.6452 clk/byte,   1.824 Gb/s @3GHz
              t1ha0_32be:      54 ticks,  1.7419 clk/byte,   1.722 Gb/s @3GHz

Simple bench for AES-NI (medium keys, 127 bytes):
     t1ha0_ia32aes_noavx:      72 ticks,  0.5669 clk/byte,   5.292 Gb/s @3GHz
       t1ha0_ia32aes_avx:      78 ticks,  0.6142 clk/byte,   4.885 Gb/s @3GHz
      t1ha0_ia32aes_avx2:      78 ticks,  0.6142 clk/byte,   4.885 Gb/s @3GHz

Simple bench for AES-NI (large keys, 262144 bytes):
     t1ha0_ia32aes_noavx:   38607 ticks,  0.1473 clk/byte,  20.370 Gb/s @3GHz
       t1ha0_ia32aes_avx:   38595 ticks,  0.1472 clk/byte,  20.377 Gb/s @3GHz
      t1ha0_ia32aes_avx2:   19881 ticks,  0.0758 clk/byte,  39.557 Gb/s @3GHz

Остальное здесь.

Спасибо за внимание. Всем добра.

Закрепление проекта 3CX за партнером

• Автоматические зачисление партнерских баллов на аккаунт партнера: это позволит вам быстрее перейти на следующий уровень скидок.
  
• Бесплатная техподдержка для закрепленных за вами пользователей: вскоре предоставление поддержки партнеру (от имени и по вопросу пользователя) будет привязано к лицензионному ключу инсталляции.
  
• Ключевая информация об установленных клиентских системах 3CX в вашем партнерском портале: свободное место на диске сервера, количество пользователей системы, предупреждение о ненадежных паролях, время создания последней резервной копии, срок действия подписки на обновления / годовой лицензии, контроль качества вызовов (будет добавлен).
  
• Дальнейшее сопровождение системы: продление подписки на обновление или расширение редакции 3CX одним кликом — и только вами! Обратите внимание, пользователи, которые не привязаны к партнерскому аккаунту, имеют возможность приобретать обновления системы напрямую у компании 3CX.
  

Связывание из интерфейса 3CX

Связывание во время установки

Связывание потенциальных пользователей

• Установка PBX Express: https://pbxexpress.3cx.com/?resellerId=[ID]
  
• Обычная загрузка: https://www.3cx.ru/ip-pbx/download-atc/?resellerId=[ID]
  

Новые отчеты колл-центра 3CX

• Распределение вызовов по времени (Call Distribution)
  
• Среднее время ожидания клиента в Очереди вызовов (Average Queue Waiting Time)
  
• Активность операторов по времени (User Activity)
  
• Отвеченные / неотвеченные вызовы в Очереди вызовов по времени (Queue Answered / Unanswered Calls)
  

Гистограмма Распределение вызовов по времени

График Среднее время ожидания абонента (клиента) в Очереди вызовов

Гистограмма Действия пользователей (Активность операторов) по времени

Гистограмма Отвеченные / неотвеченные вызовы Очереди по времени

Принцип работы

• разрешает установку приложений из неизвестных источников
• устанавливает BankBot из набора и запускает его
• активирует права администратора для BankBot
• устанавливает BankBot в качестве приложения для обмена SMS по умолчанию
• получает разрешение для показа поверх других приложений

Чем опасен BankBot

Как очистить зараженное устройство?

• Наличие приложения под названием Google Update (рисунок 8: находится в разделе меню Settings > Application manager/Apps > Google Update)
• Активный администратор устройства под названием System update (рисунок 9: находится в Settings > Security > Device administrators).
• Повторяющееся появление уведомления Google Service (рисунок 2)

Как обезопасить себя?

• По возможности используйте официальные магазины приложений, а не альтернативные источники. И хотя и они не безупречны, Google Play действительно применяет продвинутые механизмы обеспечения безопасности, чего не делают сторонние магазины.
• Проверяйте приложения до скачивания – просматривайте число загрузок, рейтинг и отзывы.
• После запуска любого установленного приложения обращайте внимание на запросы разрешений.

Образцы / Индикаторы компрометации

Глава 1. Мотивированные установки

Глава 2. Где их взять и почему США?

1. www.waypedia.com
2. www.cpimobi.com
3. www.keyapp.top
4. www.mopeak.com
5. www.cpidroid.com

Глава 3. Цели, бюджет, сроки

Глава 4. Процесс

Глава 5. Подводим итоги

Довольно часто программисты и специалисты из области data science сталкиваются с задачей поиска похожих профилей пользователей или подбора схожей музыки. Решения могут сводиться к преобразованию объектов в векторную форму и поиску ближайших.

Мы тоже столкнулись с необходимостью поиска ближайших соседей в задаче распознавания лиц. Там мы формируем векторные представления лиц при помощи нейросети и ищем ближайшие векторы уже известных людей. Изначально для поиска мы выбрали Annoy, как хорошо известный и проверенный алгоритм, используемый в том числе в Spotify. Но быстро поняли, что с его аппетитами по памяти мы либо не вмещаемся в RAM, либо сильно теряем в точности. Это привело к небольшому исследованию. О результатах которого пойдет речь ниже.

Чтобы разбавить теорию практикой, в статье будет немного кода, где мы ищем ближайших соседей для слов. Получим их векторные представления, используя популярный word2vec. Этот алгоритм выдает близкие векторы для семантически похожих слов. В word2vec CBOW векторные представления получаются как побочный продукт обучения небольшой нейросети, которая предсказывает слово по его окружению. Любопытно, что с векторами можно проворачивать арифметические операции наподобие king + (woman – man) = queen.

Посмотрим, как с этим работать в коде.

model = gensim.models.KeyedVectors.load_word2vec_format('./GoogleNews-vectors-negative300.bin', binary=True)
start = time.time()
pprint.pprint(model.wv.most_similar(positive=['king']))
print('time:', time.time() - start)
print('king + (woman - man) = ', model.wv.most_similar(positive=['woman', 'king'], negative=['man'])[0])
print('Japan + (Moscow - Russia) = ', model.wv.most_similar(positive=['Moscow', 'Japan'], negative=['Russia'])[0])

Получаем:

    [(u'kings', 0.7138045430183411),
     (u'queen', 0.6510956883430481),
     (u'monarch', 0.6413194537162781),
     (u'crown_prince', 0.6204219460487366),
     (u'prince', 0.6159993410110474),
     (u'sultan', 0.5864823460578918),
     (u'ruler', 0.5797567367553711),
     (u'princes', 0.5646552443504333),
     (u'Prince_Paras', 0.5432944297790527),
     (u'throne', 0.5422105193138123)]
    time: 0.236690998077
    king + (woman - man) =  (u'queen', 0.7118192911148071)
    Japan + (Moscow - Russia) =  (u'Tokyo', 0.8696038722991943)

В примере выше использовалась библиотека для работы с текстом gensim и word2vec модель (1,5 Гбайт) от Google, которая насчитывает 3 миллиона слов и коротких фраз. В выводе кода видно, что к королю близки королевы, монархи и принцы. Также мы убедились, что арифметика с векторами работает. Однако четверть секунды на один запрос — не очень привлекательно, а ведь в gensim сравнительно хорошая реализация bruteforce-поиска (с подсчетом расстояний до всех известных объектов). Далее мы рассмотрим методы, позволяющие сократить это время в сотни раз лишь с небольшими потерями в точности.

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

nbrs = NearestNeighbors(algorithm='brute', metric='cosine')
nbrs.fit(model.wv.syn0norm)
king_vec = model.wv['king'][np.newaxis, :]
# замерим скорость поиска сосдей к королю без разделения пространства и заодно выведем результат
start = time.time()
idxs = nbrs.kneighbors(king_vec, return_distance=False, n_neighbors=10)[0]
print('full search time:', time.time() - start)
print([model.wv.index2word[idx] for idx in idxs])

# выберем 2 случайных вектора и получем коэффициенты задающие плоскость между ними
vec1_idx = random.randint(0, model.wv.syn0norm.shape[0])
vec2_idx = random.randint(0, model.wv.syn0norm.shape[0])
plane = model.wv.syn0norm[vec1_idx] - model.wv.syn0norm[vec2_idx]

# в результате следующего умножения матрица-вектор, мы получим вектор. 
# Знаки элементов этого вектора указывают с какой стороны разделяющей плоскости оказалось слово
scalar = model.wv.syn0norm.dot(np.transpose(plane))

# определим с какой стороны плоскости запрос и подготовим бинарную маску для выборки векторов по ту же сторону плоскости
if king_vec.dot(plane) > 0:
    mask = scalar > 0
else:
    mask = scalar < 0

print('elements in mask:', mask.sum())

half_nbrs = NearestNeighbors(algorithm='brute', metric='cosine')
half_nbrs.fit(model.wv.syn0norm[mask])
half_index2word = list(compress(model.wv.index2word, mask))

start = time.time()
idxs = half_nbrs.kneighbors(king_vec, return_distance=False, n_neighbors=10)[0]
print('half search time:', time.time() - start)
print([half_index2word[idx] for idx in idxs])

Получаем:

    full search time: 20.3163180351
    [u'king', u'kings', u'queen', u'monarch', u'crown_prince', u'prince', u'sultan', u'ruler', u'princes', u'Prince_Paras']
    elements in mask: 1961204
    half search time: 9.15824007988
    [u'king', u'kings', u'queen', u'monarch', u'crown_prince', u'prince', u'sultan', u'ruler', u'princes', u'Prince_Paras']

Так мы сократили вычисления вдвое, потеряв в точности только рядом с плоскостью. В кое-каких алгоритмах, которые мы рассмотрим дальше, используются похожие трюки.

1. HNSW

В 2013 году был опубликован один из лучших алгоритмов поиска ближайших соседей Navigable Small World (NSW). В 2016-м появился его наследник Hierarchical Navigable Small World (HNSW).

Начнем с родительского алгоритма NSW. Он основан на графе «мир тесен». Эти графы имеют любопытную и полезную нам особенность: пара вершин с большой вероятностью не смежна, но они достижимы за сравнительно небольшое число шагов ($$ в среднем). Такие графы встречаются довольно часто. К примеру, нейронные сети мозга, группы в социальных сетях и семантическая сеть WordNet — это графы SW. В нашем случае вершинами являются векторы, а ребра соединяют их с ближайшими. В графе также представлены ребра, соединяющие вершины на большом расстоянии.

Для поиска соседей мы обходим граф в поисках вершин с минимальным расстоянием до запроса. Начинаем со случайной вершины, считаем расстояние от непосещенных вершин «друзей» (вершин, соединенных с текущей ребром) до запроса и переходим в вершину с наименьшим расстоянием. Длинные ребра придают графу свойства тесного мира и позволяют быстро перемещаться в область близких к запросу объектов, а короткие — жадно искать ближайших соседей.

По мере обхода графа обновляем небольшой список ближайших соседей и останавливаемся, если на очередной итерации список не обновился.

K-NNSearch(object q, integer: m, k)
1 TreeSet [object] tempRes, candidates, visitedSet, result
2 for (i<-0; i < m; i++) do:
3    put random entry point in candidates
4    tempRes<-null
5    repeat:
6       get element c closest from candidates to q
7       remove c from candidates
8       //check stop condition:
9       if c is further than k-th element from result
10          than break repeat
11    //update list of candidates:
12    for every element e from friends of c do:
13       if e is not in visitedSet than
14          add e to visitedSet, candidates, tempRes
15
16    end repeat
17    //aggregate the results:
18    add objects from tempRes to result
19 end for
20 return best k elements from result

index = nmslib.init(space='cosinesimil', method='sw-graph')
nmslib.addDataPointBatch(index, np.arange(model.wv.syn0.shape[0], dtype=np.int32), model.wv.syn0)
index.createIndex({}, print_progress=True)
start = time.time()
items = nmslib.knnQuery(index, 10, king_vec.tolist())
print(time.time() - start)
print([model.wv.index2word[idx] for idx in items])

Получаем:

    0.000545024871826
    [u'king', u'kings', u'queen', u'monarch', u'crown_prince', u'prince', u'sultan', u'ruler', u'princes', u'royal']

Рассмотрим развитие описанной выше идеи в алгоритме Hierarchical Navigable Small World (HNSW). Он во многом схож с NSW, однако теперь мы имеем дело с иерархией графов: на нулевом слое представлены все объекты, а по мере увеличения слоя — все меньшая и меньшая их подвыборка. При этом все объекты на слое $$ есть и на слое $$.

При поиске старт происходит со случайной вершины в графе верхнего слоя, там мы быстро находим близкие к запросу вершины (кандидаты) и возобновляем поиск с них на предыдущем слое.

SearchAtLayer (object q, Set[object] enterPoints, integer: M, ef, layer)
1  Set [object] visitedSet
2  priority_queue [object] candidates (closer - first), result (further - first)
3  candidates, visitedSet, result <- enterPoints
7
4  repeat:
5     object c =candidates.top()
6     candidates.pop()
7     //check stop condition:
8     if d(c,q)>d(result.top(),q) do:
9        break
10    //update list of candidates:
11    for_each object e from c.friends(layer) do:
12       if e is not in visitedSet do:
13          add e to visitedSet
14          if d(e, q)< d(result.top(),q) or result.size()ef do:
17                result.pop()
18 return best k elements from result

K-NNSearch (object query, integer: ef)
1 Set [object] tempRes, enterPoints=[enterpoint]
2 for i=maxLayer downto 1 do:
3    tempRes=SearchAtLayer (query, enterPoints, M, 1, i)
4    enterPoints =closest elements from tempRes
5 tempRes=SearchAtLayer (query, enterPoints, M, ef, 0)
6 return best K of tempRes

1.1. Pros & Cons

+ Алгоритм просто понять

+ Он показывает state-of-the-art результаты

+ Существует эффективная реализация в библиотеке nmslib

+ Небольшие дополнительные расходы памяти на хранение ребер графа

– Алгоритм не поддерживает сжатие векторных представлений, которое мы рассмотрим далее

index = nmslib.init(space='cosinesimil', method='hnsw')
nmslib.addDataPointBatch(index, np.arange(model.wv.syn0.shape[0], dtype=np.int32), model.wv.syn0)
index.createIndex({}, print_progress=True)
start = time.time()
items = nmslib.knnQuery(index, 10, king_vec.tolist())
print(time.time() - start)
print([model.wv.index2word[idx] for idx in items])

Получаем:

    0.000469923019409
    [u'king', u'kings', u'queen', u'monarch', u'crown_prince', u'prince', u'sultan', u'ruler', u'princes', u'Prince_Paras']

2. FAISS

В марте 2017 года Facebook представила свое решение для ANN — библиотеку FAISS. Она объединяет множество методов и алгоритмов. В алгоритме, который мы рассмотрим ниже, расстояния до групп векторов будут приближаться расстоянием до опорной точки рядом с ними. Так мы можем выяснить расстояния от запроса до небольшого количества опорных точек, а затем полным перебором посчитать расстояния до векторов, принадлежащих опорной точке, которая ближе остальных к запросу. Разберем этот алгоритм по частям.

2.1. ADC — asymmetric distance computation

Рассмотрим подробнее следующую идею: расстояния до групп векторов можно приблизить расстояниями до опорных точек рядом с ними. Опорные точки делят пространство на области. Для поиска опорных точек в FAISS используется широко известный алгоритм кластеризации k-means, векторам сопоставляются полученные центроиды.

(0.1, 0.2) -> 1
(0.5, -0.2) -> 2
(0.1, 0.1) -> 1
(0.6, -0.1) -> 2

Векторы коллекции аппроксимируются своими центроидами $$, где $$ и $$ — множество центроидов. Тогда расстояние от запроса $$ до $$ может быть приближено $$. Такой способ вычисления дистанции называют асимметричным. Простыми словами: мы разбили пространство на области и сказали, что расстояние от запроса до группы векторов, попавших в одну область, приблизительно равно расстоянию до центроида, образующего эту область.

Эффективно хранить и быстро получать векторы, принадлежащие центроиду, помогает простой трюк под названием inverted file.

2.2. IVF — inverted file

В IVF мы инвертируем присвоение. Теперь центроидам сопоставляются списки векторов.

1 -> [(0.1, 0.2), (0.1, 0.1)]
2 -> [(0.5, -0.2), (0.6, -0.1)]

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

2.3. PQ — product quantizer

Последняя составляющая, которой мы коснемся в статье, называется product quantizer. Она обеспечивает сжатие векторов с потерями и применяется, когда векторные представления не влезают в память. Предположим, что наши векторы имеют размерность 128 и мы хотим кодировать их 64 битами (всего 0,5 бита на компоненту), тогда нам придется заниматься квантованием с количеством центроидов, равным $$. Это нетривиальная задача $$, которая также требует огромной обучающей выборки.

Упростим задачу, разбив вектор на $$ частей $$, и по традиции найдем 256 центроидов для каждой из частей. То есть вектор можно переписать как набор индексов центроидов — например $$, а занимает это хозяйство $$ байт.

Такой вид кодирования будем применять к остаточным векторам $$, $$, и тогда $$

2.4. Поиск

А теперь соберем все это в одной схеме.

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

import faiss

index = faiss.index_factory(model.wv.syn0norm.shape[1], 'IVF16384,Flat')
index.verbose = True
train = model.wv.syn0norm[np.random.binomial(1, 1./3, size=model.wv.syn0norm.shape[0]).astype(bool)]
index.train(train)
index.add(model.wv.syn0norm)
index.nprobe = 100
start = time.time()
distances, items = index.search(king_vec, 10)
print(time.time() - start)
print([model.wv.index2word[idx] for idx in items[0]])

Получаем:

    0.0048999786377
    [u'king', u'kings', u'queen', u'monarch', u'crown_prince', u'prince', u'sultan', u'ruler', u'princes', u'Prince_Paras']

2.5. Pros & Cons

+ Поддержка сжатия

+ Малые накладные расходы на хранение центроидов

+ Возможность вычислений на GPU*

– В пять раз медленнее HNSW на CPU

* Мы не смогли быстро завести GPU-реализацию из коробки и решили не тратить время на это.

3. ANNOY

Идея деления пространства плоскостями хорошо реализована в Annoy. Алгоритм прекрасно описан автором в блоге, рекомендую прочесть, если хотите разобраться в деталях. Я попробую коротко изложить суть. В алгоритме мы рекурсивно делим пространство плоскостями, образуя бинарное дерево. В каждом узле дерева хранится вектор, задающий текущую плоскость. При поиске мы начинаем с корня и выбираем дочернюю ноду на основе положения запроса относительно плоскости. Так мы спускаемся к листовым элементам дерева, в которых хранятся векторы, оказавшиеся по одну сторону группы плоскостей (это небольшой кусочек пространства), они с высокой вероятностью окажутся искомыми ближайшими соседями. Посмотрим на достоинства и недостатки Annoy по сравнению с другими алгоритмами.

3.1. Pros & Cons

+ Алгоритм просто понять

– Он требует много памяти

– Проигрывает в скорости работы

Сравнение алгоритмов

У каждого из алгоритмов есть набор параметров, будь то максимальное количество друзей для вершины (в NSW, HNSW) или количество центроидов (в FAISS). Эти параметры влияют на объем потребляемой памяти, качество и скорость поиска. Автор Annoy реализовал тесты для группы ANN алгоритмов в репозитории ann-benchmarks на разных параметрах. В них оценивается точность поиска десяти ближайших соседей в датасетах, полученных при помощи алгоритмов GloVe и SIFT.

GloVe — это еще один способ получить векторные представления слов, он превосходит word2vec по всем показателям при обучении на корпусе одного размера. Датасет составлен из 1,2 миллиона векторных представлений слов, обученных на 2 миллиардах твитов. SIFT — старый алгоритм получения ключевых точек изображения и их векторных представлений, устойчивых к трансформациям. Он использовался для распознавания объектов, и важной частью этого распознавания был поиск похожих векторных представлений. Есть несколько вариаций датасетов, нас интересует SIFT 1M, содержащий миллион векторов.

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

Видно, что HNSW уверенно лидирует. Однако на графиках нет FAISS. Facebook самостоятельно сравнил HNSW и FAISS в разных конфигурациях, результаты приведены в таблице.

В таблице методы FAISS без сжатия, в частности IVF16384,Flat. Значит, используется IVFADC c 16 384 центроидами. Расходы памяти указаны для случая с миллионом векторов размерности 128 в float32. HNSW в пять раз быстрее при вычислениях на CPU, но на хранение ребер графа ($$) требуется больше памяти, чем на центроиды ($$).

4. Заключение

Мы рассмотрели ряд алгоритмов, применяемых для быстрого поиска ближайших соседей. Annoy проиграл и по памяти, и по скорости работы, но идея хороша и может помочь в решении смежных задач. Например, удобный для чистки датасета алгоритм поиска аномалий isolation forest очень похож по своей задумке. FAISS — отличное решение при ограничениях по памяти, с ним вполне можно уложить миллиард векторных представлений в 60 Гбайт RAM, используя IVF16384, PQ64. Однако если память не узкое место, то стоит выбрать HNSW.

P. S. Самыми интересными оказались публикации об алгоритмах в FAISS. Там, к примеру, можно прочесть об оптимизации под GPU, об улучшенном методе квантования (Optimized Product Quantization) и о более хитром способе построении индекса (inverted multi-index).

P. P. S. Для себя мы выбрали HNSW.

5. Литература

• Approximate nearest neighbor algorithm based on navigable small world graphs
• Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs
• Product quantization for nearest neighbor search
• SEARCHING IN ONE BILLION VECTORS: RE-RANK WITH SOURCE CODING
• GloVe: Global Vectors for Word Representation
• Object Recognition from Local Scale-Invariant Features
• Isolation Forest
• Billion-scale similarity search with GPUs
• Optimized Product Quantization
• The inverted multi-index

Пример

import requests 


create_jon_snow_user = requests.post(
    'https://gameofthrones.com/api/v1/user', 
    params={
        'id': 7,
        'name': 'Jon',
        'surname': 'Snow',
    }
)

get_jon_snow_user = requests.get(
    'https://gameofthrones.com/api/v1/user', params={'id': 7}
)

create_jon_snow_castle = requests.post(
    'https://gameofthrones.com/api/v1/user/castle', 
    params={
        'id': 7,
        'castle': 'Winterfell',
    }
)

from gameofthrones_api import gameofthrones_api_client as got_api_client


create_jon_snow_user = got_api_alient.user.create({
    'id': 7,
    'name': 'Jon',
    'surname': 'Snow'
})

get_jon_snow_user = got_api_alient.user.get({'id': 7})

create_jon_snow_castle = got_api_alient.user.castle.create({
    'id': 7,
    'castle': 'Winterfell',
})

Как это работает

pypi:
  username: dmytrostriletskyi
  password: d843rnd3

acg:
  name: gameofthronesapi
  version: 0.1.5

  api: https://gameofthrones.com/api/v1

  services:
    user:
      url: /user
      endpoints: create:post, get:get

    user.castle:
      url: /user/castle
      endpoints: create:post

• в .acg.yml доступно поле api, где нужно указать корень (адрес), от которого уже идут ответвления на различные запросы. Например, корнем является ваша API myapi.com, а ответвлением /users/all.
• в services уже на любой вкус можно указать сколько угодно «путей», все они заканчиваются эндпоинтами (endpoints) и имеют в наличие адрес, к которому они «принадлежат».
• endpoints в пункте acg в конфигурациях — это название метода и его тип запроса HTTP. Пример из конфигураций выше: user.castle.create, post-запрос, на адрес /user/castle. Наличие endpoint полезно, когда один путь поддерживает много типов запроса (get, post, delete для одного адреса). Например, apple.iphone.ten.account может поддерживать endpoints get (тип запроса get), delete (delete), create (post), modify (put) к адресу /apple/iphone/ten/account.
• Множество эндпоинтов к одному адресу записываются в одну строку к пункту endpoints через запятую — get:get, delete:delete, create:post, modify:put (пример).

Установка acg

$ pip install acg

$ pip3 install acg

$ python setup.py install

Команда acg

$ acg

Как установить и использовать свой клиент

from telegrambotapi import telegrambotapi_client

• Цифровая трансформация. Получите новые впечатляющие бизнес-результаты, используя адаптивное ПО, Интернет вещей (IoT) и аналитику Big Data.
  
• Трансформация ИТ. Познакомьтесь с новейшими платформами, конвергентными системами и облачными технологиями на примере Microsoft Azure и SOHO-решений.
  
• Трансформация рабочих мест. Обеспечьте своих сотрудников современными технологиями для работы в офисе и за его пределами.
  
• Трансформация систем безопасности. Узнайте о новых способах борьбы с ИТ-угрозами, защите и восстановлении инфраструктуры.
  

Как работает SSR в React 15

// используем Express
import { renderToString } from "react-dom/server"
import MyPage from "./MyPage"
app.get("/", (req, res) => {
  res.write("");
  res.write("
");  
  res.write(renderToString());
  res.write("
");
  res.end();
});

import { render } from "react-dom"
import MyPage from "./MyPage"
render(, document.getElementById("content"));

Обратная совместимость React 16

Метод render() становится методом hydrate()

import { hydrate } from "react-dom"
import MyPage from "./MyPage"
hydrate(, document.getElementById("content"))

React 16 может работать с массивами, строками и числами

class MyArrayComponent extends React.Component {
  render() {
    return [
      
first element
, 
      
second element
    ];
  }
}
class MyStringComponent extends React.Component {
  render() {
    return "hey there";
  }
}
class MyNumberComponent extends React.Component {
  render() {
    return 2;
  }
}

res.write(renderToString([
      
first element
, 
      
second element
    ]));
// Не вполне ясно, зачем так делать, но это работает!
res.write(renderToString("hey there"));
res.write(renderToString(2));

React 16 генерирует более эффективный HTML

renderToString(
  

    This is some server-generated HTML.
  
);

  This is some 
  server-generated
   
  HTML.

  This is some server-generated HTML.

React 16 поддерживает произвольные атрибуты DOM

SSR в React 16 не поддерживает обработчики ошибок и порталы

React 16 производит менее строгую проверку на стороне клиента

React 16 не нужно компилировать для улучшения производительности

if (process.env.NODE_ENV !== "production") {
  // что-то тут проверить и выдать полезное
  // предупреждение для разработчика.
}

React 16 отличается более высокой производительностью

React 16 поддерживает потоковую передачу данных

// используем Express
import { renderToNodeStream } from "react-dom/server"
import MyPage from "./MyPage"
app.get("/", (req, res) => {
  res.write("");
  res.write("
"); 
  const stream = renderToNodeStream();
  stream.pipe(res, { end: false });
  stream.on('end', () => {
    res.write("
");
    res.end();
  });
});

Подводные камни потокового рендеринга

Каким вы видите будущее компьютерного зрения? Наблюдая за развитием машинного обучения, какие перспективы вы видите?

• everything learnable, minimum handcrafting
• новое – это хорошо забытое старое.

1. попытаться применять deep learning для новых задач, все более и более сложных,
2. в-частности, применить к задачам, где трудно собрать огромные тренировочные базы.

Нет ли планов добавить в OpenCV возможность обрабатывать 3D (volumetric) изображения? Работаю с томографическими изображениями размера порядка 4000х4000х4000. Существующие open-source библиотеки для 3D, мягко говоря, бедноваты и медленноваты по сравнению с OpenCV.

Видеокамера висит на мосту, под которым идет поток автомобилей. Для видеокамеры установлено отличное освещение, в нормальную погоду ночью можно даже лица водителей рассматривать. Когда же начинается метель, снимки получаются почти белыми (из-за большого количества мелких движущихся объектов, снежинок). Можете подсказать, как побороть такой «шум»?

Какой язык лучше всего подходит для экспериментов с CV? Стоит ли разбираться с Erlang для этого?
Есть ли канонический набор книг или цикл статей, для быстрого старта с техническим зрением? Есть ли с кем пообщаться?

1. C++ с хорошей средой разработки,
2. Python

• awesome-rnn
• awesome-deep-vision
• awesome-computer-vision
• awesome-random-forest
• neural-network-papers
• awesome-tensorflow

Как начать свою карьеру в области CV, если ты не имеешь в нем опыта? Где набраться опыта решения реальных задач и стажа в этой области, который так любят HRы?

Немного TL;DR который является предысторией возникновения вопроса

Я отучился в ВУЗе, где не было такого направления и, естественно, пошел работать в другую область (программная инженерия, автоматизация). Будь у меня возможность и понимание, насколько потенциально круто работать в области CV, я бы поступил на него пусть даже в другой ВУЗ, но, увы, я узнал о нем слишком поздно. Переучиваться на второе высшее уже как-то непозволительно долго.

По долгу службы попалась задача детектирования с помощью Python+OpenCV, решил кое-как через template match (благо предметная область позволяла). Было весело, ново и вообще всем понравилось, особенно мне.

Начал изучать возможность самообучения, прошел курс Introduction to Computer Vision (Udacity-Georgia Tech) и начал практические от PyImageSearch.
Параллельно смотрел вакансии на Upwork и PyImageSearch Jobs, Fiverr и расстраивался, так как знаний явно не хватает для решения реальных задач (например, почти везде мешают light/shadow/angle conditions). Не уверен, что даже полное прохождение, скажем, Guru курса от PyImageSearch поможет найти достойную работу, ибо примеры уж очень «идеальные» и редко работают, как задумывались в реальных условиях.

На биржах типа Fiverr, Upwork, PyImageJobs большая конкуренция и требуется выполнение задач очень быстро. А хочется чего-то с небольшим порогом вхождения и взлетной learning-curve. Про удаленную работу вообще молчу. Плюс, везде еще хотят deep/machine learning вдогонку.

Бросать основную работу ради того, чтобы не найти себе работу в CV, как-то не хочется. Но и опускать руки тоже. Это же крутая и интересная область, чтобы развиваться профессионально, как ни смотри).

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

OpenCV превратился в склад алгоритмов из разных областей (вычислительная геометрия, обработка сигнала, machine learning и т.д.). А между тем, есть более продвинутые библиотеки по той же вычислительной геометрии (не говоря о нейросетях). Выходит, смысл OpenCV только в одном — все зависимости в одном флаконе?

Почему так мало готовых решений? Например, если я новичок в CV, и хочу искать черный квадрат на белом фоне, то открыв доку OpenCV, я утону в ней. Вместо этого я бы хотел полистать список наиболее типичных и простых задач и выбрать, или скомбинировать. Т.е. в OpenCV практически нет декларативного подхода.

Расскажите, пожалуйста, об наиболее интересных проектах с оригинальным решением — OpenCV с микрокомпьютерами (Raspberry, ASUS ...)

Есть ли небольшие платы (уровня Raspberry Pi с процессором, заточенным под видеообработку OpenCV) и видеокамерой, подключенной напрямую к микропроцессору (микроконтроллеру) без всяких посредников в виде USB и его больших задержек? Чтобы можно было бы взять его и на коленке быстро сделать устройство для подсчета ворон на грядке или устройство для слежения за объектом (простейшая обработка изображения + реакция с минимальными задержками на раздражители).

Мой собственный опыт

Крайний раз пытался решать подобную задачу года 4 назад. 1) Все популярные доступные платы разработки не тянули обработку хорошего видео потока быстрее чем 1-2 раза в секунду, задействовать DSP без программирования на низких уровнях было нереально, да и достать контроллер с мощным хорошим документированным DSP и софтом у нему было непросто 2) все камеры во всех примерах цепляются по USB, соответственно на пустом месте огромные задержки + софтовая обработка камеры маломощным основным процессором. На распознавание процессорного времени уже почти не остается.

Есть ли готовые дистрибутивы и софт «из коробки» под такие железки, с которым можно сразу начать работать, не допиливая неделями?

Обобщая, задам вопрос так: можно ли в 2017-2018 году студенту 2-3 курса IT-специальности с базовыми навыками программирования, уложившись в 10000 руб., достать железку уровня 2-3 летнего телефона, на которой за 2-4 недели изучения OpenCV и написания кода создать простейшее устройство: камеру на мотоподвесе с парой осей движения, которая будет висеть на балконе и следить за движением любимой собаки во дворе?

• как обрабатывать движения/колыхания самой камеры, какое поведение ожидается в темное время суток, туман, дождь, снег, как обрабатывать разные времена года,
• как обрабатывать разные условия освещения – пасмурно, солнце в зените, солнце на восходе-закате с большими тенями,
• как система должна обрабатывать появление другого объекта в области видимости (машины, человека, кошки, другой собаки, другой собаки такой же породы),
• какое качество считается допустимым (система выдает вам ложные сообщения о пропаже собаки каждые 5 минут, система сообщает о пропаже собаки через сутки после ее пропажи)
• и т.д.

Не работает функция model = cv2.ANN_MLP() на питоне.

Код функции

import cv2
import numpy as np
import math
class NeuralNetwork(object):

def __init__(self):
self.model = cv2.ANN_MLP()

def create(self):
layer_size = np.int32([38400, 32, 4])
self.model.create(layer_size)
self.model.load('mlp_xml/mlp.xml')

def predict(self, samples):
ret, resp = self.model.predict(samples)
return resp.argmax(-1)

model = NeuralNetwork()
model.create()

Ошибка AttributeError: 'module' object has no attribute 'ANN_MLP'

Как OpenCV будет развиваться в сторону нейросетей, машинного обучения? Где есть простые примеры для начинающих по машинному обучению? Желательно на русском.

Каким алгоритмом лучше искать относительно сложные логотипы на фотографии — например, логотипы различных маркировок, где обычно присутствует и текст, и рисунки, и все вписано в форму? Пробовал через Haar Cascade — этот алгоритм хорошо ищет цельные куски, а такой сложный многосоставной объект, как логотип, не находит. Попробовал MatchTemplate — не ищет, если происходит минимальное несовпадение — уменьшение, поворот относительно исходной картинки. Не подскажете, в каком направлении искать?

Можно ли с помощью компьютерного зрения смоделировать аналоги зрения различных биологических организмов, например, животных и насекомых и создать приложение, дающее возможность увидеть мир глазами других существ?

Если пойти еще дальше, то можно создать множество моделей зрения различных живых существ, пропустить всё это многообразие через нейросеть и создать нечто новое? Возможен ли синтез зрения различных биологических систем?

Почему нельзя умножить матрицу на вектор (cv::Vec_) в OpenCV, но при этом можно умножить на точку? (cv::Point_) Получается, что проще манипулировать с точками тогда, когда математически это не точки, а вектора. Например, направление линии легче хранить как точку, а не как вектор — меньше преобразований типов в цепочке операций.

Почему до сих пор в OpenCV нет ни одной реализации Hough Transform, которая возвращала бы аккумулятор. Ведь иногда надо найти, скажем, единственный максимум! Разрешат ли держатели проекта добавить новую реализацию, которая возвращала бы аккумулятор?

Пробует ли Intel создавать аппаратные нейросети для обработки изображений и есть ли результаты?

Пользуюсь OpenCV не первый год, но столкнулся с такой интересной штуковиной. Есть камера, которая передает сигнал, и есть телеметрия, которая принимает сигнал, а еще есть тюнер, который декодирует сигнал в видео на компьютер. Так вот программы по захвату изображения работают на ура, но библиотека OpenCV при попытке вывести на экран изображение выдает черный экран, а при попытке выйти из программы, вываливается синий экран) ВОПРОС Почему это происходит?

Характеристики устройств: TV-тюнер EasyCap USB 2.0, Приемник FPV видеосигнала 5.8ГГц RC832, FPV камера с передатчиком 5.8ГГц 1000TVL.

Видео ошибки

Есть ли смысл в современных реалиях в программах видеоанализа, основанных на фичах, спроектированных человеком, или лучше не морочиться и сразу тренировать нейронную сеть?

Я использовал версию OpenCV 3.1.0, пользовался cv2.HOGDescriptor() и .setSVMDetector(cv2.HOGDescriptor_getDefaultPeopleDetector()), остался под хорошим впечатлением. Но я хочу уменьшить количество ложных срабатываний и поэтому хочу узнать, какой набор данных использовался для обучения SVM классификатора и могу ли я получить доступ к этому набору? Также хотелось бы узнать, планируется ли создание модулей OpenCV для распознавания различных объектов на базе YOLO или Semantic Segmentation?

«Посоветуйте, как можно распознать штамп слева в изображении справа? Штампы не идентичны, но есть общие элементы.



Пробовал find_obj.py из примеров opencv, но в данной ситуации этот пример не помогает.