A text-classifier that explains its decisions

Question

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...

Answer 1

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.

Answer 2

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.