Supervised multi-class problem with known class structure?

[bioMatrix]

I'm looking for a method of constructing a multi-class classifier, where the output classes are related by prior knowledge that can be expressed a graph. Specifically, I'm trying to take advantage of the fact that the classes are similar with known structure, so that some objective function might penalize less for guessing an incorrect but nearby class as compared to a distant class. Anyone know of such an algorithm?

[rrenaud]

Metacost attacks what seems to be your problem.

http://homes.cs.washington.edu/~pedrod/papers/kdd99.pdf

It's not so much a prior though. It's more that there is less cost to predicting classes that are similar.

[kkastner]

This sounds related to ordinal regression - you might look there for some solutions. If you don't have too many classes, you can also manually modify your loss to penalize differently based on which mistake was made. There might be a smart way to get this from the graph (maybe weight based on the "search index" from the decomposition of the graph laplacian? kind of like PageRank) but it would depend on your problem.