11
$\begingroup$

I am building a text categorizer for short sentences. In addition to telling the user "the category of the text you entered is C", I want to be able to explain why I made this decision, in a short and understandable way. For example, I don't want to tell the user "I put your sentence into a complex 3-layered neural network and that's the answer that scored the best"; I want explanations such as "Your sentence contains the words U, V and W, that are characteristic of this category, because of sentences such as X, Y and Z that appeared in the training data".

My question is: what classification algorithms are best suited for such application?

k-nearest-neighbours seems like a good candidate, because I can tell the user "Your sentence has category C because it is similar to sentences X, Y and Z that have the same category. But its performance on text categorization problems is known to be poor. I am looking for a classifie that balances performance with explanation ability.

EDIT: After spending a lot of time looking for such a classifier, I started to build a machine-learning library called limdu, that allows the classifiers to explain their decisions. It is still under development, but, it has already helped me explain to myself and my colleagues why our classifiers fail so often...

$\endgroup$
  • $\begingroup$ The point of machine learning is that you don't care what happens under the hood, you only care about the performance. The other approach failed, and that's why everyone is nowadays using these opaque statistical approaches - they're just so much better. $\endgroup$ – Yuval Filmus Jun 30 '13 at 3:01
  • 2
    $\begingroup$ @Yuval I completely disagree that the other approaches failed. They aren't optimal but they still achieve the goal of automating classification tasks well above what a human has the ability or patience to do. Opaque black boxes are not the only way to effectively do machine learning especially in situations like this where performance isn't the only consideration. Be a little more open-minded about the varying goals behind machine learning tasks. $\endgroup$ – Richard D Jun 30 '13 at 10:35
7
$\begingroup$

Although it performs poorly on text classification tasks, if you want a clear explanation of the classification reasoning, a decision tree would be your best option as it provides clear rules for how an instance is classified. A trace of the tree would provide the determining values and by analyzing the instances close to the root node, you might even be able to determine which attributes where more significant in the classification.

Another option would be to use a Naive Bayes classifier, which performs better for text mining tasks and would give you a comprehensible evaluation scheme based on probabilities that you could use to generate the "why" you're looking for, even providing an indication of which attribute values were more important than others in making the determination.

Support Vector Machines, specifically Sequential Minimum Optimization (SMO), seem to work well with these tasks and likewise provide indication of the values used to make the classification in the form of attribute weights and support vectors, but I think you may have a harder time making explicit how these weights and vectors influenced the overall classification decision.

Good luck with your project! Sounds very interesting.

$\endgroup$
  • 1
    $\begingroup$ Thanks. I also found out that online classifiers, such as perceptron and winnow, are quite good at this task (at least in my scenario), and it is easy to explain the decision by looking at the absolute value each feature adds to the classification score. For each sample, I sort the features according to the absolute value of (feature*weight), and show the first few. $\endgroup$ – Erel Segal-Halevi Jul 3 '13 at 12:20
3
$\begingroup$

I vaguely recall that Peter Norvig had an implementation of MYCIN, a medical diagnosis expert system, written in LISP in his book Paradigms of Artificial Intelligence Programming: Case Studies in Common Lisp, which did exactly this.

Maybe that is a good place to start your research. You will find the source code online, together with a rule base, however, I strongly recommend reading the text and not try to understand it from the source code alone.

You can also head directly to the page for Emycin (my emphasis),

Emycin is an expert system shell, a framework for building programs that record the knowledge of domain experts and use that knowledge to help non-expert users solve problems. It provides an interface that helps experts define data types and rules, a backwards-chaining reasoning algorithm (similar to Prolog, but with key differences), a mechanism for dealing with uncertainty, and facilities for introspection that permit users to learn what the system knows and what it is doing.

$\endgroup$
  • 2
    $\begingroup$ There is a reason why expert systems are not very popular anymore though, it's hard to code up all the rules. $\endgroup$ – adrianN Jun 28 '13 at 13:48

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.