# What classifier allows me to classify: object 1, object 2, object 3, none of those 3?

I am working on an "object recognition" project. I have 3 types of objects. I am always able to detect them but unable to correctly classify them using an SVM. Very often, for example, an "unknown" object is misclassified as object 1 with very high certainty.

My SVM only contains 3 classes actually: object 1,2 and 3, which correspond to my 3 classes. I don't have any data about the "unknown" object when training. When the object's features don't correspond to any of the 3 objects, it should be classified as "unknown."

What classifier would be the most suited for this?

Could it be that the incorrect classification happens because object 1 has 4x more training data than object 2?

My initial thoughts are to use random forest, but I'm not sure.

• Can you explain what you mean by "My SVM...contains 3 classes"? SVMs learn a decision boundary between two classes, so do you mean to say that you are using an ensemble of SVMs? – user77876 Sep 20 '17 at 20:44
• @user77876 yes it is an ensemble – LandonZeKepitelOfGreytBritn Sep 20 '17 at 20:46
• How sure are you that the unknown objects are not of any of the three classes? You say you have no information about them, thus you also don't know they can't be of the three classes, can you? Who is to say your classifier is wrong when telling you they belong to class 1? – David Ernst Sep 20 '17 at 20:49
• @DavidErnst well let's take the example of faces rather than objects. If you would have 3 users in a system and suddenly a face appears which does't belong to any of the 3 registered users it should be classified as "unknown". I don't have any data of that face. I know it is unknown and doesn't belong to the 3 classes, because I know who is in the system. – LandonZeKepitelOfGreytBritn Sep 20 '17 at 20:51
• @user77876 That's actually not true. While vanilla SVMs only work with binary boundaries, there hare been several implementations of native multiclass hinge loss already under the same umbrella of SVM. – Firebug Sep 21 '17 at 12:37

Since you know that your unknown objects in your data set are not of the three classes, as you know they are past face photos of unauthorized users, you can just treat them as a separate class. Since that fourth class is less defined as the first three and would contain very different objects, you should expect it to be scattered in a complex form over your input feature space.

Therefore, you need a classifier that can model complex non-linear decision boundaries. SVMs can do that. Unfortunately, SVMs do only binary classification and you have multiple classes. But do you? You could also see your problem as a two step procedure:

1. Decide if the object is unknown or known
2. If it is known, decide which of the three it is

It is not guaranteed that this will work better, but it's worth a shot. Step 1 would be binary which is better for SVMs. The ensembles to extend them to multiple classes come with problems. Step two is only necessary if the different authorized users have different types of access or if you need to log who was there at what time. If you only need an access/no access decision, no need for step two. For step two you could still try SVM ensembles or something else.

You should try a couple of algorithms (including those that have a two step procedure and those that don't) on the same cross validation folds and decide.

Your application scenario also can tell you whether it is a good idea or not to aggregate allowed users into one class:

• If you have only very few users that rarely if ever change, it is more practical to once aggregate them into a class and not have to retrain the classifier all the time
• If you have a long list of authorized users and correspondingly often new ones added to the list and old ones subtracted, it would not be practical to put them all in a class and retrain the entire classifier every time a user changes (though some techniques like $k$NN aren't prohibitive in that regard)
• You could do multiple single class classifications: user 1 or not? user 2 or not? etc. With 3 users that will work just fine. With 300 it would be dangerous because you inflate your chances of allowing an intruder. The user scans once and your system does 300 tests (without the user seeing there are so many tests). Each of these 300 tests would have a non-zero probability of falsely admitting someone who is not that particular user. So an intruder has 300 chances of being falsely admitted. If you raise all your 300 cutoffs in the 300 tests to counterbalance this problem, you raise the chances that authorized users will have to scan multiple times.

Regarding the higher class prevalence of object 1, that can be problematic for most algorithms (more for some than for others), but at factor 4 to 1, it shouldn't be a major concern yet.

What you should do however is take misclassification costs into consideration. If you know how much more costly it is to misclassify in one direction rather than the other and if you have an estimate of the probability of the classes, you can base your decision on this.

• The only way for me to know whether the object is unknown is by comparing it to the 3 other ones. I have the feeling that step 1 would not work in my case. If the object is not similar to the 3 objects in my system we classify it as being unknown. Did I misunderstand you? – LandonZeKepitelOfGreytBritn Sep 20 '17 at 21:28
• That's why I asked you first if you know beforehand that the unknown objects are not of the 3 classes. You said yes. Now you say no! – David Ernst Sep 20 '17 at 21:56
• sorry if I misinterpreted your question. If I would know it beforehand I wouldn t need a classifier and could just use a simple if statement in my code somehiw. It is up to the classifier to find that out and correctly classify. – LandonZeKepitelOfGreytBritn Sep 20 '17 at 22:00
• You would need a classifier if you knew it for your existing data (based on human expertise, hindsight knowledge etc.) but not for future data. This is the usual classification scenario. But in yours, you only know the 3 objects with certainty (do you?) but nothing of the other observations (not even if they are others or in fact part of the 3 classes!). In which case we are back to my initial question: Why do you not trust your classifier when it tells you the unknown is actually a class 1 object? For all you know it could be one and your classifier tells you it probably is one. – David Ernst Sep 20 '17 at 22:55
• why I don't trust it? Well see my explanation about facial recognition. I can see the difference between an unknown face and one that belongs to the system. The system is trained for those 3 faces (supervised learning) and suddenly we slow it a picture of a fourth person it has never seen and classifies it as being as person1. How do I know it's incorrect? Because after the classification I see how this face got incorrectly classified. – LandonZeKepitelOfGreytBritn Sep 21 '17 at 6:38

A possible approach is to treat your task as a series of one-class classification (OCC) [1] problems. OCC allows you to build models in the absence of negative data or if the negative class has insufficient instances to learn a model.

There are a variety of one-class classifiers, including One-Class Support Vector Machines (for example [2]).

A sketch of this approach is:

1. Train a one-class classifier for each of your classes of interest;

2. If none of the classifiers recognize the provided instance (or none meet the target threshold) then label as "unknown";

3. Else, label the instance with the class of the classifier which recognized it (or which provided the highest confidence level).

References

[1] S. S. Khan and M. G. Madden, “One-class classification: taxonomy of study and review of techniques,” Knowl. Eng. Rev., vol. 29, no. 3, pp. 345–374, Jun. 2014. DOI

[2] B. Schölkopf, J. C. Platt, J. Shawe-Taylor, A. J. Smola, and R. C. Williamson, “Estimating the Support of a High-Dimensional Distribution,” Neural Comput., vol. 13, no. 7, pp. 1443–1471, 2001. DOI

• Never heard of this method! How accurate is it? I didnt see it on wikipedia when reading about svm. – LandonZeKepitelOfGreytBritn Sep 20 '17 at 22:01
• @LandonZeKepitelOfGreytBritn The answer, as always in machine learning, is that it depends. There are a variety of one-class classifiers that you might want to investigate in order to see which, if any, will best suit your data. Without an official reference to lean back on, I would say that OCSVMs are well-regarded and worth considering as part of that investigation. – user77876 Sep 20 '17 at 22:39
• What if I need to classify 10k objects. 10k conditional branches to test, doesn't seem to be a great approach. What do you think? – LandonZeKepitelOfGreytBritn Sep 21 '17 at 12:49
• @LandonZeKepitelOfGreytBritn The answer to a lot of machine learning questions is "it depends." I would agree that the feasibility of building and utilizing 10,000 models could be different than utilizing 3 models. It comes down to understanding your data and the resources at your disposal - maybe the extra storage requirement and computational time doesn't matter to you, maybe you don't have sufficient data to build 10,000 good models. – user77876 Sep 21 '17 at 15:38