Suggestion for method/framework to use for short string classification with "complex" ouput

Question

What I am trying to do :

1. I have short text strings (max 128 total chars in length) which I would like to classify (or use for prediction) as belonging to a particular type of output (more on the output structure follows).

2. The output is a set of sets of categorical labels , just to make things a little bit clearer , if I had two sets, one composed of geometric shapes and one of colors , the output I would like to predict/classify would look like : class 1 = { {circle,red} , {square,black} } class 2 = { {circle,blue} , {square,black} , {rectangle , yellow} } ...

3. In my particular case the "geometric shapes" has cardinality around 120 and the "color" has cardinality around 60.

4. The output are dependent on each other, that is ,a certain set of predicted geometric shapes influences the color that can be assigned to each individual shape. Also not all combinations of shapes and corresponding colors are allowed.

What I have investigated so far :

1. Direct Multi-class classification (svm) : not practical, as there are too many combinations of the output space.
2. 2 Multi-class classifications : first predict shape , than predict color for each predicted shape. The problem with this is that I am not sure how to include the constraints that certain shape combinations are more probable than others and that the final colors do not depend on a single shape but all the shapes detected in the first classification step.
3. I am checking publications regarding multi-label classification but this still does not help me in resolving the {shape,color} combination.
4. Structured output svm , mostly used in computer vision : however this implies "inventing" a feature mapping function and loss functions and this is quite beyond me. I would like as much as possible to use ready-made code/libraries/toolboxes...

I would be very thankful to anyone for suggestions/publications/comments etc. that could at least put me on the right track.

Answer 1

First of all: What is the size of your data? Then you should probably reduce the number of labels (so far 120 * 60 = 7200 is a large number for output). But you could encode them with label = 1, ..., k => your classes)

Do you want a multi-label classification or a multi-class classification (there is a difference, allthough you can do both by extending a binary classifier for each output)

Maybe you should hear "Random Forest", "Support Vector Machine", "Naive Bayes Classifier" or "k-NN"

There are dozen of algorithms for classification....