Java IR Utils

Я создал на Google Code проект Java IR Utils, куда буду выкладывать всякие полезности вроде SparseArrayList.

Анонимный доступ:

svn checkout http://java-ir-utils.googlecode.com/svn/trunk/ java-ir-utils

Если есть желание участвовать в проекте, пишите.

Контроль над поисковой выдачей

Nigma первой в рунете сделала удивительно полезную вещь: возможность управлять результатами поиска в зависимости от цели запроса. Не секрет, что большинство интернет-магазинов очень хорошо оптимизированы и занимают первые места в выдаче, хотя нам очень часто нужна только информация о товаре, обзоры, отзывы с форумов. Теперь при поиске в Нигме есть возможность отключать целые кластеры результатов, например "интернет-магазины".

Стоит отметить, что Yahoo запустил подобную поиск больше года назад и он как раз целиком направлен на исключение (или включение) магазинов из результатов.

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

Как хранить double

Задался вчера интересным вопросом, как экономнее всего хранить числа с плавающей точкой. Понятно, что выиграют примитивы, интересно было сравнить double[] (массив из одного элемента) и Double. Результат для меня был неожиданный: double/Double/double[] = 1/2/3. Получается, что в контейнерах эффективнее хранить класс-обертку, а не массив. Если же можно использовать массивы вместо контейнеров, лучше использовать массивы: выигрыш в памяти составит более 100%!

SparseArrayList, новая версия

Выложил новую версию SparseArrayList. Добавил возможность итерации по паре индекс-значение в порядке возрастания индекса. Очень удобно, когда надо слить несколько списков в один.

Заодно провел несколько измерений расхода памяти и скорости доступа по сравнению с HashMap и TreeMap.

• SparseArrayList позволяет сэкономить около 5% памяти по сравнению с HashMap
• Скорость произвольного доступа к элементам выше у HashMap при маленьком числе элементов (100-200) и становится одинаковой при большом числе (>5000)
• Скорость последовательного (по возрастанию индекса) доступа у SparseArrayList выше чем у TreeMap более чем в 2 раза
  

SparseArrayList

Бывают такие ситуации, когда стандартный HashMap слишком медленный и затратный по памяти, а возможностей SparseVector из MTJ не хватает, поскольку надо хранить произвольные объекты. Для таких случаев я написал простой класс SparseArrayList, который практически идентичен SparseVector за вычетом, собственно, векторных операций. Плюс для хранения данных используется не массив, а ArrayList, и размер контейнера не ограничивается в конструкторе.

В архиве лежит еще и класс Arrays (дополнение к стандартному) из MTJ. В библиотеке он package-local, для реализации SparseArrayList пришлось сделать его public.

Multiword Features

В ситуациях когда различиях между категориями проявляются не на уровне различных слов, а на уровне сочетаний этих слов, классические классификаторы Байеса могут показывать не очень удовлетворительные результаты. Справиться с этой проблемой можно используя шинглы (shingles) или multiword features.

В общем случае, шинглы — это уникальные последовательности символов одинаковой длины выделенные из документа. Для задач классификации можно рассматривать последовательности не символов, а слов. Например, для документа "a rose is a rose is a rose" шинглами длиной в четыре слова будут: { (a,rose,is,a), (rose,is,a,rose), (is,a,rose,is) }. Построить все шинглы для документа можно за O(w(n-w)), где w — длина шингла. Дальше шинглы используются как обычные слова в классификаторе Байеса, за счет чего заметно вырастает точность, особенно когда мы работаем с иерархической структурой категорий.

К сожалению шинглы нам не помогут в случае, когда слова из характерных сочетаний идут в документах не подряд, а на различном расстоянии друг от друга. В таком случае можно использовать обобщение идеи шинглов: multiword features. Собственно, что это такое уже понятно, весь вопрос в том, как эффективно эффективно найти характерные для категории multiword features. Действительно, наивный алгоритм, который находит все возможные сочетания слов, скорее всего просто не влезет в память. Очевидно, что нам нужны не все возможные сочетания слов, а только наиболее характерные для категории, то есть которые встречаются, например, как минимум в 10% документов. Это позволяет нам последовательно вычислять корреляцию для очередного набора слов и хранить в памяти только удовлетворяющие условию. Тем не менее, временная сложность такого алгоритма все равно будет O(mk), где m — число слов в категории, k — число слов в наборе. Очевидно, что вычислять наборы более чем из двух слов неэффективно, да и, как правило, это не даст большого выигрыша в точности.

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

1. Каждое слово представляется вектором, элементы которого равны нулю или единице, в зависимости от присутствия слова в документе с соответствующим номером.
2. Этот вектор хранится в виде long[], длина массива равна [n / sizeof(long)] + 1, где n — число документов.
3. Вычисление корреляции между двумя документами сводится к последовательному побитовому умножению элементов двух массивов и вычислению числа единиц в результате.

Хороший практический результат на многих задачах может дать совместное использование шинглов длиной в 3-5 слов и 2-word features.

Eigenvalue Decomposition

После более детального исследования оказалось, что других хороших библиотек кроме Matrix Toolkits for Java для работы с матрицами и векторами на Java попросту нет. Ни по набору функций, ни по производительности. MTJ построена поверх BLAS/LAPACK и может использовать оптимизированные под определенную платформу реализации этих библиотек (инструкции для Linux и Windows).

Достаточно часто в задачах IR требуется найти собственные вектора какой-либо матрицы nxn (eigenvalue decomposition, EVD), причем обычно нам нужны только k << n векторов соответствующих k наибольшим собственным числам матрицы. Но существующие в MTJ классы для вычисления EVD находят сразу все вектора, что приводит к совершенно неоправданным временным затратам. Для решения этой задачи я немного модифицировал класс SymmDenseEVD, который находит собственные вектора у симметричной матрицы. Теперь в конструкторе можно задать какие собственные числа (по убыванию) и соответствующие им вектора нам нужны.

Binaries: mtj.jar
Source code: mtj-src.tar.gz