0
$\begingroup$

I am trying to find the best approach to this problem.

Consider that there is a type of text document, for instance a letter. I will refer to this as the Document Type.

I will refer to an individual instance of a Document Type as a Document.

A Document is a list of words, and includes word, x_position and y_position for each word, but there will be slight variations. For example words may be slightly differently positioned, or maybe not present, or maybe extra words. This is the core of the problem.

I will use supervised learning to classify each document, resulting in data of this shape -

Training Data

document, word, x_position, y_position, classification
1, {anonymized}, 167, 198, FirstName
1, some, 454, 17, 0
1, other, 124, 279, 0
1, words, 687, 826, 0
1, {anonymized}, 946, 342, PhoneNumber
2, {anonymized}, 169, 195, FirstName
2, some, 453, 16, 0
2, different, 123, 276, 0
2, words, 689, 822, 0
2, {anonymized}, 948, 346, PhoneNumber

Of course there will be many more documents and many more words in each document.

Note that an unclassified word has changed between documents, and the x_positions and y_positions have also changed slightly, as described above.

What is the best approach to use machine learning to build a model that will classify the following document, again with slightly different x_positions and y_positions and words.

Test Data

James, 165, 196  -> expect classification of FirstName
similar, 452, 18
different, 121, 279
words, 689, 822
0121789456, 941, 348 -> expect classification of PhoneNumber

This is a follow on question from this question. Your thoughts and advice would be greatly appreciated.

$\endgroup$
1
  • 1
    $\begingroup$ There is no "best" way, but look into word embeddings and the vector space model to construct your input layer and then apply a any number of classification algorithms (e.g., random forests, boosted trees, SVM, neural nets) etc to actually determine how to best classify to categories based on the input layer. $\endgroup$ – user145807 Nov 1 '17 at 17:07
1
$\begingroup$

Let me first restate the problem in a way more suitable for ML.

When you apply your model, you don't know which words are "named entities" - names, phones, etc. So in fact your data looks like

James, 165, 196      -> expect classification of FirstName
similar, 452, 18     -> expect classification of NoEntity
different, 121, 279  -> expect classification of NoEntity
words, 689, 822      -> expect classification of NoEntity
0121789456, 941, 348 -> expect classification of PhoneNumber

Given train data in this format, you can assign a class to each word in the letter, if you create good features and feed them to a good classifier.

I would start with a tree-based model (random forest or gradient boosting) and simple manually engineered features, like:

  • type of the document
  • x position of the word
  • x distance from the rightmost word
  • y position
  • y distance from the lowest word
  • position of the word in the document (from the beginning)
  • position of the word in the document (from the end)
  • position of the word in the current sentence (from the beginning)
  • position of the word in the current sentence (from the end)
  • number of occurences of this word in the document
  • number of letters in the word
  • number of capital letters in the word
  • number of digits
  • occurence of special symbols
  • part-of-speech of the word (predicted by nltk.tag, for example)
  • The word itself (word2vec embedding, or one-hot encoding) - if you have enough training data (which is, I would guess, not the case)
  • similar statistics for the $k$ previous and next words
  • distance from the closest occurence of the word 'number'
  • distance from the closest adjective
  • ...

Maybe you would like to concentrate on the nearest words (both sequentially and geometrically). To accomplish this, you could take the $k$ closest words (I would start with $k\approx 10$) in the document, and use them as features in a Naive Bayes classifier. Probabilities predicted by this classifier could be used directly or as additional features for the tree-based model.

You could include in your model all the possible words, but there would be tens of thousands of features, and your model would most likely overfit. You can decrease number of possible words by first taking embeddings of your words from a pretrained model (e.g. word2vec or fastText), clustering them, and using cluster labels instead of words. As a result, synonims or semantically close words will go into the same feature.

A more elaborate approach would be to train a RNN on your data, but probably this simple design will already suffice.

$\endgroup$
7
  • $\begingroup$ Thank you for this very helpful answer and suggested approach. Would it be possible using tree-based model to take into consideration the position of the words in relation to other words, almost "triangulating" them? Or is this a crazy idea? $\endgroup$ – gamesmad Nov 1 '17 at 17:33
  • $\begingroup$ @gamesmad yes, you can add features like <distance from the closest word 'number'> or <distance from the closest noun from the left>. $\endgroup$ – David Dale Nov 1 '17 at 17:35
  • $\begingroup$ For instance, in my training data from the question, if take the word "some" in document 1 and add -287 to x, and 181 to y, we will find the position of FirstName. In document 2 this is add -284 to x and 179 to y. These values are similar. I feel like the subtle similarities of the documents such as just described would be lost using the tree-based model? Or am I misunderstanding? $\endgroup$ – gamesmad Nov 1 '17 at 17:43
  • $\begingroup$ For example if we then find the word "some" in the test data, and try to find elements in range of -287 to -284 of x, and +181 to +179 of y, we are likely to find the FirstName value. Taking into account all of those relationships on the document would find the correct value. Again this may be a crazy idea...!? $\endgroup$ – gamesmad Nov 1 '17 at 17:46
  • 1
    $\begingroup$ I do not know a good way to include distances from all the words. Of course you can just loop across all the possible words, but there would be thousands of features, and your model would most likely overfit. You can decrease number of possible words by first taking embeddings of your words from a pretrained model (e.g. word2vec or fastText), clustering them, and use cluster labels instead of words. $\endgroup$ – David Dale Nov 2 '17 at 9:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.