Monday, June 9, 2014

Low-level testing your Lucene TokenFilters

On the recent Berlin buzzwords conference talk on Apache Lucene 4 Robert Muir mentioned the Lucene's internal testing library. This library is essentially the collection of classes and methods that form the test bed for Lucene committers. But, as a matter of fact, the same library can be perfectly used in your own code. David Weiss has talked about randomized testing with Lucene, which is not the focus of this post but is really a great way of running your usual static tests with randomization.

This post will show a few code snippets, that illustrate the usage of the Lucene test library for verifying the consistency of your custom TokenFilters on lower level, than your might used to.




(Credits: http://blog.csdn.net/caoxu1987728/article/details/3294145 
I'm putting this fancy term graph to prove, that posts with images are opened more often, than those without. Ok, it has relevant parts too: in particular we are looking into creating our own TokenFilter in parallel to StopFilter, LowerCaseFilter, StandardFilter and PorterStemFilter.).


In the naming convention spirit of the previous post, where custom classes started with GroundShaking prefix, let's create our own MindBlowingTokenFilter class. For the sake of illustration, our token filter will take each term from the term stream, add "mindblowing" suffix to it and store in the stream as a new term. This class will be a basis for writing unit-tests.

package com.dmitrykan.blogspot;

import org.apache.lucene.analysis.TokenFilter;
import org.apache.lucene.analysis.TokenStream;
import org.apache.lucene.analysis.tokenattributes.CharTermAttribute;
import org.apache.lucene.analysis.tokenattributes.PositionIncrementAttribute;
import org.apache.lucene.analysis.tokenattributes.PositionLengthAttribute;

import java.io.IOException;

/**
 * Created by dmitry on 6/9/14.
 */
public final class MindBlowingTokenFilter extends TokenFilter {

    private final CharTermAttribute termAtt;
    private final PositionIncrementAttribute posAtt;
    // dummy thing, is needed for complying with BaseTokenStreamTestCase assertions
    private PositionLengthAttribute posLenAtt; // don't remove this, otherwise the low-level test will fail

    private State save;

    public static final String MIND_BLOWING_SUFFIX = "mindblowing";

    /**
     * Construct a token stream filtering the given input.
     *
     * @param input
     */
    protected MindBlowingTokenFilter(TokenStream input) {
        super(input);
        this.termAtt = addAttribute(CharTermAttribute.class);
        this.posAtt = addAttribute(PositionIncrementAttribute.class);
        this.posLenAtt = addAttribute(PositionLengthAttribute.class);
    }

    @Override
    public boolean incrementToken() throws IOException {
        if( save != null ) {
            restoreState(save);
            save = null;
            return true;
        }

        if (input.incrementToken()) {
            // pass through zero-length terms
            int oldLen = termAtt.length();
            if (oldLen == 0) return true;
            int origOffset = posAtt.getPositionIncrement();

            // save original state
            posAtt.setPositionIncrement(0);
            save = captureState();

            //char[] origBuffer = termAtt.buffer();

            char [] buffer = termAtt.resizeBuffer(oldLen + MIND_BLOWING_SUFFIX.length());

            for (int i = 0; i < MIND_BLOWING_SUFFIX.length(); i++) {
                buffer[oldLen + i] = MIND_BLOWING_SUFFIX.charAt(i);
            }

            posAtt.setPositionIncrement(origOffset);
            termAtt.copyBuffer(buffer, 0, oldLen + MIND_BLOWING_SUFFIX.length());

            return true;
        }
        return false;
    }
}

The next thing we would like to do is to write a Lucene-level test suite for this class. We will extend it from BaseTokenStreamTestCase, not standard TestCase or other class from a testing framework you might have used to deal with. The reason being we'd like to utilize the internal Lucene's test functionality, that lets you access and cross check the lower-level items, like term position increments, position lengths, position start and end offsets etc.

About the same information you can see with Apache Solr's analysis page, if you enable verbose mode. While the analysis page is good to visually debug your code, the unit test is meant to run for you every time you change and build you code. If you decide to first visually examine the term positions, start and end offsets with Solr, you'll need to wrap the token filter into factory and register it in the schema on your field type. The factory code:

package com.dmitrykan.blogspot;

import org.apache.lucene.analysis.TokenStream;
import org.apache.lucene.analysis.util.TokenFilterFactory;

import java.util.Map;

/**
 * Created by dmitry on 6/9/14.
 */
public class MindBlowingTokenFilterFactory extends TokenFilterFactory {
    public MindBlowingTokenFilterFactory(Map args) {
        super(args);
    }

    public MindBlowingTokenFilter create(TokenStream input) {
        return new MindBlowingTokenFilter(input);
    }

}

Here is the test class in all its glory.

package com.dmitrykan.blogspot;

import org.apache.lucene.analysis.Analyzer;
import org.apache.lucene.analysis.BaseTokenStreamTestCase;
import org.apache.lucene.analysis.MockTokenizer;
import org.apache.lucene.analysis.Tokenizer;

import java.io.IOException;
import java.io.Reader;

/**
 * Created by dmitry on 6/9/14.
 */
public class TestMindBlowingTokenFilter extends BaseTokenStreamTestCase {
    private Analyzer analyzer = new Analyzer() {
        @Override
        protected TokenStreamComponents createComponents(String fieldName, Reader reader) {
            Tokenizer source = new MockTokenizer(reader, MockTokenizer.WHITESPACE, true);
            return new TokenStreamComponents(source, new MindBlowingTokenFilter(source));
        }
    };

    public void testPositionIncrementsSingleTerm() throws IOException {

        String output[] = {"queries" + MindBlowingTokenFilter.MIND_BLOWING_SUFFIX, "queries"};
        // the position increment for the first term must be one in this case and of the second must be 0,
        // because the second term is stored in the same position in the token filter stream
        int posIncrements[] = {1, 0};
        // this is dummy stuff, but the test does not run without it
        int posLengths[] = {1, 1};

        assertAnalyzesToPositions(analyzer, "queries", output, posIncrements, posLengths);
    }

    public void testPositionIncrementsTwoTerm() throws IOException {

        String output[] = {"your" + MindBlowingTokenFilter.MIND_BLOWING_SUFFIX, "your", "queries" + MindBlowingTokenFilter.MIND_BLOWING_SUFFIX, "queries"};
        // the position increment for the first term must be one in this case and of the second must be 0,
        // because the second term is stored in the same position in the token filter stream
        int posIncrements[] = {1, 0, 1, 0};
        // this is dummy stuff, but the test does not run without it
        int posLengths[] = {1, 1, 1, 1};

        assertAnalyzesToPositions(analyzer, "your queries", output, posIncrements, posLengths);
    }

    public void testPositionIncrementsFourTerms() throws IOException {

        String output[] = {
                "your" + MindBlowingTokenFilter.MIND_BLOWING_SUFFIX, "your",
                "queries" + MindBlowingTokenFilter.MIND_BLOWING_SUFFIX, "queries",
                "are" + MindBlowingTokenFilter.MIND_BLOWING_SUFFIX, "are",
                "fast" + MindBlowingTokenFilter.MIND_BLOWING_SUFFIX, "fast"};
        // the position increment for the first term must be one in this case and of the second must be 0,
        // because the second term is stored in the same position in the token filter stream
        int posIncrements[] = {
                1, 0,
                1, 0,
                1, 0,
                1, 0};
        // this is dummy stuff, but the test does not run without it
        int posLengths[] = {
                1, 1,
                1, 1,
                1, 1,
                1, 1};

        // position increments are following the 1-0 pattern, because for each next term we insert a new term into
        // the same position (i.e. position increment is 0)
        assertAnalyzesToPositions(analyzer, "your queries are fast", output, posIncrements, posLengths);
    }

    public void testPositionOffsetsFourTerms() throws IOException {

        String output[] = {
                "your" + MindBlowingTokenFilter.MIND_BLOWING_SUFFIX, "your",
                "queries" + MindBlowingTokenFilter.MIND_BLOWING_SUFFIX, "queries",
                "are" + MindBlowingTokenFilter.MIND_BLOWING_SUFFIX, "are",
                "fast" + MindBlowingTokenFilter.MIND_BLOWING_SUFFIX, "fast"};
        // the position increment for the first term must be one in this case and of the second must be 0,
        // because the second term is stored in the same position in the token filter stream
        int startOffsets[] = {
                0, 0,
                5, 5,
                13, 13,
                17, 17};
        // this is dummy stuff, but the test does not run without it
        int endOffsets[] = {
                4, 4,
                12, 12,
                16, 16,
                21, 21};

        assertAnalyzesTo(analyzer, "your queries are fast", output, startOffsets, endOffsets);
    }

}

All tests should pass and yes, the same numbers are present on the Solr's analysis page:



MindBlowingTokenFilter solr analysis page


Happy unit testing with Lucene!

your @dmitrykan

Wednesday, May 28, 2014

Using system disk cache for speeding up the indexing with SOLR

Benchmarking is rather hard subject of software development, especially in a sand-boxed development environments, like JVM with "uncontrolled" garbage collection. Still, there are tasks, that are more IO heavy, like indexing xml files into Apache Solr and this is where you can control more on the system level to do better benchmarking.

So what about batch indexing? There are ways to speed it up purely on SOLR side.

This post shows a possible remedy to speeding up indexing purely on the system level, and assumes linux as the system.

The benchmarking setup that I had is the following:

Apache SOLR 4.3.1
Ubuntu with 16G RAM
Committing via softCommit feature

What I set up to do is to play around the system disk cache. One of the recommendations of speeding up the search is to cat the index files into the cache, using the command:

cat an_index_file > /dev/null

Then the index is read from the disk cache buffers and is faster than reading it cold.

What about bulk indexing xml files into Solr? We could cat the xml files to be indexed into the disk cache and possibly speed up the indexing. The following figures are not exactly statistically significant, nor was the test done on a large amount of xml files, but the figures do show the trend:

With warmed up disk cache:
real    1m27.604s
user    0m2.220s
sys    0m2.860s

After dropping the file cache:
echo 3 | sudo tee /proc/sys/vm/drop_caches

real    1m30.285s
user    0m2.148s
sys    0m3.700s

Again, hot cache:
real    1m27.924s
user    0m2.264s
sys    0m3.068s


Again, after dropping the file cache:
echo 3 | sudo tee /proc/sys/vm/drop_caches

real    1m32.791s
user    0m2.204s
sys    0m3.104s

The figures above are pretty clear, that having the files cached speeds the indexing up by about 3-5 seconds for just 420 xml files.

Coupled with ways of increasing the throughput on the SOLR side this approach could win some more seconds / minutes / hours in the batch indexing.

Monday, May 5, 2014

Making jetty / apache tomcat work on amazon ec2 windows instance

Suppose you have an Amazon ec2 instance running windows OS. One day you decided to run jetty or apache tomcat servlet containers. What does it take to enable these servers to be visible outside your security group, say Internet?

1. Enable the target port in the amazon console like this (supposing it is port 8080):

,

One may think this should be enough. But, that is not so. Not in the case of windows box at least.

Next is:

2. You need to edit the security rules of the windows box such that the inbound connection on port 8080 is allowed:



3. You are done!

Saturday, May 3, 2014

Weka проект-заготовка для задачи распознавания тональности (сентимента)

Это перевод моей предыдущей публикации на английском языке.
 
Интернет полон статьями, заметками, блогами и успешными историями применения машинного обучения (machine learning, ML) для решения практических задач. Кто-то использует его для пользы и просто поднять настроение, как эта картинка:



credits: Customers Who Bought This Item Also Bought PaulsHealthBlog.com, 11.04.2014
 

Правда, человеку, не являющемуся экспертом в этих областях, подчас не так просто подобраться к существующему инструментарию. Есть, безусловно, хорошие и относительно быстрые пути к практическому машинному обучению, например, Python-библиотека scikit. Кстати, этот проект содержит код, написанный в команде SkyNet и иллюстрирующий простоту взаимодействия с библиотекой. Если вы Java разработчик, есть пара хороших инструментов: Weka и Apache Mahout. Обе библиотеки универсальны с точки зрения применимости к конкретной задаче: от рекомендательных систем до классификации текстов. Существует инструментарий и более заточенный под текстовое машинное обучение: Mallet и набор библиотек Stanford. Есть и менее известные библиотеки, как Java-ML.

В этом посте мы сфокусируемся на библиотеке Weka и сделаем проект-заготовку или проект-шаблон для текстового машинного обучения на конкретном примере: задача распознавания тональности или сентимента (sentiment analysis, sentiment detection). Несмотря на всё это, проект полностью рабочий и даже под commercial-friendly лицензией, т.е. при большом желании вы можете даже применить код в своих проектах. Из всего набора в целом подходящих для выбранной задачи алгоритмов Weka мы воспользуемся алгоритмом Multinomial Naive Bayes. В этом посте я почти всегда привожу те же ссылки, что и в английской версии. Но так как перевод задача творческая, позволю себе привести ссылку по теме на отечественный ресурс по машинному обучению.

По моему мнению и опыту взаимодействия с инструментарием машинного обучения, обычно программист находится в поисках решения трёх задач при использовании той или иной ML-библиотеки: настройка алгоритма, тренировка алгоритма и I/O, т.е. сохранение на диск и загрузка с диска натренированной модели в память. Помимо перечисленных сугубо практических аспектов из теоретических, пожалуй, наиболее важным является оценка качества модели. Мы коснёмся этого тоже.

Итак, по порядку.

Настройка алгоритма классификации 

Начнём с задачи распознавания тональности на три класса. 

public class ThreeWayMNBTrainer {
    private NaiveBayesMultinomialText classifier;
    private String modelFile;
    private Instances dataRaw;

    public ThreeWayMNBTrainer(String outputModel) {
        // create the classifier
        classifier = new NaiveBayesMultinomialText();
        // filename for outputting the trained model
        modelFile = outputModel;

        // listing class labels
        ArrayList<attribute> atts = new ArrayList<attribute>(2);
        ArrayList<string> classVal = new ArrayList<string>();
        classVal.add(SentimentClass.ThreeWayClazz.NEGATIVE.name());
        classVal.add(SentimentClass.ThreeWayClazz.POSITIVE.name());
        atts.add(new Attribute("content",(ArrayList<string>)null));
        atts.add(new Attribute("@@class@@",classVal));
        // create the instances data structure
        dataRaw = new Instances("TrainingInstances",atts,10);
    }

}

В приведённом коде происходит следующее:
  • Создаётся объект класса алгоритма классификации (мы любим каламбуры)
  • Приводится список меток целевых классов: NEGATIVE и POSITIVE
  • Создаётся структура данных для хранения пар (объект, метка класса)
Похожим образом, но с бо́льшим количеством выходных меток, создаётся классификатор на 5 классов:

public class FiveWayMNBTrainer {
    private NaiveBayesMultinomialText classifier;
    private String modelFile;
    private Instances dataRaw;

    public FiveWayMNBTrainer(String outputModel) {
        classifier = new NaiveBayesMultinomialText();
        classifier.setLowercaseTokens(true);
        classifier.setUseWordFrequencies(true);

        modelFile = outputModel;

        ArrayList<Attribute> atts = new ArrayList<Attribute>(2);
        ArrayList<String> classVal = new ArrayList<String>();
        classVal.add(SentimentClass.FiveWayClazz.NEGATIVE.name());
        classVal.add(SentimentClass.FiveWayClazz.SOMEWHAT_NEGATIVE.name());
        classVal.add(SentimentClass.FiveWayClazz.NEUTRAL.name());
        classVal.add(SentimentClass.FiveWayClazz.SOMEWHAT_POSITIVE.name());
        classVal.add(SentimentClass.FiveWayClazz.POSITIVE.name());
        atts.add(new Attribute("content",(ArrayList<String>)null));
        atts.add(new Attribute("@@class@@",classVal));

        dataRaw = new Instances("TrainingInstances",atts,10);
    }
}

Тренировка классификатора

Тренировка алгоритма классификации или классификатора заключается в сообщению алгоритму примеров (объект, метка), помещённых в пару (x,y). Объект описывается некоторыми признаками, по набору (или вектору) которых можно качественно отличать объект одного класса от объекта другого класса. Скажем, в задаче классификации объектов-фруктов, к примеру на два класса: апельсины и яблоки, такими признаками могли бы быть: размер, цвет, наличие пупырышек, наличие хвостика. В контексте задачи распознавания тональности вектор признаков может состоять из слов (unigrams) либо пар слов (bigrams). А метками будут названия (либо порядковые номера) классов тональности: NEGATIVE, NEUTRAL или POSITIVE. На основе примеров мы ожидаем, что алгоритм сможет обучиться и обобщиться до уровня предсказания неизвестной метки y' по вектору признаков x'.

Реализуем метод добавления пары (x,y) для классификации тональности на три класса. Будем полагать, что вектором признаков является список слов.

public void addTrainingInstance(SentimentClass.ThreeWayClazz threeWayClazz, String[] words) {
        double[] instanceValue = new double[dataRaw.numAttributes()];
        instanceValue[0] = dataRaw.attribute(0).addStringValue(Join.join(" ", words));
        instanceValue[1] = threeWayClazz.ordinal();
        dataRaw.add(new DenseInstance(1.0, instanceValue));
        dataRaw.setClassIndex(1);
    }

На самом деле в качестве второго параметра мы могли передать в метод и строку вместо массива строк. Но мы намеренно работаем с массивом элементов, чтобы выше в коде была возможность наложить те фильтры, которые мы хотим. Для анализа тональности (а быть может, и для других задач текстового машинного обучения) вполне релевантным фильтром является склеивание слов отрицаний (частиц и тд) с последующим словом: не нравится => не_нравится. Таким образом, признаки нравится и не_нравится образуют разнополярные сущности. Без склейки мы получили бы, что слово нравится может встретиться как в позитивном, так и в негативном контекстах, а значит не несёт нужного сигнала (в отличие от реальности). На следующем шаге, при построении классификатора строка из элементов-строк будет токенизирована и превращена в вектор.

Собственно, тренировка классификатора реализуется в одну строку:

public void trainModel() throws Exception {
        classifier.buildClassifier(dataRaw);
    }

Просто!

I/O (сохранение и загрузка модели)

Вполне распространённым сценарием в области машинного обучения является тренировка модели классификатора в памяти и последующее распознавание / классификация новых объектов. Однако для работы в составе некоторого продукта модель должна поставляться на диске и загружаться в память. Сохранение на диск и загрузка с диска в память натренированной модели в Weka достигается очень просто благодаря тому, что классы алгоритмов классификации реализуют среди множества прочих интерфейс Serializable.

Сохранение натренированной модели:

public void saveModel() throws Exception {
        weka.core.SerializationHelper.write(modelFile, classifier);
    }

Загрузка натренированной модели:
public void loadModel(String _modelFile) throws Exception {
        NaiveBayesMultinomialText classifier = (NaiveBayesMultinomialText) weka.core.SerializationHelper.read(_modelFile);
        this.classifier = classifier;
    }


После загрузки модели с диска займёмся классификацией текстов. Для трёх-классового предсказания реализуем такой метод:

public SentimentClass.ThreeWayClazz classify(String sentence) throws Exception {
        double[] instanceValue = new double[dataRaw.numAttributes()];
        instanceValue[0] = dataRaw.attribute(0).addStringValue(sentence);

        Instance toClassify = new DenseInstance(1.0, instanceValue);
        dataRaw.setClassIndex(1);
        toClassify.setDataset(dataRaw);

        double prediction = this.classifier.classifyInstance(toClassify);

        double distribution[] = this.classifier.distributionForInstance(toClassify);
        if (distribution[0] != distribution[1])
            return SentimentClass.ThreeWayClazz.values()[(int)prediction];
        else
            return SentimentClass.ThreeWayClazz.NEUTRAL;
    }

Обратите внимание на строку номер 12. Как вы помните, мы определили список меток классов для данного случая как: {NEGATIVE, POSITIVE}. Поэтому в принципе наш классификатор должен быть как минимум бинарным. Но! В случае если распределение вероятностей двух данных меток одинаково (по 50%), можно совершенно уверенно полагать, что мы имеем дело с нейтральным классом. Таким образом, мы получаем классификатор на три класса.

Если классификатор построен верно, то следующий юнит-тест должен отработать верно:

@org.junit.Test
    public void testArbitraryTextPositive() throws Exception {
        threeWayMnbTrainer.loadModel(modelFile);
        Assert.assertEquals(SentimentClass.ThreeWayClazz.POSITIVE, threeWayMnbTrainer.classify("I like this weather"));
    }

Для полноты реализуем класс-оболочку, который строит и тренирует классификатор, сохраняет модель на диск и тестирует модель на качество:

public class ThreeWayMNBTrainerRunner {
    public static void main(String[] args) throws Exception {
        KaggleCSVReader kaggleCSVReader = new KaggleCSVReader();
        kaggleCSVReader.readKaggleCSV("kaggle/train.tsv");
        KaggleCSVReader.CSVInstanceThreeWay csvInstanceThreeWay;

        String outputModel = "models/three-way-sentiment-mnb.model";

        ThreeWayMNBTrainer threeWayMNBTrainer = new ThreeWayMNBTrainer(outputModel);

        System.out.println("Adding training instances");
        int addedNum = 0;
        while ((csvInstanceThreeWay = kaggleCSVReader.next()) != null) {
            if (csvInstanceThreeWay.isValidInstance) {
                threeWayMNBTrainer.addTrainingInstance(csvInstanceThreeWay.sentiment, csvInstanceThreeWay.phrase.split("\\s+"));
                addedNum++;
            }
        }

        kaggleCSVReader.close();

        System.out.println("Added " + addedNum + " instances");

        System.out.println("Training and saving Model");
        threeWayMNBTrainer.trainModel();
        threeWayMNBTrainer.saveModel();

        System.out.println("Testing model");
        threeWayMNBTrainer.testModel();
    }
}


Качество модели

Как вы уже догадались, тестирование качества модели тоже довольно просто реализуется с Weka. Вычисление качественных характеристик модели необходимо, например, для того, чтобы проверить, переобучилась ли или недоучилась наша модель. С недоученностью модели интуитивно понятно: мы не нашли оптимального количества признаков классифицируемых объектов, и модель получилась слишком простой. Переобучение означает, что модель слишком подстроилась под примеры, т.е. она не обобщается на реальный мир, являясь излишне сложной.

Существуют разные способы тестирования модели. Один из таких способов заключается в выделении тестовой выборки из тренировочного набора (скажем, одну треть) и прогоне через кросс-валидацию. Т.е. на каждой новой итерации мы берём новую треть тренировочного набора в качестве тестовой выборки и вычисляем уместные для решаемой задачи параметры качества, например, точность / полноту / аккуратность и т.д. В конце такого прогона вычисляем среднее по всем итерациям. Это будет амортизированным качеством модели. Т.е., на практике оно может быть ниже, чем по полному тренировочному набору данных, но ближе к качеству в реальной жизни.

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

public void testModel() throws Exception {
        Evaluation eTest = new Evaluation(dataRaw);
        eTest.evaluateModel(classifier, dataRaw);
        String strSummary = eTest.toSummaryString();
        System.out.println(strSummary);
    }

Данный метод выводит следующие стастистики:

Correctly Classified Instances       28625               83.3455 %
Incorrectly Classified Instances      5720               16.6545 %
Kappa statistic                          0.4643
Mean absolute error                      0.2354
Root mean squared error                  0.3555
Relative absolute error                 71.991  %
Root relative squared error             87.9228 %
Coverage of cases (0.95 level)          97.7697 %
Mean rel. region size (0.95 level)      83.3426 %
Total Number of Instances            34345     

Таким образом, аккуратность модели по всему тренировочному набору 83,35%. Полный проект с кодом можно найти на моём github. Код использует данные с kaggle. Поэтому если вы решите использовать код (либо даже посоревноваться на конкурсе) вам понадобится принять условия участия и скачать данные. Задача реализации полного кода для классификации тональности на 5 классов остаётся читателю. Успехов!

Sunday, April 27, 2014

Weka template project for sentiment classification of an English text

Internet is buzzing about machine learning. Many folks use it for fun and profit

credits: Customers Who Bought This Item Also Bought PaulsHealthBlog.com, 11.04.2014

But! When a non-expert gets around started with these topics in practice, it becomes increasingly difficult to just get going. There are of course quick solutions, like scikit-learn library for Python. If you are a Java developer, there are a few options as well: Weka, Apache Mahout. Both of these are generic enough to be applied to different machine learning problems, including text classification. More tailored libraries and packages for text oriented machine learning in Java are Mallet and Stanford's set of libraries. There are as well some less known machine learning toolkits, like Java-ML.

This post will focus on Weka and will give you a very simple and working template project for classifying sentiment in the English text. Specifically, we will create three way sentiment classifier using Multinomial Naive Bayes algorithm.

In my view, there are three main practical problems, that a programmer seeks to find solutions for using a machine learning library: setting up a classifier algorithm, adding training instances (effectively, training the classifier) and I/O (storing and retrieving a model). Beyond this and of high importance is measuring the quality of the trained model that we will take a look at as well.

Setting up a classifier

As mentioned above, we will use the Multinomial Naive Bayes algorithm. To get going, let's set it up for the three way sentiment classification:


public class ThreeWayMNBTrainer {
    private NaiveBayesMultinomialText classifier;
    private String modelFile;
    private Instances dataRaw;

    public ThreeWayMNBTrainer(String outputModel) {
        // create the classifier
        classifier = new NaiveBayesMultinomialText();
        // filename for outputting the trained model
        modelFile = outputModel;

        // listing class labels
        ArrayList<attribute> atts = new ArrayList<attribute>(2);
        ArrayList<string> classVal = new ArrayList<string>();
        classVal.add(SentimentClass.ThreeWayClazz.NEGATIVE.name());
        classVal.add(SentimentClass.ThreeWayClazz.POSITIVE.name());
        atts.add(new Attribute("content",(ArrayList<string>)null));
        atts.add(new Attribute("@@class@@",classVal));
        // create the instances data structure
        dataRaw = new Instances("TrainingInstances",atts,10);
    }

}

What goes in the above code is:
  • Create the classifier
  • List the target labels: NEGATIVE and POSITIVE
  • Create the instances data structure
In a similar fashion, but with more classes (target labels) we'd set up a five way classifier, using the same algorithm under the hood:

public class FiveWayMNBTrainer {
    private NaiveBayesMultinomialText classifier;
    private String modelFile;
    private Instances dataRaw;

    public FiveWayMNBTrainer(String outputModel) {
        classifier = new NaiveBayesMultinomialText();
        classifier.setLowercaseTokens(true);
        classifier.setUseWordFrequencies(true);

        modelFile = outputModel;

        ArrayList<Attribute> atts = new ArrayList<Attribute>(2);
        ArrayList<String> classVal = new ArrayList<String>();
        classVal.add(SentimentClass.FiveWayClazz.NEGATIVE.name());
        classVal.add(SentimentClass.FiveWayClazz.SOMEWHAT_NEGATIVE.name());
        classVal.add(SentimentClass.FiveWayClazz.NEUTRAL.name());
        classVal.add(SentimentClass.FiveWayClazz.SOMEWHAT_POSITIVE.name());
        classVal.add(SentimentClass.FiveWayClazz.POSITIVE.name());
        atts.add(new Attribute("content",(ArrayList<String>)null));
        atts.add(new Attribute("@@class@@",classVal));

        dataRaw = new Instances("TrainingInstances",atts,10);
    }
}

Adding training instances (training a classifier)

Training the classifier is the process of showing examples to the algorithm. An example usually consists of a set of pairs (x,y), where x is a feature vector and y is a label for this vector. In the context of sentiment analysis specifically, a feature vector can be words (unigrams) in a sentence and a label is sentiment: NEGATIVE, NEUTRAL or POSITIVE in the case of three way sentiment classification. The algorithm is expected to learn from the example set and generalize to predict labels y' for the previously unseen vectors x'.

Engineering the features is both the mix of art and mechanical work, as I've once mentioned. And also finding good classifier options can be a task for statistical analysis with visualization.

Let's implement the method for adding the training instances for three way classification:

public void addTrainingInstance(SentimentClass.ThreeWayClazz threeWayClazz, String[] words) {
        double[] instanceValue = new double[dataRaw.numAttributes()];
        instanceValue[0] = dataRaw.attribute(0).addStringValue(Join.join(" ", words));
        instanceValue[1] = threeWayClazz.ordinal();
        dataRaw.add(new DenseInstance(1.0, instanceValue));
        dataRaw.setClassIndex(1);
    }

So basically we put input unigrams (words) as a String x value and integer of label as y value, thus forming a training instance for the algorithm. Next the algorithm will internally tokenize the input string sequence and update the necessary probabilities.

For five way classification the above method looks almost the same, except the first parameter is of type SentimentClass.FiveWayClazz.

Training the model after we have finished adding the training examples is quite simple:

public void trainModel() throws Exception {
        classifier.buildClassifier(dataRaw);
    }

That's it!

I/O (storing and retrieving the trained model)

It is ok to train a model and classify right a way. But, that does not work, if you want to develop your model and ship that to production. In production mode your trained classifier will do its main work: classify new instances. So your model must be pre-trained and exist on disk. Storing and loading a trained model with Weka is extremely easy. This is thanks to the fact the classifiers extend abstract class AbstractClassifier, which in turn implements Serializable interface among others.

Storing the trained model is as easy as:

public void saveModel() throws Exception {
        weka.core.SerializationHelper.write(modelFile, classifier);
    }

And loading the model is easy too:
public void loadModel(String _modelFile) throws Exception {
        NaiveBayesMultinomialText classifier = (NaiveBayesMultinomialText) weka.core.SerializationHelper.read(_modelFile);
        this.classifier = classifier;
    }


After we have loaded the model, let's classify some texts. The method for the three way classification is:

public SentimentClass.ThreeWayClazz classify(String sentence) throws Exception {
        double[] instanceValue = new double[dataRaw.numAttributes()];
        instanceValue[0] = dataRaw.attribute(0).addStringValue(sentence);

        Instance toClassify = new DenseInstance(1.0, instanceValue);
        dataRaw.setClassIndex(1);
        toClassify.setDataset(dataRaw);

        double prediction = this.classifier.classifyInstance(toClassify);

        double distribution[] = this.classifier.distributionForInstance(toClassify);
        if (distribution[0] != distribution[1])
            return SentimentClass.ThreeWayClazz.values()[(int)prediction];
        else
            return SentimentClass.ThreeWayClazz.NEUTRAL;
    }

Notice the line #12. Remember, that we have defined the target classes for the three way classifier as {NEGATIVE, POSITIVE}. So in principle our classifier should be capable to do the binary classification. But! In the event when the probability distribution between the classes is exactly equal, we can safely assume it is NEUTRAL class. So we get the three way classifier. The following test case should ideally pass:

@org.junit.Test
    public void testArbitraryTextPositive() throws Exception {
        threeWayMnbTrainer.loadModel(modelFile);
        Assert.assertEquals(SentimentClass.ThreeWayClazz.POSITIVE, threeWayMnbTrainer.classify("I like this weather"));
    }

Neat!

To wrap things up, here is the "runner" class that builds the three-way classifier, saves the model and tests it for quality over the training data:

public class ThreeWayMNBTrainerRunner {
    public static void main(String[] args) throws Exception {
        KaggleCSVReader kaggleCSVReader = new KaggleCSVReader();
        kaggleCSVReader.readKaggleCSV("kaggle/train.tsv");
        KaggleCSVReader.CSVInstanceThreeWay csvInstanceThreeWay;

        String outputModel = "models/three-way-sentiment-mnb.model";

        ThreeWayMNBTrainer threeWayMNBTrainer = new ThreeWayMNBTrainer(outputModel);

        System.out.println("Adding training instances");
        int addedNum = 0;
        while ((csvInstanceThreeWay = kaggleCSVReader.next()) != null) {
            if (csvInstanceThreeWay.isValidInstance) {
                threeWayMNBTrainer.addTrainingInstance(csvInstanceThreeWay.sentiment, csvInstanceThreeWay.phrase.split("\\s+"));
                addedNum++;
            }
        }

        kaggleCSVReader.close();

        System.out.println("Added " + addedNum + " instances");

        System.out.println("Training and saving Model");
        threeWayMNBTrainer.trainModel();
        threeWayMNBTrainer.saveModel();

        System.out.println("Testing model");
        threeWayMNBTrainer.testModel();
    }
}



The quality of the model

Testing the trained model is fairly easy with Weka as well. Knowing the quality of your model is important because you want to make sure that there is no under- or overfitting happening. Underfitting means you haven't found an optimum of features describing your fenomena to fully utilize your training data, thus the model is long-sighted or too simple. Overfitting means you deal with over-learning your training data and over-adjusting for it, i.e. the model does not generalize for real world instances and becomes too short-sighted or too complex.

There are different ways to test the model, one is use part of you training data as test data (for example one third) and perform N fold cross-validation. I.e. on each iteration take a new piece of training data for test data and compute sensible metrics, like precision / recall / accuracy etc. In the end of the cross-validation take average over computed values. This will be your "amortized" quality.

We can also take a peek look at the quality by just counting the number of correctly classified instances from the training data:

    public void testModel() throws Exception {
        Evaluation eTest = new Evaluation(dataRaw);
        eTest.evaluateModel(classifier, dataRaw);
        String strSummary = eTest.toSummaryString();
        System.out.println(strSummary);
    }

The method outputs the following statistics:

Correctly Classified Instances       28625               83.3455 %
Incorrectly Classified Instances      5720               16.6545 %
Kappa statistic                          0.4643
Mean absolute error                      0.2354
Root mean squared error                  0.3555
Relative absolute error                 71.991  %
Root relative squared error             87.9228 %
Coverage of cases (0.95 level)          97.7697 %
Mean rel. region size (0.95 level)      83.3426 %
Total Number of Instances            34345     

The code can be found on my github. It utilizes the data posted on kaggle. So if you want to use the code as is (and perhaps even make a submission) you need to accept the terms of the kaggle competition and download the training set. I leave the exercise of implementing the full code for five-way classification and code for classifying kaggle's test set to the reader.



Monday, March 31, 2014

Implementing own LuceneQParserPlugin for Solr

Whenever you need to implement a query parser in Solr, you start by sub-classing the LuceneQParserPlugin:


public class MyGroundShakingQueryParser 
                           extends LuceneQParserPlugin {
    public QParser createParser(String qstr, 
                                SolrParams localParams,
                                SolrParams params,
                                SolrQueryRequest req) {}
}

In this way you will reuse the underlining functionality and parser of the LuceneQParserPlugin. The grammar of the parser is defined in QueryParser.jj file inside Lucene/Solr source code tree.

The grammar that QueryParser.jj uses is BNF. The JavaCC tool implements parsing of such grammars and producing the java code for you. The produced code is effectively a parser with built-in validation etc.

In Solr there is its own version of LuceneQParserPlugin: it is called QParserPlugin and in fact it pretty much implements almost the same functionality as its counterpart.

There could be use cases for customization of the lucene parsing grammar (stored in QueryParser.jj). Once the customization is done (let's rename the jj file to GroundShakingQueryParser.jj), we invoke the javacc tool and it produces a GroundShakingQueryParser.java and supplementary classes. In order to wire it into the Solr we need to do a few things. The final class inter-play is shown on the class diagram:

class diagram of inter-relations between classes
Going bottom up:
1. You implement your custom logic in GroundShakingQueryParser.jj that produces GroundShakingQueryParser.java. Make sure the class extends SolrQueryParserBase.
2. To wire this into Solr, we need to extend the GroundShakingQueryParser class in GroundShakingSolrQueryParser class.

/**
 * Solr's default query parser, a schema-driven superset of the classic lucene query parser.
 * It extends the query parser class with modified grammar stored in GroundShakingQueryParser.jj.
 */
public class GroundShakingSolrQueryParser extends GroundShakingQueryParser {

  public GroundShakingSolrQueryParser(QParser parser, String defaultField) {
    super(parser.getReq().getCore().getSolrConfig().luceneMatchVersion, defaultField, parser);
  }

}

3. Instance of GroundShakingSolrQueryParser is acquired in the GroundShakingLuceneQParser class.

class GroundShakingLuceneQParser extends QParser {
    GroundShakingSolrQueryParser lparser;

    public GroundShakingLuceneQParser(String qstr, SolrParams localParams, SolrParams params, SolrQueryRequest req) {
        super(qstr, localParams, params, req);
    }


    @Override
    public Query parse() throws SyntaxError {
        String qstr = getString();
        if (qstr == null || qstr.length()==0) return null;

        String defaultField = getParam(CommonParams.DF);
        if (defaultField==null) {
            defaultField = getReq().getSchema().getDefaultSearchFieldName();
        }
        lparser = new GroundShakingSolrQueryParser(this, defaultField);

        lparser.setDefaultOperator
                (GroundShakingQueryParsing.getQueryParserDefaultOperator(getReq().getSchema(),
                        getParam(QueryParsing.OP)));

            return lparser.parse(qstr);
    }


    @Override
    public String[] getDefaultHighlightFields() {
        return lparser == null ? new String[]{} : new String[]{lparser.getDefaultField()};
    }

}


4. GroundShakingLuceneQParser is wired into GroundShakingQParserPlugin that extends the aforementioned QParserPlugin.


public class GroundShakingQParserPlugin extends QParserPlugin {
  public static String NAME = "lucene";

  @Override
  public void init(NamedList args) {
  }

  @Override
  public QParser createParser(String qstr, SolrParams localParams, SolrParams params, SolrQueryRequest req) {
    return new GroundShakingLuceneQParser(qstr, localParams, params, req);
  }
}


5.  Now we have our custom GroundShakingLuceneQParser which can be directly extended in our MyGroundShakingQueryParser!

public class MyGroundShakingQueryParser 
                           extends GroundShakingLuceneQParserPlugin {
    public QParser createParser(String qstr, 
                                SolrParams localParams,
                                SolrParams params,
                                SolrQueryRequest req) {}
}

To register the MyGroundShakingQueryParser in solr, you need to add the following line into solrconfig.xml:

<queryparser class="com.groundshaking.MyGroundShakingQueryParser" name="groundshakingqparser"/ >


To use it, just specify the name in the defType=groundshakingqparser as a query parameter to Solr.


By the way, one convenience of this implementation is that we can deploy the above classes in a jar under solr core's lib directory. I.e. we do not need to overhaul solr source code and deal with deploying some "custom" solr shards.



Monday, February 24, 2014

First Android app published

First Android app published! To be used in Helsinki Metropolitan Area. Give it a spin!


PysaDroid is an easy and clutter free app for planning your journey in the Helsinki Metropolitan Area similar to what you get with HSL service https://www.hsl.fi/. Currently bus routes are supported only.
The name PysaDroid comes from a blend of Pysäkki ([bus] stop in Finnish) and Android.
Key features:
- Non-intrusive autocomplete. Very useful feature if you feel like you don't remember the full street or place name. Or it is just too freezing outside to type with bare fingers.
- Clean design of the resulting routes
- Latest search button that remembers your last search! Press the bus button to load your latest search.
- Take me to home functionality: set up the direction to home on the results page once by pressing the button with home icon and use every day!
- Take me to the office functionality: similar to take me home.
- View the route on the map.

Sunday, February 23, 2014

Android: filler / divider between columns in a TableLayout

Android is pretty tricky to deal with at times, and surprisingly difficult for something very simple..
..like adding a filler between columns in a TableLayout. "Gotta be simpler!" I thought after having spent countless minutes reading up over countless suggestions and recipes.

So I took the path of just creating an empty filler.png image in the mspaint, just a vertical bar, and inserting it programmatically:

ImageView dividerView = new ImageView(this);
dividerView.setImageResource(R.drawable.filler);

Then added this to a TableRow object which subsequently should be added to the aforementioned TableLayout.

Before adding a divider:


After adding a divider:


Monday, December 16, 2013

Lucene Toolbox Luke

As I was mentioning in some of the previous posts, I have been working on luke, the Lucene Toolbox. Recently, the releases have been more or less steady, providing the binaries right on the github site.



Here is the most recent release of luke for the most recent release of Lucene 4.6.0:

port to Lucene 4.6.
Tested against the solr-4.6 index of exampledocs xml files.
Changelist:
1. bumped up the version of maven-assembly plugin to the latest 2.4
2. added maven-jar plugin which copies all binary dependencies into lib/ subdirectory
3. Fixed AnalyzerToolPlugin to use token stream reset outside while loop over tokens
4. added lock factory handling in FsDirectory (untested)
5. updated trivia in about.xml

At the moment the generated all-inclusive jar can be launched by double-clicking it only. There is some work to do to enable command line launches.

If you feel like contributing (patches and new features alike) and enjoy using the tool, get in touch or just send a pull request.

Enjoy the season's holidays,

Sunday, November 24, 2013

Training on NLProc and Machine Learning

Just did a training on NLProc (imho, better abbreviation for natural language processing than NLP) and Machine Learning for OK.ru (Russian Facebook owned by Mail.Ru Group) in person in Saint-Petersburg, Russia.

OK.ru has a nice office not far from Petrogradskaya subway station in Saint-Petersburg (the central office is in Moscow).


If you feel like your project is somewhat stuck and needs a fresh look or you need to widen you knowledge in NLProc and / or machine learning, feel free to contact me on g+. At the moment folks at SemanticAnalyzer can do this in Europe / western part of Russia. At SemanticAnalyzer we also offer a full package of services for natural language processing development in case there isn't expertise in your house. This includes project scoping, breaking down by technical tasks, time estimation, development, testing / evaluation and delivery.

Wednesday, November 13, 2013

Lucene Revolution EU 2013 in Dublin: Day 2

This post tells my impressions of the Lucene Revolution conference held in Dublin, Ireland, 2013, day 2. The day 1 is described here.

Second day was slightly tougher to start right after the previous evening in a bar with committers and conference participants, but good portion of full Irish breakfast with coffee helped a lot and set me up for the day.

I decided to postpone coming to the conference venue (Aviva stadium) right until the technical presentations started. But, I was in early enough still to make it to the panel with Paul Doscher. Paul holds himself quite professionally and talks in a convincing manner. He didn't seem to be a BS CEO, and tries best to address the question at hand as deeply and low-level as possible. May be EU audience was a bit sleepy or a not too comfortable talking otherwise (geeks, geeks), which didn't spawn as many discussions / questions. Two Paul's questions that come to mind:



1. Have you been doing search / big data during past 4-5 years?
2. Do you think the search / big data is a good area to stay until end of your IT career?

There have been more hands for 1 than for 2. Which in Paul's mind was a bit strange as he strongly believes search and big data is the area to stay. There is so much complexity involved and so much data has been accumulated by enterprises that there will be a strong demand in specialists of this sort. While I would second this, I can tell that the consumers of enterprise data will have higher standards to quality, because they do business with it. On the other hand, in my opinion, if you take so called mass media (microblogs, forums, user sentiment and so on), there is also big data produced at high speeds, but the user base on average is not as demanding. It is again businesses that will likely to be interested to sift some signal from the mass media noise.

Coming back to the technical presentations.

The first technical presentation I visited has been "Lucene Search Essentials: Scorers, Collections and Custom Queries" by +Mikhail Khludnev. I know Mikhail since more than a year ago, sitting on the same Solr user mail-list and commenting on SORL jira.

His team has been doing some really low-level stuff with Solr / Lucene code for e-commerce and this presentation has summarized his knowledge pretty much. I'd say while the presentation is accessible for a non-prepared audience, it goes quite deep into analyzing compexities of certain search algorithms and lays a background for more conscious search. The slides.

On the next session Isabel Drost-Fomm introduced the audience into the world of text classification and Apache Mahout. Isabel is a co-founder of another exciting conference on search and related technologies Berlin Buzzwords and is a Mahout committer.



Before the session Isabel mentioned to me, that one of the targets of her presentation is let people know the existing good systems like Lucene with tokenizers and focus on solving a particular task at hand instead of reinventing a wheel. Good intro level presentation, and after trying out Mahout, I must say you can get going with the examples quite easily. Isabel had mentioned that becoming a committer in the Apache community is easier than one might think: fix or write new documentation, attach small patches (not necessarily code) and that might be enough. But, removing yourself from the committer status is much harder, because, if I sensed it right, Apache has rather wide network of reminding you to commit. So you might find yourself coding over the weekend for Open Source. Which, in the long run,  may make a good career boost for you.

In the lobbies some folks wanted to chat about luke project, that I have been contributing lately. Finally added its creator Andrzej Bialecki as a contributor. If you enjoy using luke and want to make it better, feel free to join and start contributing yummy patches!

The next cool presentation was presented by Alan Woodward and Charlie Hull (who published a nice writeup on the conference here and here). Their collaborative talk focused on turning the search upside down: queries become documents and documents become queries (honestly, I would like to see how this is handled in the code in terms of naming the variables and functions). Charlie briefly mentioned that the code will be open-sourced. The specific use case for this is a bank of queries or a taxonomy of queries (for instance, for patent examiners) that need to be executed against each incoming document. If there is a hit, this document gets the query id as some concept. What I liked in the presentation is the innovative look on the problem: given a set of queries, what is the efficient representation of them in the Lucene index? For example a SpanNear query can be represented as an AND on its operands, then  the AND query can be checked only for one operand quickly and efficiently. If it is not present, the entire query is not hitting the document. They also used the position aware Scorer that can iterate the intervals of positions. I did a similar work in the past, but used the not so efficient Highlighter component. So I'm glad there is a similar work done in an efficient manner. UPD: the tool called Luwak has been open-sourced!

In the next presentation Adrien Grand walked the audience through the design decisions behind data structures in Lucene index, compared Lucene indices to RDBMS indices (I tried to summarize it here) and talked about things on hardware / OS level, like using SSD disks and allocating enough RAM for OS cache buffers. During the Q&A I have suggested an idea that in order to increase the indexing throughput one can set the merge factor to thousands and upon completion to 10 or even 1 so that the search side would be efficient. The indexing then will not need to merge as often. Adrien has seconded this idea and also proposed to use TieredMergePolicy (default in Solr) where you can control the merging of segments with a number of docs deleted. This is needed both for efficiency and timely space re-claiming. Even though I have missed the closing remarks, since this presentation took more time than expected, I was happy to be there as the presentation was quite thought provocative.

These have been two intense days both in terms of technical presentations and sightseeing. I have only been able to explore Trinity College and areas around it, but doing this on foot was quite a good sport activity.

The apogee of this day and perhaps of the conference was meeting entire sematext team while roaming around shopping streets near Trinity College! We had some good time together in a local bar. It's been fun, thanks guys!

This pretty much wraps up my 2-post impressions and notes on the Lucene Revolution conference 2013 in Dublin.

If you enjoyed this writeup, there is a delightful writeup by +Mike Sokolov :
http://blog.safariflow.com/2013/11/25/this-revolution-will-be-televised/

And read the Flax writeups too (links above in the post).

Happy searching,

@dmitrykan

Sunday, November 10, 2013

Lucene Revolution EU 2013 in Dublin: Day 1

The Lucene Revolution conference has been held for the first time in Europe. Dublin, Ireland, has been selected as the conference city and I must say it is a great choice. The city itself is quite compact and friendly, full of places to see (Trinity Colleage, Temple Bar, O'Connell street and many more) as well as places to relax with all the pubs, bars and shopping streets.



It was my first time in Dublin and my general impression of the city is very good.

Let's proceed to the conference!

Day 1


The keynote has been presented by Michael Busch of Twitter, who talked about their data structure for holding an index in such a way that posting lists are automatically sorted and one can read backwards without reopening an index (costly op). They also support early termination naturally in such a way. Everything is stored in RAM and they never commit.

Followed by the keynote I watched Timothy Potter present about integrating Solr and Storm for realtime stream processing.
What I specifically liked in Tim's presentation was two things: (1) he gave personal recommendations for certain libraries and frameworks, like Netty, Coda Hale Metrics and (2) he emphasized, that even that we deal with relatively exotic technologies like Solr and Storm we can still rely on old proven technologies, like Spring + Jackson to remap input json into neatly named properties of a Java class. This all comes in handy when you start working on your own backend code.

Next, LinkedIn engg's talked about their indexing architecture for segmentation and targeting platform.
They use Lucene only, no Solr yet, but would be interested to look into things like SolrCloud. Also mentioned in the presentation was the architectural decision to abstract the Lucene engine from the the business logic by writing a json to Lucene query parser. This will help if they ever decide to try some other search engine. On one hand I sense here, that large business is more cautious than let's say a smaller company. On the other hand, imho, Lucene has grown into a very stable system and given its long presence on the market and wide adoption wouldn't be too cautious. But biz is biz.

Up next was the session on additions to Lucene arsenal by Shai Erera and Adrien Grand. I'd say this presentation was the most in-depth technically during this day. Shai talked about new replication module added to Lucene and expressed the hope of it being added to ElasticSearch and Solr or even replacing their own replication methods. Adrien focused on implementation details of new feature called Index Sorting. The idea is that an index can be kept always sorted on some criteria, like modification date of a document, which in turn will enable for early termination techniques and better compression of sorted index.

After lunch break I decided to go to "Shrinking the Haystack" using Solr and OpenNLP by Wes Cladwell. While his presentation wasn't too technical it had mentioned really hilarious uncommon practice they have at ISS Inc while building search and data processing solutions for FBI type of agencies. One question, he said, strucks every sw engg applicant is: "Will you be ok to spend a weekend in Afganistan?" Not an usual working place, hah? To me, having spent a month in Algeria as a consultant, this sounded somewhat familiar, because when entering my hotel the car was always checked by tommy-gunners. The take-away point of this presentation was that they build big data systems not to find a needle in the haystack, but give tools to human analysts to help find an actionable intelligent data. I.e. you can't replace people. The presentation also mentioned some tech. goodies, like boilerpipe for extracting text from an html leaving boiler html out; GeoNames = open source geo-entity database, that can be indexed into a Solr core for better search. In terms of NLProc and machine learning at ISS they have arrived at combining gazeteer (dictionary) and supervised machine learning to give the best of both worlds. From my NLProc + ML experience at SemanticAnalyzer I will only second this.


Since I have spent a number of weeks focusing of various query parsers changing QueryParser.jj grammar with JavaCC I have decided to see an alternative approach to building parsers: presentation on Parboiled by John Berryman. He has been implementing a legacy replacement system for patent examiners, who have at times super-long boolean and positional queries and who are not ready to give up their query syntax. What is great about Parboiled based parsers is that it is Java, i.e. the parser itself is declaratively expressed using your own Java code. It works nicely with Lucene's SpanQueries and general Queries. On the other hand, in lobbies John had mentioned that debugging the Parboiled generated parser is not straighforward. Well, JavaCC isn't any better either in terms of debugging. One listener from the audience has mentioned Antlr, which he enjoyed using. There is a JIRA for introducing Antlr into query parsing with Lucene, if you would like to work on this practically. John's slides can be enjoyed here.

After all this techy stuff I made a larger break and searched for networking with sematext guys at their booth, with +Mikhail Khludnev, Documill (from Espoo, yeah!) and other people to sense what type of audience has arrived at the conference and why did they have an interest in Lucene / Solr specifically.

The apogee of the day had been the lovely Stump the Chump session by +Chris Hostetter. Which truly yours had a privilege to win with the first time first place! I'll update this post with the video once it is out of production lines.

Up next is the second day of the conference in the next post as this post is quite a long read already.

Sunday, October 20, 2013

SentiScan: блог-пост о технологии распознавания сентимента (тональной окрашенности сообщений)

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

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

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

позитив
благородный
доход
изысканный
лояльный
необыкновенный
оперативный
передовой

негатив
абсурд
винить
вымогательство
грабеж
идиотский
нытье
отвратительный

Как можно заметить, в словарях присутствуют представители любых частей речи: не только имён прилагательных, но имён существительных, глаголов. Есть и наречия (отвратительно). 

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

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

1. в тексте не было ни одной тонально окрашенной единицы либо синтаксического противопоставления (объект А, но объект Б)

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

У описанного здесь вкратце алгоритма есть также и отдельная функциональность определения объективности ("беспристрастноси") и субъективности текста либо сообщения. Если автор текста не использует эмоционально окрашенных выражений, то его текст можно в целом считать объективным или беспристрастным. И субъективным, если использует. Распознавание субъективности автора может быть полезна тем брендам, которые ищут "подлинные" обзоры их продукции, т.е. опирающиеся на факты.

Попробовать эту систему в действии можно, написав нам письмо на info@semanticanalyzer.info. Техническая документация и характеристики быстродействия описаны в документации.



Sunday, October 6, 2013

Deep learning: анализ текста и изображений при помощи Рекурсивных Нейронных сетей

Продолжая тему Deep Learning, получившую в последнее время большое внимание научного сообщества и индустрии, хочется рассказать про довольно необычную сферу применения нейронных сетей. Это сфера разбора (parsing) изображений рекурсивными нейронными сетями. В этом посте я кратко опишу суть и приведу ссылки для более детального ознакомления с материалом. Помимо этого будет ссылка на задачу из Stanford'а для желающих попробовать свои силы и получить практический результат в области deep learning для NLP.

Этот пост базируется на докладе Richard Socher, видео на английском доступно здесь.

Как оказывается, рекурсивной (или некоторой регулярной) структурой может обладать не только язык, но и изображения. Но в начале о рекурсивных свойствах предложений. Принцип композиционности (principle of compositionality) делает предположение, что любое предложение на естественном языке можно представить в виде иерархической структуры из связных составляющих. Смысл предложения можно представить в виде смыслов слов, в него входящих, и списка правил соединения слов в группы. Например, в предложении:

Это страна моего рождения.

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

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

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

Алгоритм на основе рекурсивных нейронных сетей авторов Socher и др. достигает 78,1% качества. Область применения таких алгоритмов -- распознавание сцен (область анализа изображений или image analysis). Исходные коды и датасеты можно посмотреть здесь.

Задачка. Для более детального ознакомления с deep learning в применении к задачам NLP на сайте Stanford'a предлагается к решению задачка: реализовать простой оконный распознаватель именных сущностей (Named Entity Recognition или NER). Описание задачки здесь. Стартовый исходный код на Java и тренировочный сет здесь. Тренировочный сет аннотирован персонами, например:

Franz PERSON
Fischler PERSON

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

Довольно много материалов по теме Deep Learning можно найти на сайте Richard Socher, включая применение данного направления к распознаванию тональности (sentiment analysis).