Hash Learning для больших данных: вводное руководство - Введение

задняя часть база данных регулярное выражение Нейронные сети

Переведено сLearning to Hash for Big Data: A Tutorial.

Введение

Поиск ближайшего соседа в больших данных

Поиск ближайшего соседа: при заданной точке запроса q вернуть набор точек в базе данных, наиболее близких (наиболее похожих) к q.

  • Facebook: 750 миллионов пользователей
  • Flickr: 60 миллионов фотографий
  • Wal-Mart: 267 миллионов товаров в день, хранилище данных 4PB
  • Sloan Digital Sky Survery: Телескоп в Нью-Мексико получает 200 ГБ данных изображений в день.

Задача поиска ближайшего соседа в больших данных:

  • проклятие размерности
  • место хранения
  • скорость запроса

Хеширование с сохранением подобия

Сделайте соответствующие хэш-коды несвязанных изображений как можно более разными, а хэш-коды похожих изображений — как можно более одинаковыми.

Требования к пространству для хранения снижены.

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

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

Два этапа обучения хеш-функции

  • первый сорт
    • Стадия проекции (уменьшение размеров)
      • Проектирование с помощью проекционной функции с действительным знаком
      • Для точки x каждое проецируемое измерение i связано с проекционной функцией с действительным знаком fi (x) (например, fi (x) = Wi ^ T * x
    • Стадия квантования
      • Превратить реальный в двоичный
      • Существенная разница между метрическим обучением и обучением хешированию
  • Категория 2
    • Этап обучения двоичному кодированию
    • Этап обучения хэш-функции

независимый от данных подход

Определение хеш-функции не зависит от обучающего набора данных.

  • Хеширование с учетом местоположения (LSH) Хеширование с учетом местоположения (Gionis et al., 1999; Andoni and Indyk, 2008)
    • и его расширения (Датар и др., 2004; Кулис и Грауман, 2009; Кулис и др., 2009)
  • SIKH: хеширование ядра с инвариантным сдвигом (SIKH) (Рагинский и Лазебник, 2009 г.)
  • MinHash (Broder et al., 1998)
    • и его расширения (Ли и Кониг, 2011)

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

Методы корреляции данных

Хеш-функция изучается из данного обучающего набора данных.

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

Новаторские документы: (Салахутдинов и Хинтон, 2007, 2009; Торральба и др., 2008; Вайс и др., 2008)

Два вида:

  • одномодальный
    • Контролируемые методы: при наличии некоторой контролируемой (семантической) информации, такой как парные метки s_ij, точечные метки yi или триплетные метки (xi, xj, xk).
    • Неконтролируемые методы
  • мультимодальный
    • контролируемый подход
    • Неконтролируемые методы

Унимодальные неконтролируемые методы

Метки, обозначающие класс тренировочных очков, отсутствуют.

  • PCAH: анализ основных компонентов
  • SH: рассчитывается на графике схожести данных.собственные функции (Weiss et al., 2008)
  • AGH: хеширование на основе графа привязки (Liu et al., 2011)
  • ITQ: сМатрица ортогонального вращенияулучшить начальную проекционную матрицу, полученную с помощью PCA (Gong and Lazebnik, 2011)
  • Изохэш: использоватьМатрица ортогонального вращениявносить изменения в разные стороныизотропный(Равный) (Конг и Ли, 2012b)
  • DGH: прямое изучение дискретных двоичных кодов (Liu et al., 2014)
  • SGH: Масштабируемое хэширование графов с использованием преобразований функций (Цзян и Ли, 2015 г.)

Методы унимодального надзора (полуконтролируемого)

Имеет метки классов или попарные ограничения.

  • SSH (SPLH): полуконтролируемое хэширование с использованием как помеченных, так и неразмеченных данных (Wang et al., 2010a,b).
  • MLH: хеширование с минимальными потерями на основе скрытой структурной платформы SVM (Нороузи и Флит, 2011 г.)
  • LDAHash: хеширование на основе линейного дискриминантного анализа (Strecha et al., 2012)
  • KSH: контролируемое хеширование на основе ядра (Liu et al., 2012)
  • LFH: Контролируемое хэширование для моделей скрытых факторов (Чжан и др., 2014 г.)
  • FastH: контролируемое хэширование с использованием разрезов графов и деревьев решений (Lin et al., 2014)
  • SDH: контролируемое дискретное хеширование с использованием точечных меток (Shen et al., 2015)
  • COSDISH: масштабируемое дискретное хеширование с использованием парного контроля

Подход на основе сортировки

Информация о контроле — это метки заказа, такие как тройки (xi, xj, xk).

  • HDML: обучение по метрике расстояния Хэмминга (Norouzi et al., 2012)
  • OPH: порядок сохранения хэша, приблизительный поиск ближайшего соседа (Wang et al., 2013b)
  • RSH: изучение хэш-кодов с контролем списка (Wang et al., 2013a)
  • RPH: сортировка с сохранением хэша, быстрый поиск по сходству (Wang et al., 2015)

мультимедийный метод

  • Мульти-источник хэша (мульти-источник)
  • Кросс-модальное хеширование
многосторонний подход
  • Цель состоит в том, чтобы использовать вспомогательные представления, чтобы лучше изучить кодирование, чем одномодальное хеширование.
  • Предположим, запрос предоставляет все представления
  • MFH: Многофункциональное хэширование (Song et al., 2011)
  • CH: Compound Hash (Чжан и др., 2011 г.)
межмедийный подход

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

  • CVH: перекрестное хеширование (Кумар и Удупа, 2011 г.)
  • MLBE: Мультимодальное неявное двоичное встраивание (Чжэнь и Йенг, 2012a)
  • CRH: совместно регулируемый хеш (Чжэнь и Йенг, 2012b)
  • IMH: промежуточное хеширование (Song et al., 2013)
  • RaHH: гетерогенное хеширование с учетом отношений (Ou et al., 2013)
  • SCM: максимизация семантической корреляции (Чжан и Ли, 2014 г.)
  • CMFH: Коллективное матричное факторизационное хеширование (Ding et al., 2014)
  • QCH: квантизация хеширования корреляций (Wu et al., 2015)
  • SePH: хеширование с сохранением семантики (Lin et al., 2015b)

глубокий хэш

Хэш с использованием глубокого обучения.

  • CNNH: контролируемое хеширование с помощью обучения представлению изображений (Xia et al., 2014)
  • NINH: одновременное изучение функций и хеш-кодирование с помощью глубоких нейронных сетей (Лай и др., 2015 г.)
  • DSRH: хэширование на основе глубокого семантического ранжирования (Чжао и др., 2015 г.)
  • DRSCH: масштабируемое по битам глубокое хеширование (Чжан и др., 2015 г.)
  • DH: Глубокое хеширование, обучение сжатому двоичному коду (Лионг и др., 2015 г.)
  • Изучение глубокого хеширования с помощью двоичных кодов (Lin et al., 2015a)
  • DPSH: основанное на обучении хэширование с глубоким наблюдением и использованием парных меток (Li et al., 2015)

количественно

Стадия квантования так же важна, как и стадия проецирования.

  • DBQ: двухбитовое квантование (Конг и Ли, 2012a)
  • MQ: манхэттенское квантование (Конг и др., 2012 г.)
  • VBQ: вариабельный квантование квантования битов (Moran et al., 2013)
Категории