A binary classlficktion Washington D.C. problem: solution: classifier(w)is 101st Congressional learned for each District. image,and if there are,return category.Using missile range. an encoding of SMO to train the national park. their location. linear SVM takes an illegal inmigrant. The encoding in average of 0.26 this system is to CPU seconds per fit each face in a category (averaged bounding box over 118 categories) defined by the on a 266-MHz Pentium II running Windows offer great potential to support flexible,dy- image coordinates of the corners. NT.Other learning methods are 20 to 50 namic,and personalized information access Face detection as a computer-vision task times slower.New instances are classified by and management in a wide variety of tasks. has many applications.It has direct rele- computing a score for each document ( vance to the face-recognition problem,be- and comparing the score with a leamed cause the first important step of a fully au- threshold.New documents exceeding the References tomatic human face recognizer is usually threshold are said to belong to the category. 1. D.D.Lewis and P.Hayes,special issue of identifying and locating faces in an un- The learned SVM classifiers are intu- ACM Trans.Information Systems,Vol.12. known image.Face detection also has po- itively reasonable.The weight vector for No.1.July 1994. tential application in human-computer in- the category“interest'”includes the words Y.Yang,"An Evaluation of Statistical Ap- proaches to Text Categorization,"to be terfaces,surveillance systems,and census prime (.70),rate (.67),interest (.63),rates published in.J.Information Retrieval,1998 systems,for example. (.60),and discount(.46),with large posi- T.Joachims,"Text Categorization with Sup- For this discussion.face detection is also tive weights,and the words group (-24). port Vector Machines:Leaming with Many nteresting as an example of a natural and year (-25),sees(-.33)world (-.35),and Relevant Features,"to be published in Proc. challenging problem for demonstrating and dlrs(-71),with large negative weights. 10th European Conf.Machine Leaming ECML),Springer-Verlag,1998;http:// testing the potentials of SVMs.Many other As is typical in evaluating text catego- www-ai.cs.uni-dortmund.de/PERSONAL/ real-world object classes and phenomena rization,we measure classification accu- joachims.html/Joachims 97b.ps.gz. share similar characteristics-for example, racy using the average of precision and S.Dumais et al.,"Inductive Learning Algo- tumor anomalies in MRI scans and struc- recall (the so-called breakeven point).Pre- rithms and Representations for Text Catego- tural defects in manufactured parts.A suc- cision is the proportion of items placed in rization,to be published in Proc.Conf.Infor mation and Knowledge Management,1998; cessful and general methodology for find- the category that are really in the category, http://research.microsoft.com/-sdumais/ ing faces using SVMs should generalize and recall is the proportion of items in the cikm98.doc. well for other spatially well-defined pat- category that are actually placed in the cat- G.Salton and M.McGill,Introduction to tern-and feature-detection problems. egory.Table 1 summarizes microaveraged Modern Information Retrieval,McGraw Face detection.like most obiect-detection Hill.New York.1983. breakeven performance for five learning problems,is a difficult task because of the J.Platt,"Fast Training of SVMs Using Se- algorithms explored by my colleagues and quential Minimal Optimization,"to be pub significant pattern variations that are hard to I explored for the 10 most frequent cate- lished in Advances in Kernel Methods- parameterize analytically.Some common gories,as well as the overall score for all Support Vector Machine Learning,B. sources of pattern variations are facial ap- 118 categories.4 Scholkpf,C.Burges,and A.Smola,eds. pearance,expression,presence or absence of Linear SVMs were the most accurate MIT Press,Cambridge,Mass.,1998. common structural features such as glasses or method,averaging 91.3%for the 10 most a moustache,and light-source distribution. frequent categories and 85.5%over all 118 This system works by testing candidate categories.These results are consistent Applying SVMs to face detection image locations for local patterns that ap- with Joachims'results in spite of substan- pear like faces,using a classification proce- tial differences in text preprocessing,term Edgar Osuna.MIT Center for Biological and dure that determines whether a given local weighting,and parameter selection,sug- Computational Learning and Operations Re- image pattern is a face.Therefore.our ap- gesting that the SVM approach is quite search Center proach comes at the face-detection problem robust and generally applicable for text- This essay introduces an SMV applica- as a classification problem given by exam- categorization problems.3 tion for detecting vertically oriented and ples of two classes:faces and nonfaces. Figure 5 shows a representative ROC unoccluded frontal views of human faces in curve for the category“grain.”We generate gray-level images.This application handles Previous systems this curve by varying the decision threshold faces over a wide range of scales and works Researchers have approached the face- to produce higher precision or higher re- under different lighting conditions,even detection problem with different techniques call,depending on the task.The advantages with moderately strong shadows. in the last few years,including neural net- of the SVM can be seen over the entire We can define the face-detection prob- works,2 detection of face features and use recall-precision space lem as follows.Given as input an arbitrary of geometrical constraints,3 density estima- image,which could be a digitized video tion of the training data,labeled graphs,s Summary signal or a scanned photograph,determine and clustering and distribution-based mod- In summary,inductive learning methods whether there are any human faces in the eling.6.7 The results of Kah-Kay Sung and JULY/AUGUST 1998 23JULY/AUGUST 1998 23 classifier (→w ) is learned for each category. Using SMO to train the linear SVM takes an average of 0.26 CPU seconds per category (averaged over 118 categories) on a 266-MHz Pentium II running Windows NT. Other learning methods are 20 to 50 times slower. New instances are classified by computing a score for each document ( →x ⋅ →w ) and comparing the score with a learned threshold. New documents exceeding the threshold are said to belong to the category. The learned SVM classifiers are intu￾itively reasonable. The weight vector for the category “interest” includes the words prime (.70), rate (.67), interest (.63), rates (.60), and discount (.46), with large posi￾tive weights, and the words group (–.24), year (–.25), sees (–.33) world (–.35), and dlrs (–.71), with large negative weights. As is typical in evaluating text catego￾rization, we measure classification accu￾racy using the average of precision and recall (the so-called breakeven point). Pre￾cision is the proportion of items placed in the category that are really in the category, and recall is the proportion of items in the category that are actually placed in the cat￾egory. Table 1 summarizes microaveraged breakeven performance for five learning algorithms explored by my colleagues and I explored for the 10 most frequent cate￾gories, as well as the overall score for all 118 categories.4 Linear SVMs were the most accurate method, averaging 91.3% for the 10 most frequent categories and 85.5% over all 118 categories. These results are consistent with Joachims’results in spite of substan￾tial differences in text preprocessing, term weighting, and parameter selection, sug￾gesting that the SVM approach is quite robust and generally applicable for text￾categorization problems.3 Figure 5 shows a representative ROC curve for the category “grain.” We generate this curve by varying the decision threshold to produce higher precision or higher re￾call, depending on the task. The advantages of the SVM can be seen over the entire recall-precision space. Summary In summary, inductive learning methods offer great potential to support flexible, dy￾namic, and personalized information access and management in a wide variety of tasks. References 1. D.D. Lewis and P. Hayes, special issue of ACM Trans. Information Systems, Vol. 12, No. 1, July 1994. 2. Y. Yang, “An Evaluation of Statistical Ap￾proaches to Text Categorization,” to be published in J. Information Retrieval, 1998. 3. T. Joachims, “Text Categorization with Sup￾port Vector Machines: Learning with Many Relevant Features,” to be published in Proc. 10th European Conf. Machine Learning (ECML), Springer-Verlag, 1998; http:// www-ai.cs.uni-dortmund.de/PERSONAL/ joachims.html/Joachims_97b.ps.gz. 4. S. Dumais et al., “Inductive Learning Algo￾rithms and Representations for Text Catego￾rization, to be published in Proc. Conf. Infor￾mation and Knowledge Management, 1998; http://research.microsoft.com/~sdumais/ cikm98.doc. 5. G. Salton and M. McGill, Introduction to Modern Information Retrieval, McGraw Hill, New York, 1983. 6. J. Platt, “Fast Training of SVMs Using Se￾quential Minimal Optimization,” to be pub￾lished in Advances in Kernel Methods— Support Vector Machine Learning, B. Schölkpf, C. Burges, and A. Smola, eds., MIT Press, Cambridge, Mass., 1998. Applying SVMs to face detection Edgar Osuna, MIT Center for Biological and Computational Learning and Operations Re￾search Center This essay introduces an SMV applica￾tion for detecting vertically oriented and unoccluded frontal views of human faces in gray-level images. This application handles faces over a wide range of scales and works under different lighting conditions, even with moderately strong shadows. We can define the face-detection prob￾lem as follows. Given as input an arbitrary image, which could be a digitized video signal or a scanned photograph, determine whether there are any human faces in the image, and if there are, return an encoding of their location. The encoding in this system is to fit each face in a bounding box defined by the image coordinates of the corners. Face detection as a computer-vision task has many applications. It has direct rele￾vance to the face-recognition problem, be￾cause the first important step of a fully au￾tomatic human face recognizer is usually identifying and locating faces in an un￾known image. Face detection also has po￾tential application in human-computer in￾terfaces, surveillance systems, and census systems, for example. For this discussion, face detection is also interesting as an example of a natural and challenging problem for demonstrating and testing the potentials of SVMs. Many other real-world object classes and phenomena share similar characteristics—for example, tumor anomalies in MRI scans and struc￾tural defects in manufactured parts. A suc￾cessful and general methodology for find￾ing faces using SVMs should generalize well for other spatially well-defined pat￾tern- and feature-detection problems. Face detection, like most object-detection problems, is a difficult task because of the significant pattern variations that are hard to parameterize analytically. Some common sources of pattern variations are facial ap￾pearance, expression, presence or absence of common structural features such as glasses or a moustache, and light-source distribution. This system works by testing candidate image locations for local patterns that ap￾pear like faces, using a classification proce￾dure that determines whether a given local image pattern is a face. Therefore, our ap￾proach comes at the face-detection problem as a classification problem given by exam￾ples of two classes: faces and nonfaces. Previous systems Researchers have approached the face￾detection problem with different techniques in the last few years, including neural net￾works,1,2 detection of face features and use of geometrical constraints,3 density estima￾tion of the training data,4 labeled graphs,5 and clustering and distribution-based mod￾eling. 6,7 The results of Kah-Kay Sung and