Classification of text using a neural network in Java

i11 July 3, 2017 at 10:19

Classification of text using a neural network in Java

Tutorial

“Our Lena goes on maternity leave,” the chief said, “so we need to look for a replacement for the time of her absence.” We will distribute part of the tasks, but what about the task of redirecting user requests?

Lena is our technical support officer. One of her responsibilities is the distribution of calls received by e-mail between specialists. It analyzes the appeal and defines a number of characteristics. For example, “Call Type”: a system error, the user just needs a consultation, the user wants some new functionality. Defines the “System Functional Module”: accounting module, equipment certification module, etc. Having set all these characteristics, she redirects the appeal to the appropriate specialist.

- Let me write a program that will do this automatically! I answered.

On this fascinating novel we finish and move on to the technical part.

We formalize the problem

the input receives text of arbitrary length and content;
the text is written by a person, therefore it may contain typos, errors, abbreviations and generally be obscure;
this text needs to be somehow analyzed and classified according to several unrelated characteristics. In our case, it was necessary to determine the essence of the appeal: an error message, a request for new functionality or a consultation is needed, and also to determine a functional module: payroll calculation, accounting, warehouse management, etc .;
only one value can be assigned for each characteristic;
the set of possible values for each characteristic is known in advance;
there are several thousand already classified calls.

Having formalized the task and starting development for our specific needs, I realized that it is better to develop a universal tool right away that will not be rigidly tied to any specific characteristics and the number of these characteristics. As a result, a tool was born that was able to classify text according to arbitrary characteristics.

I did not look for ready-made solutions, because there was time and interest to do it myself, while immersing myself in the study of neural networks.

Tool selection

I decided to develop in Java.

As a DBMS used SQLite and H2 . Hibernate also came in handy .

From here I took the finished implementation of the neural network (Encog Machine Learning Framework). I decided to use a neural network as a classifier, and not, for example, a naive Bayesian classifier , because, firstly, theoretically, a neural network should be more accurate. Secondly, I just wanted to play around with neural networks.

To read the Excel file with data for training, some Apache POI libraries were needed .

Well, and for tests traditionally used JUnit 4 + Mockito .

A bit of theory

I will not describe in detail the theory of neural networks, since there are plenty of it ( here is a good introductory material). In short and simple: the network has an input layer, hidden layers and an output layer. The number of neurons in each layer is determined by the developer in advance and after training the network can not be changed: if at least one neuron was added / decreased, then the network needs to be retrained again. A normalized number is fed to each neuron of the input layer (most often from 0 to 1). Depending on the set of these numbers on the input layer, after certain calculations, a number from 0 to 1 is also obtained on each output neuron.

The essence of training the network is that the network adjusts its connection weights involved in the calculations so that with a predetermined set of numbers on the input layer, a previously known set of numbers on the output layer is obtained. Adjusting weights is an iterative process and occurs until the network reaches a given accuracy in the training set or until it reaches a certain number of iterations. After training, it is assumed that the network will produce a set of numbers close to the reference set on the output layer if a set of numbers similar to the one in the training set was applied to the input layer .

Let's move on to practice

The first task was to come up with how to convert the text to a form that can be transmitted to the input of a neural network. But first, it was necessary to determine the size of the input network layer, since it must be predefined. Obviously, the input layer must be of such a size that any text can be "fit" into this layer. The first thing that comes to mind is that the size of the input layer should be equal to the size of the dictionary containing the words / phrases that make up the texts.

There are many ways to build a dictionary. You can, for example, stupidly take all the words of the Russian language and this will be our dictionary. But this approach is not suitable, because the size of the input layer will be so huge that the resources of a simple workstation are not enough to create a neural network. For example, imagine that our dictionary consists of 100,000 words, then we have 100,000 neurons in the input layer; let's say 80,000 in a hidden layer (the method for determining the dimension of a hidden layer is described below) and 25 in the output. Then, just to store the connection weights, ~ 60 GB of RAM is required: ((100 000 * 80 000) + (80 000 * 25)) * 64 bits (double type in JAVA). Secondly, this approach is not suitable, because the texts can use specific terminology that is not in the dictionaries.

This suggests the conclusion that the dictionary should be built only from those words / phrases that make up our analyzed texts. It is important to understand that in this case, to build a dictionary, there must be a sufficiently large amount of training data.

One of the ways to “pull out” words / phrases (even more precisely, fragments) from a text is called building N-grams . The most popular are unigrams and bigrams. There are also symbolic N-grams - this is when the text is not split into separate words, but into segments of characters of a certain length. It is difficult to say in advance which of the N-grams will be more effective in a particular task, so you need to experiment.

Text	Unigram	Bigram	3-character N-gram
This text should be broken into pieces.	[“This”, “text”, “should”, “be”, “broken”, “on”, “parts”]	[“This text”, “text should”, “should be”, “be broken”, “broken into”, “into parts”]	[“This”, “t t”, “ex”, “t d”, “olzh”, “en”, “everyday life”, “b r”, “azb”, “um”, “on”, “hour "," Tee "]

I decided to move from simple to complex and first developed the Unigram class.

Unigram class

class Unigram implements NGramStrategy {
  @Override
  public Set getNGram(String text) {
    if (text == null) {
      text = "";
    }
    // get all words and digits
    String[] words = text.toLowerCase().split("[ \\pP\n\t\r$+<>№=]");
    Set uniqueValues = new LinkedHashSet<>(Arrays.asList(words));
    uniqueValues.removeIf(s -> s.equals(""));
    return uniqueValues;
  }
}

As a result, after processing ~ 10,000 texts, I received a dictionary of ~ 32,000 elements in size. After analyzing the resulting dictionary diagonally, I realized that it has a lot of unnecessary things to get rid of. To do this, I did the following:

Removed all non-letter characters (numbers, punctuation, arithmetic operations, etc.), since they, as a rule, carry no semantic load.
I drove through the procedure word Stemming (used stemmer Porter for Russian language). By the way, a useful side effect of this procedure is the “unisexation” of texts, that is, “made” and “done” will be transformed into a “do”.
At first I wanted to identify and correct typos and grammatical errors. I read about the Oliver Algorithm ( similar_text function in PHP) and the Levenshtein distance . But the problem was solved much easier, albeit with an error: I decided that if an element of the N-gram is found in less than 4 texts from the training set, then we do not include this element in the dictionary as useless in the future. Thus, I got rid of most typos, words with grammatical errors, “stuck together” and just very rare words. But you must understand that if typos and grammatical errors are often found in future texts, the classification accuracy of such texts will be lower and then you still have to implement a mechanism for correcting typos and grammatical errors. Important: such a “feint” with ejecting rare words is permissible with a large amount of data for training and building a dictionary.

All this is implemented in the FilteredUnigram and VocabularyBuilder classes.

Class FilteredUnigram

public class FilteredUnigram implements NGramStrategy {
  @Override
  public Set getNGram(String text) {
    // get all significant words
    String[] words = clean(text).split("[ \n\t\r$+<>№=]");
    // remove endings of words
    for (int i = 0; i < words.length; i++) {
      words[i] = PorterStemmer.doStem(words[i]);
    }
    Set uniqueValues = new LinkedHashSet<>(Arrays.asList(words));
    uniqueValues.removeIf(s -> s.equals(""));
    return uniqueValues;
  }
  private String clean(String text) {
    // remove all digits and punctuation marks
    if (text != null) {
      return text.toLowerCase().replaceAll("[\\pP\\d]", " ");
    } else {
      return "";
    }
  }
}

Class VocabularyBuilder

class VocabularyBuilder {
  private final NGramStrategy nGramStrategy;
  VocabularyBuilder(NGramStrategy nGramStrategy) {
    if (nGramStrategy == null) {
      throw new IllegalArgumentException();
    }
    this.nGramStrategy = nGramStrategy;
  }
  List getVocabulary(List classifiableTexts) {
    if (classifiableTexts == null ||
        classifiableTexts.size() == 0) {
      throw new IllegalArgumentException();
    }
    Map uniqueValues = new HashMap<>();
    List vocabulary = new ArrayList<>();
    // count frequency of use each word (converted to n-gram) from all Classifiable Texts
    //
    for (ClassifiableText classifiableText : classifiableTexts) {
      for (String word : nGramStrategy.getNGram(classifiableText.getText())) {
        if (uniqueValues.containsKey(word)) {
          // increase counter
          uniqueValues.put(word, uniqueValues.get(word) + 1);
        } else {
          // add new word
          uniqueValues.put(word, 1);
        }
      }
    }
    // convert uniqueValues to Vocabulary, excluding infrequent
    //
    for (Map.Entry entry : uniqueValues.entrySet()) {
      if (entry.getValue() > 3) {
        vocabulary.add(new VocabularyWord(entry.getKey()));
      }
    }
    return vocabulary;
  }
}

Dictionary Compilation Example:

Text	Filtered Unigram	Vocabulary
Need to find a sequence of 12 tasks	needed, knight, sequential, tasks	needed, knight, sequential, tasks, for, arbitrarily, add, transpositions
Task for arbitrary	tasks, for, arbitrarily
Add arbitrary transposition	add, arbitrary, transposition

To build Bigram, he also immediately wrote a class, so that after the experiments, he would choose the option that gives the best result in terms of the ratio of dictionary size and classification accuracy.

Class bigram

class Bigram implements NGramStrategy {
  private NGramStrategy nGramStrategy;
  Bigram(NGramStrategy nGramStrategy) {
    if (nGramStrategy == null) {
      throw new IllegalArgumentException();
    }
    this.nGramStrategy = nGramStrategy;
  }
  @Override
  public Set getNGram(String text) {
    List unigram = new ArrayList<>(nGramStrategy.getNGram(text));
    // concatenate words to bigrams
    // example: "How are you doing?" => {"how are", "are you", "you doing"}
    Set uniqueValues = new LinkedHashSet<>();
    for (int i = 0; i < unigram.size() - 1; i++) {
      uniqueValues.add(unigram.get(i) + " " + unigram.get(i + 1));
    }
    return uniqueValues;
  }
}

I decided to dwell on this for the time being, but further word processing for compiling a dictionary is possible. For example, you can define synonyms and bring them to a single look, you can analyze the similarity of words, you can even come up with something of your own, etc. But, as a rule, this does not give a significant increase in the accuracy of classification.

Okay, let's move on. The size of the input layer of the neural network, which will be equal to the number of elements in the dictionary, we calculated.

The size of the output layer for our task will be made equal to the number of possible values for the characteristic. For example, we have 3 possible values for the “Contact type” characteristic: a system error, user assistance, new functionality. Then the number of neurons of the output layer will be equal to three. When training the network for each value of the characteristic, it is necessary to determine in advance a unique reference set of numbers that we expect to receive on the output layer: 1 0 0 for the first value, 0 1 0 for the second, 0 0 1 for the third ...

As for the number and dimension of hidden layers, there is no specific recommendation. The sources write that the optimal size for each specific task can only be calculated experimentally, but for a narrowing network it is recommended to start with one hidden layer, the size of which varies between the sizes of the input layer and the output. To start, I created one hidden layer 2/3 the size of the input layer, and then I experimented with the number of hidden layers and their sizes. Here here you can read a bit of theory and guidelines on this subject. It also describes how much data should be for training.

So, we have created a network. Now we need to decide how we will convert the text into numbers suitable for “feeding” a neural network. To do this, we need to convert the text into a text vector . First, you need to assign each word in the dictionary a unique vector of the word , the size of which must be equal to the size of the dictionary. After training the network, you cannot change the vectors for words. Here's what it looks like for a 4-word dictionary:

Dictionary word	Word vector
Hi	1 0 0 0
as	0 1 0 0
business	0 0 1 0
you	0 0 0 1

The procedure for converting text into a text vector involves the addition of vectors of words used in the text: the text "how do you like hello?" will be converted to the vector "1 1 0 1". We can already feed this vector to the input of a neural network: each separate number for each separate neuron of the input layer (the number of neurons is exactly equal to the size of the text vector).

Method computing a text vector

private double[] getTextAsVectorOfWords(ClassifiableText classifiableText) {
  double[] vector = new double[inputLayerSize];
  // convert text to nGram
  Set uniqueValues = nGramStrategy.getNGram(classifiableText.getText());
  // create vector
  //
  for (String word : uniqueValues) {
    VocabularyWord vw = findWordInVocabulary(word);
    if (vw != null) { // word found in vocabulary
      vector[vw.getId() - 1] = 1;
    }
  }
  return vector;
}

Here and here you can read more about preparing the text for analysis.

Classification accuracy

Having experimented with different dictionary formation algorithms and with different numbers and dimensions of hidden layers, I settled on this option: we use FilteredUnigram with cutting off rarely used words to form a dictionary; make 2 hidden layers with a dimension of 1/6 of the size of the dictionary - the first layer and 1/4 of the size of the first layer - the second layer.

After learning ~ 20,000 texts (which is very small for a network of this size) and running a network of 2,000 reference texts, we have:

N gram	Accuracy	Dictionary size (without rarely used words)
Unigram	58%	~ 25,000
Filtered Unigram	73%	~ 1,200
Bigram	63%	~ 8 000
Filtered Bigram	69%	~ 3,000

This is accuracy for one characteristic. If accuracy is needed for several characteristics, then the calculation formulas are as follows:

The probability of guessing all characteristics at once is equal to the product of the guessing probabilities of each characteristic.
The probability of guessing at least one characteristic is equal to the difference between the unit and the product of the probabilities of the incorrect determination of each characteristic.

Example:

Suppose that the accuracy of determining one characteristic is 65%, the second characteristic is 73%. Then the accuracy of determining both at once is 0.65 * 0.73 = 0.4745 = 47.45% , and the accuracy of determining at least one characteristic is 1- (1-0.65) * (1-0.73) = 0 , 9055 = 90.55% .

Quite a good result for a tool that does not require preliminary manual processing of incoming data.

There is one “but”: the accuracy strongly depends on the similarity of the texts that should be assigned to different categories: the less similar the texts from the category “System Errors” to the texts from the category “Need Help”, the more accurate the classification will be. Therefore, with the same network and dictionary settings in different tasks and on different texts, there may be significant differences in accuracy.

Final program

As already said, I decided to write a universal program that is not tied to the number of characteristics by which to classify the text. I will not describe in detail all the details of the development, I will describe only the algorithm of the program, and a link to the sources will be at the end of the article.

The general algorithm of the program:

At the first start, the program requests an .xlsx file with training data. A file may consist of one or two sheets. The first sheet contains data for training, the second contains data for subsequent testing of network accuracy. The structure of the sheets is the same. The first column should contain the analyzed text. The following columns (there may be as many as they need) should contain the values of the text characteristics. The first line should contain the names of these characteristics.
Based on this file, a dictionary is built, a list of characteristics and unique values that are valid for each characteristic are determined. All this is stored in storage.
A separate neural network is created for each characteristic.
All created neural networks are trained and stored.
At a subsequent start-up, all stored trained neural networks are loaded. The program is ready for text analysis.
The resulting text is processed independently by each neural network, and the overall result is output as a value for each characteristic.

In the plans:

Add other types of classifiers (for example, convolutional neural network and naive Bayesian classifier );
Try using a dictionary consisting of a combination of unigrams and bigrams.
Add a mechanism to eliminate typos and grammatical errors.
Add a synonym dictionary.
Exclude too-frequent words, as they are usually informational noise.
Add weights to individual meaningful words so that their influence in the analyzed text is greater.
Redo the architecture a bit, simplifying the API so that you can take out the main functionality in a separate library.

A bit about the source

Sources can be useful as an example of the use of some design patterns. It makes no sense to put this in a separate article, but I also don’t want to keep silent about them, since I share my experience, so let it be in this article.

The "Strategy" pattern . NGramStrategy interface and classes that implement it.
Observer pattern . The LogWindow and Classifier classes that implement the Observer and Observable interfaces.
Decorator Pattern . Class Bigram.
Simple Factory Pattern. The getNGramStrategy () method of the NGramStrategy interface.
The "Factory Method" pattern . The getNgramStrategy () method of the NGramStrategyTest class.
Pattern "Abstract Factory" . Class JDBCDAOFactory.
Pattern (antipattern?) "Loner" . Class EMFProvider.
Pattern Template Method . The initializeIdeal () method of the NGramStrategyTest class. True, its application is not entirely classical here.
The DAO pattern . Interfaces CharacteristicDAO, ClassifiableTextDAO, etc.

Full source: https://github.com/RusZ/TextClassifier

Constructive suggestions and criticism are welcome.

PS: Do not worry about Lena - this is a fictional character.

Tags:

Classification of text using a neural network in Java