4
$\begingroup$

I am building a natural language understanding component for a dialog system. The input is a natural language sentence (usually a short one), and the output should be a set of zero or more classes from a pre-specified set. For example: 

input: "I offer a salary of 20000 per month for work as a programmer with a company car"
output: ["OFFER(Salary=20000)", "OFFER(Job=programmer)", "OFFER(Car=yes)"]

I collected some examples from real dialogs, in order to train a classifier. My current approach is:

  • Features: I take the words of each sentence as features (I also tried word bi-grams and letter n-grams but the performance was worse).
  • Training: I train a separate binary classifier for each class. As positive examples, I take all sentences that have this class, and as negative examples, I take all sentences that don't have this class.
  • Running: I run each of the binary classifiers on the new sample, and return the set of classes that correspond to the classifiers that answered 'yes'.

This approach lead to too many false positives. Since my dataset contains many sentences with many classes (about 6 classes per sentence), the classifier gets confused between words that belong to different classes. For example, it takes the words "work as a programmer" as positive signal to the class "OFFER(Salary=20000)", because they appeared together in many training samples.

So, I edited my training data and separated each sample sentence to several sub-sentences, such that each sub-sentence matches just one class:

input: "I offer a salary of 20000 per month"
output: ["OFFER(Salary=20000)"]
input: "for work as a programmer"
output: ["OFFER(Job=programmer)"]
input: "with a company car"
output: ["OFFER(Car=yes)"]

The new approach lead to too many false negatives: since every sentence is a negative example of all classes except its own class, the classifier takes the words "a salary of 20000" as negative signal to the class "OFFER(Job=programmer)". Therefore, for compound sentences such as "I offer a salary of 20000 per month for work as a programmer with a company car", the classifier finds a single class and misses all other classes.

I also created a mixed dataset - half of the one-class samples and half of the multi-class samples (the other half I used for testing), and got much better result. However, this approach seems like a hack, and I would like to know if there is a more professional approach.

Any suggestions for solution will be welcome...

NOTE: I use the winnow classification algorithm, which currently has the best score (I also tried Naive Bayes, SVM, neural network and perceptron).

--

Some numbers:

  • Performance of classifier trained on multi-class sentences and tested on single-class sentences: Precision=69% Recall=97% F1=81%
  • Performance of classifier trained on single-class sentences and tested on multi-class sentences: Precision=99% Recall=32% F1=48%
  • Performance of classifier trained on a mixed dataset (1/2 single-class and 1/2 multi-class), and tested on the other half: Precision=88% Recall=89% F1=89%
Improve this question
$\endgroup$
1
  • 3
    $\begingroup$ It might help just to change your point of view. It strikes me that this is not a classification problem, but rather it is an attribution problem. The distinction is that each phrase or sentence no longer needs to be put into one category, but rather can be assigned multiple attributes. From this point of view the problem turns into a collection of (practically) independent problems: you need a job description classifier, a salary identifier, and so on, each of which could be developed and run independently of each other (and even use different methods). $\endgroup$
    – whuber ♦
    Commented Jul 10, 2013 at 19:02

3 Answers 3

Reset to default
2
$\begingroup$

The approach of training the classifier on single-class "sentences" (actually, not necessarily sentences, but phrases) is promising, but where it breaks down is you are training the classifier on a different type of data than what you're using it on.

You need a pre-processing step that breaks the sentences down into phrases, and use that same phrase-level data for both training and actual classification. Then, in your reporting step, you could aggregate all of the positive phrase-level results to the level of the input sentence (each sentence is a list of phrases with some positive identification of classes, and so you would simply combine all of the phrase-level positive results).

This approach isn't perfect either - it will often fail properly account for contextual information like negation and pronouns. But, it's the next logical step if you're building it from the ground up.

Improve this answer
$\endgroup$
4
  • $\begingroup$ The problem is, I don't have an automatic way to split a sentence into phrases... I could do it manually in my annotated dataset, but I need the system to work automatically on new sentences. $\endgroup$
    – Erel Segal-Halevi
    Commented Jul 7, 2013 at 4:04
  • $\begingroup$ Agreed - you need an automated system for new sentences, but you also need to use the same system on your annotated data. Many people have worked on this problem already and published packages such as the Stanford Parser (nlp.stanford.edu/software/lex-parser.shtml) and the Parser package in the Natural Language Toolkit (nltk.org/api/nltk.parse.html#module-nltk.parse) $\endgroup$
    – Jonathan
    Commented Jul 7, 2013 at 18:52
  • $\begingroup$ I already tried those tools... the problem is that they are very noisy, especially when the sentences have spelling and grammar errors (as is common, for example, with ASR output). Therefore I now try a purely machine-learning approach. $\endgroup$
    – Erel Segal-Halevi
    Commented Jul 9, 2013 at 19:18
  • 1
    $\begingroup$ Ah - I didn't realize that. It still seems that the core problem is that a method which works very well on short phrases individually fails when confronted with longer sentences. You mentioned you tried using n-grams as a feature... perhaps you could try using them as a unit of analysis with words as a feature. And, aggregate findings across n-grams within a sentence. $\endgroup$
    – Jonathan
    Commented Jul 10, 2013 at 17:20
2
$\begingroup$

I now discovered that this topic is called multi-label classification. Recently, many new methods have been developed for this task.

Improve this answer
$\endgroup$
1
$\begingroup$

2 disconnected thoughts:

  • You don't say if the inputs are all from the narrow domain of hiring, interviews, job offers, benefits, descriptions, etc. If so a gazetteer approach may be fruitful, after building a list of a few hundred significant words/phrases, if it's not one of those infinite acronyms/synonyms domains. A good place to start is to search ACL anthology on "gazette", and lucene/SOLR text indexing has many capabilities in this area

http://aclweb.org/anthology-new/

  • (A long shot but my jog memories) there's also a large body of research on parsing twitter 140 character messages for named entity recognition and topicality. This might not have anything to do with the type of data you're seeing, but just a thought.
Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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