Abstract:
An apparatus and methods for feature selection and classifier builder are disclosed. The feature selection apparatus allows for removal of bias features. The classifier builder apparatus allows building a classifier using non-biased features. The feature selection methods disclosed teach how to remove bias features. The classifier builder methods disclosed teach how to build a classifier with non-biased features.

Description:
BACKGROUND  
       [0001]     1. Field of Technology  
         [0002]     The disclosure relates generally to machine learning and classification systems.  
         [0003]     2. Glossary  
         [0004]     The following definitions are provided merely to help readers generally to understand commonly used terms in machine learning, statistics, and data mining. The definitions are not designed to be completely general but instead are aimed at the most common case. No limitation on the scope of the invention (see claims section, infra) is intended, nor should any be implied.  
         [0005]     “Data set” shall mean a schema and a set of “records” matching the schema; A “labeled data set” (or “training set”) has each record explicitly assigned to a class. A single record is also sometimes referred to as a “data item,” an “example,” or a “case.” A “label” is recorded knowledge about which class or data source the record belongs to (no ordering of “records” is assumed).  
         [0006]     “Feature value” is an attribute and its value for a given record; “feature vector” or “tuple” shall mean a list of feature values describing a “record.” 
         [0007]     “Knowledge discovery” shall mean the non-trivial process of identifying valid, novel, potentially useful, and ultimately understandable patterns in data.  
         [0008]     “Machine learning” (a sub-field of artificial intelligence) is the field of scientific study that concentrates on “induction algorithms” and other algorithms that can be said to learn; generally, it shall mean the application of “induction algorithms,” which is one step in the “knowledge discovery” process.  
         [0009]     “Model” shall mean a structure and corresponding interpretation that summarizes or partially summarizes a data set for description or prediction.  
         [0010]     3. General Background  
         [0011]     The volume of machine-readable data that is currently available, for example on the Internet, is growing at a rapid rate. In order to realize the potentially huge benefits of computer access to this data, the data may be classified into categories (or classes). Traditionally, such data has been classified manually by humans. As the amount of data has increased, however, manual data interpretation has become increasingly impractical. Recently, machine learning has been implemented to classify data automatically into one or more potential classes.  
         [0012]     Machine learning (a sub-field of artificial intelligence) is the field of scientific study that concentrates on “induction algorithms” and other algorithms that can be said to learn. Machine learning encompasses a vast array of tasks and goals. Document categorization, news filtering, document routing, personalization, and the like, constitute an area of endeavor where machine learning may greatly improve computer usage. As one example, when using electronic mail (hereinafter “e-mail”), a user may wish the computer to identify and separate junk e-mails (hereinafter “SPAM e-mails”) from the rest of the incoming e-mails. Machine learning for text classification is the cornerstone of document categorization, news filtering, document routing and personalization.  
         [0013]     “Induction algorithms” (hereinafter “Inducer”) are algorithms that take as input specific feature vectors (hereinafter “feature vectors”) labeled with their assignments to categories (hereinafter “labels”) and produce a model that generalizes data beyond the training data set. Most inducers generate/build a “model” from a training data set (hereinafter “training data”) that can then be used as classifiers, regressors, patterns for human consumption, and input to subsequent stages of “knowledge discovery” and “data mining.” 
         [0014]     A classifier provides a function that maps (or classifies) data into one of several predefined potential classes. In particular, a classifier predicts one attribute of a set of data given one or more attributes. The attribute being predicted is called the label, and the attributes used for prediction are called descriptive attributes (hereinafter “feature vectors”). After a classifier has been built, its structure may be used to classify unlabeled records as belonging to one or more of the potential classes.  
         [0015]     Many different classifiers have been proposed.  
         [0016]     The potential is great for machine learning to categorize, route, filter and search for relevant text information. However, good feature selection may improve classification accuracy or, equivalently, reduce the amount and quality of training data needed to obtain a desired level of performance, and conserve computation, storage and network resources needed for future use of the classifier. Feature selection is a pre-processing step wherein a subset of features or attributes is selected for use by the induction step. Well-chosen features based on non-biased labels may improve substantially the classification accuracy, or equivalently, reduce the amount and quality of training data items needed to obtain a desired level of performance.  
         [0017]     In general, induction algorithms generate more accurate classifiers when given larger training sets. For this reason, one would like to gather as many training examples together from free or inexpensive sources. Currently, however, when training data is included from other sources besides that of the intended target, the inducer can go astray and generate poor classifiers due to biased features within the training data. 
     
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
       [0018]      FIG. 1  is a table showing an exemplary “bag-of-words” modeling.  
         [0019]      FIGS. 2   a - c  are block diagrams of an embodiment of a feature selection system.  
         [0020]      FIG. 3  is a flow diagram of an embodiment of a feature selection system of  FIG. 2   a.    
         [0021]      FIG. 4  is a flow diagram of an embodiment of a feature selection system of  FIG. 2   b.    
         [0022]      FIG. 5  is a flow diagram of an embodiment of a feature selection system of  FIG. 2   c.    
         [0023]      FIG. 6  is a block diagram of an exemplary embodiment of a classifier building system.  
         [0024]      FIG. 7  is a flow diagram of the classifier building system of  FIGS. 2   a  and  6 .  
         [0025]      FIG. 8  is a flow diagram of the classifier building system of  FIGS. 2   b  and  6 .  
         [0026]      FIG. 9  is a flow diagram of the classifier building system of  FIGS. 2   c  and  6 .  
         [0027]      FIG. 10  is a block diagram of a computer on which feature selection system or classifier building system described herein may be performed in accordance with embodiments of the present invention. 
     
    
       [0028]     In the following description, like reference numbers are used to identify like elements. Furthermore, the drawings are intended to illustrate major features of exemplary embodiments in a diagrammatic manner. The drawings are not intended to depict every feature of every implementation nor relative dimensions of the depicted elements, and are not drawn to scale.  
       DETAILED DESCRIPTION  
       [0029]     Eliminating biased features improves accuracy for biased datasets, and may be used to enable the use of additional inexpensive datasets without the loss of accuracy that-would normally come from using biased datasets.  
         [0030]     Referring to  FIGS. 1 and 2   a , in one exemplary embodiment, a feature selection system  10  may prepare input training data  20  for machine learning phase  30  and may include a feature selection process  40  to determine with respect to the biased label  50  a set of most predictive features  60  within feature vectors  70  that make up the input training data  20 . Feature selection process  40  may, for example, be an Information Gain algorithm or a Bi-Normal Separation algorithm. Input training data  20  may, for example, correspond to a database table shown in  FIG. 1  containing columns of labels  80  and feature vectors  70  where the labels  80  may contain a biased label  50  and the feature vectors  70  may contain biased features  85  and  90 .  
         [0031]     For example, to build a classifier that is able to differentiate between SPAM and regular e-mail, a user would identify a modest number of training data for regular e-mail and SPAM, and then an inducer may learn the pattern and identify additional matches to separate the incoming e-mails. In such an e-mail classification, effective feature selection makes the learning task more accurate. The quality of the training data plays a big role in making the learning task more accurate.  
         [0032]     In e-mail classification, a user may provide the data items that consist of, for example, the user&#39;s regular e-mails as examples of non-SPAM and perhaps a friend&#39;s junk e-mails as examples of SPAM. The training data, provided by the user, are reduced into feature vectors, typically a “bag-of-words model.” A sample model is shown in  FIG. 1 , in tabular format which, in practice may have many more rows and columns. Each row represents the label and feature vector of a different e-mail. Each label column may identify a particular type or class of training data. Each feature column corresponds to a given word, e.g. the occurrence of the word “project” may be a useful feature in classifying non-SPAM. The number of potential words often exceeds the number of training data by an order of magnitude. Reducing training data into features is necessary to make the problem tractable for a classifier.  
         [0033]     In the above example, all of the friend&#39;s e-mails are SPAM while most of the user e-mails are non-SPAM, so such biased features as  85  and  90  may wrongfully lead the machine learning to classify the newly incoming e-mails containing “Friend&#39;s name” as SPAM and the newly incoming e-mails containing “User&#39;s name” as non-SPAM e-mail. A similar problem arises even if the user&#39;s e-mail contains SPAM e-mail if there is significantly more SPAM e-mail from the friend.  
         [0034]     To avoid such problems, a prior solution would have been for the user not to use the friend&#39;s free e-mail as examples of SPAM e-mail. Therefore the inability to use datasets from other free or inexpensive sources means either (1) having less training data, or (2) having to go to greater effort or expense to generate additional training examples from the intended target data source. Another somewhat obscure solution would have been for the user to go ahead and use the friend&#39;s free e-mail as long as the user also obtains additional examples of SPAM e-mail from other sources so that the inducer would not consider “Friend&#39;s Name” as a good predictive feature. However, once again this requires user&#39;s time and money to obtain additional training examples.  
         [0035]      FIG. 1  is shown as an example for clarity reasons and in reality there may be many more biased label and biased features that are not shown presently.  
         [0036]     Referring to  FIGS. 2   a  and  3 , in operation, a set of most predictive features  60  may be determined based on the biased labels  50  and from the feature vectors  70  within the input training data  20  (step  100 ). Once the set of most predictive features  60 , which in this example may contain biased features  85  and  90 , is determined, the biased features  85 ,  90  and the biased labels  50  may be removed from the input training data  20  (step  105 ) and only the remaining features  95  and non-biased labels  110 , if any, may make up the output training data  115  that may be input to machine learning phase  30 . The remaining features  95  may contain features that are within the feature vectors  70  and are not within the set of most predictive features  60 .  
         [0037]     Referring to  FIG. 2   a , the threshold value  120  may be used to determine the number of features to be included within the set of the most predictive features  60 . A threshold value  120  may be a single number that may be programmable. The set of most predictive features  60  may contain a threshold value  120  of features that may be removed from the feature vectors  70 . So, for example, if the threshold value  120  were, for example, to be set to one-hundred-five (105), the set of most predictive features  60  would contain one-hundred-five (105) features that may be removed from the feature vectors  70 .  
         [0038]     Referring to  FIG. 2   a , in another exemplary embodiment, the single, programmable threshold value  120  may represent a predictiveness value of the features to be included within the set of the most predictive features  60 . So, if the threshold value  120  were, for example, set to two-point-two (2.2), the set of most predictive features  60  would contain features with the predictiveness value of two-point-two (2.2) and above, as may be computed by an Information Gain, Bi-Normal Separation, or some other known manner method.  
         [0039]     Referring to  FIG. 2   b , in another exemplary embodiment of the feature selection system  10 , feature selection process  45  may determine a second set of the most predictive features  130  based on the non-biased labels  110  and from the remaining features  95 . In this exemplary embodiment, the output training data  115  that may be input to machine learning phase  30 , may comprise the non-biased labels  110  and the second set of most predictive features  130 . Both feature selection processes  40  and  45  may be preformed by a single algorithm like, for example, an Information Gain algorithm or a Bi-Normal Separation algorithm. Remaining features  95  may contain features that are within feature vectors  70  and are not within features within the set of most predictive features  60 .  
         [0040]     Referring to  FIGS. 2   b  and  4 , in operation, a first set of the most predictive features  60  may be determined based on the biased labels  50  and from the feature vectors  70  within the input training data  20  (step  140 ). Once the first set of the most predictive features  60  is determined, a second set of the most predictive features  130  may be determined from the non-biased labels  110  and the remaining features  95  (step  145 ). Only the second set of most predictive features  30  and non-biased labels  110 , if any, make up the output training data  115  that may be input to a machine learning phase  30 .  
         [0041]     Referring to  FIG. 2   b , in one exemplary embodiment, the threshold value  120  and a second threshold value  121  may be used to determine the number of features to be included within the first set of the most predictive features  60  and the second set of most predictive features  130 , respectfully. The threshold values  120  and  121  may be a single number that may be equal to each other. The set of the most predictive features  60  may contain the threshold value  120  of features and the second set of most predictive features  130  may contain the threshold value  121  of features. So, for example, if the threshold value  120  were to be set to thirty-two (32) and the threshold value  121  were to be set to sixty-two (62), the set of most predictive features  60  would contain thirty-two (32) features and the second set of most predictive features  130  would contain sixty-two (62) features wherein none of the 32 features within the set  60  would be included within the 62 features of the set  130 .  
         [0042]     Referring to  FIG. 2   b , in another exemplary embodiment, the single, programmable threshold value  120  and  121  may represent a predictiveness value of the features to be included within the set of the most predictive features  60  and  130 . So, for example, if the threshold value  120  were, for example, set to two-point-two (2.2), the set of most predictive features  60  would contain features with the predictiveness value of two-point-two (2.2) and above, as may be computed by Information Gain, Bi-Normal Separation, or some other method. And if the threshold value  121  were, for example, set to zero-point-zero-one (0.01), the set of the most predictive features  130  would contain features with the predictiveness value of zero-point-zero-one (0.01) and above, as may be computed by an Information Gain, a Bi-Normal Separation, or some other method.  
         [0043]     Referring to  FIG. 2   c , in another exemplary embodiment of the feature  32  selection system  10 , the nature selection process  40  may assign a predictiveness  33  value  160  to each feature within the feature vectors  70  based on the biased labels  50 . Feature selection process  45  may assign a predictiveness value  165  to each feature within feature vectors  70  based on the non-biased labels  110 . The features within the feature vectors  70  are assigned predictiveness values  160  and  165 . To prepare the output training data  115 , a mathematical algorithm  170  may be applied to the predictiveness values  160  and  165  for each of the features within feature vectors  70  to assigned a third predictivenes value  175  to each feature within feature vectors  70 . The mathematical algorithm  115  may, for example, subtract the predictiveness values  160  from predictiveness values  165  for each feature to come up with the predictivenes value  175  for each feature. Other mathematical operations could be performed to come up with the predictivenes values  175 . Subtraction is just one of many mathematical algorithms that may be implemented. The output training data  115  that may be input to a machine learning phase  30 , could comprise the non-biased labels  110  and the feature vectors  70  with the predictivenes values  175 . Both feature selection processes  40  and  45  may be preformed by a single algorithm like, for example, an Information Gain algorithm or a Bi-Normal Separation algorithm.  
         [0044]     Referring to  FIGS. 2   c  and  4 , in operation, a predictiveness value  160  may be assigned to each feature within the feature vectors  70  based on the biased labels  50  (step  180 ). A predictiveness value  165  may be assigned to each feature within feature vectors  70  based on the non-biased labels  110  (step  185 ). A mathematical algorithm may be implemented to assign predictiveness value  175  to each feature within feature vectors  70  (step  190 ). Once the predictiveness values  175  are assigned, the features with predictiveness values  175  and non-biased labels  110 , if any, may make up the output training data  115  that may be input to a machine learning phase  30 .  
         [0045]     Referring to  FIG. 2   c , in one exemplary embodiment, the threshold value  120  may be used to determine the number of features with predictiveness values  175  to be input to a machine learning phase  30 . The threshold value  120  may be a single number that may be programmable. The threshold value  120  of features may be input to a machine learning phase  30 . So, for example, if the threshold value  120  were to be set to thirty-two ( 32 ), thirty-two ( 32 ) features with predictiveness values  175  would be input to a machine learning phase  30 .  
         [0046]     Referring to  FIG. 2   c , in another exemplary embodiment, the single, programmable threshold value  120  may represent a value for predictiveness value  175  of the features to be input to a machine learning phase  30 . So, for example, if the threshold value  120  were, for example, set to seven-point-nine (7.9), the features with predictiveness values  175  of seven-point-nine (7.9) and above may be input to a machine learning phase  30 .  
         [0047]     Referring to  FIG. 6 , in one exemplary embodiment, a classifier building system  11  may include a feature selection system  10  and inducer  210 , which may, for example, generate a classifier  220  based on the output training data from feature selection system  10 . The inducer  210  may be classification algorithm such as a Naive Bayes or a Support Vector Machines, or inducer  210  may be clustering algorithms such as K-Means, or the like.  
         [0048]     Referring to  FIGS. 1, 2   a ,  6  and  7 , in operation, a set of most predictive features  60  may be determined based on the biased labels  50  and from the feature  20  vectors  70  within the input training data  20  (step  260 ). Classifier  220  may be  21  generated based on the non-biased labels  110  and features that are not within the set of most predictive features  60  (step  265 ).  
         [0049]     Referring to  FIGS. 2   b ,  6  and  8 , in operation, a first set of most predictive features  60  may be determined based on the biased labels  50  and from the feature vectors  70  within the input training data  20  (step  270 ). A second set of the most predictive features  130  may be determined from the non-biased labels  110  and the remaining features  95  (step  275 ). Classifier  220  may be generated based on the non-biased labels  110  and the second set of most predictive features  130  (step  280 ).  
         [0050]     Referring to  FIGS. 2   c ,  6  and  9 , in operation, a predictiveness value  160  may be assigned to each feature within feature vectors  70  based on the biased labels  50  (step  285 ). A predictiveness value  165  may be assigned to each feature within feature vectors  70  based on the non-biased labels  110  (step  290 ). A mathematical algorithm may be implemented to assign predictiveness value  175  to each feature within feature vectors  70  (step  295 ). Classifier  220  may be generated based on the non-biased labels  110  and features with predictiveness value  175  and above (step  300 ).  
         [0051]     Referring to  FIGS. 2   a  and  6 , in one exemplary embodiment of classifier building system  11 , an optimal threshold value  120  may be determined from a range of possible numbers  125 . By varying the threshold value  120  within the range of possible numbers  125 , the feature selection process  40  may determine a set of most predictive features  60  for each value of the threshold value  120  and inducer  210  may generate classifiers  220  for every set of output training data  115  that is generated for each threshold value  120 . To determine the optimal threshold value  120 , each of the generated classifiers  220  may be applied on data items  230 . The classifiers  220  that produce the least number of errors  240  would yield the optimal threshold value  120 .  
         [0052]     Referring to  FIGS. 2   b  and  6 , in another exemplary embodiment of classifier building system  11 , an optimal combination of the threshold values  120  and  121  may be determined from a range of possible numbers  125  and  126 , respectfully. By varying the threshold value  120  within the range of possible numbers  125 , the feature selection process  40  may determine a set of most predictive features  60  for each value of the threshold value  120 . By varying the threshold value  121  within the range of possible numbers  126 , the feature selection process  45  may determine a set of most predictive features  130  for each set of most predictive features  60  and for each value of the threshold value  121 . The inducer  210  will generate classifier rules  220  for every set of the most predictive features  130 . To determine the optimal combination of threshold value  120  and  121  each of the generated classifiers  220  may be applied on the test data items  230  and the classifier  220  that produces the least number of errors  240  would yield the optimal combination of threshold value  120  and  121 .  
         [0053]     Referring to  FIGS. 2   c  and  6 , in another exemplary embodiment of a classifier building system  11 , an optimal threshold value  120  may be determined from a range of possible numbers  125 . By varying the threshold value  120  within the range of possible numbers  125 , the mathematical algorithm  170  may assign predictiveness value  175  for each value of the threshold value  120  and inducer  210  may generate classifiers  220  for every set of output training data  115  that is generated for each threshold value  120 . To determine the optimal threshold value  120 , each of the generated classifiers  220  may be applied on the test data items  230  and the classifiers  220  that produce the least number of errors  240  would yield the optimal threshold value  120 .  
         [0054]     Referring to  FIG. 10 , in one exemplary embodiment, feature selection system  10  and classifier building system  11  may be implemented as one or more respective software modules operating on a computer  410 . Computer  410  includes a processing unit  414 , a system memory  416 , and a system bus  418  that couples processing unit  414  to the various components of computer  410 . Processing unit  414  may include one or more processors, each of which may be in the form of any one of various commercially available processors. System memory  416  includes a read only memory (ROM)  420  that stores a basic input/output system (BIOS) containing start-up routines for computer  410 , and a random access memory (RAM)  422 . System bus  418  may be a memory bus, a peripheral bus or a local bus, and may be compatible with any of a variety of bus protocols, including PCI, VESA, Microchannel, ISA, and EISA. Computer  410  also includes a hard drive  424 , a floppy drive  426 , and CD ROM drive  428  that are connected to system bus  418  by respective interfaces  430 ,  432 ,  434 . Hard drive  424 , floppy drive  426 , and CD ROM drive  428  contain respective computer-readable media disks  436 ,  438 ,  440  that provide non-volatile or persistent storage for data, data structures and computer-executable instructions. Other computer-readable storage devices (e.g., magnetic tape drives, flash memory devices, and digital video disks) also may be used with computer  410 . A user may interact (e.g., enter commands or data) with computer  410  using a keyboard  442  and a mouse  444 . Other input devices (e.g., a microphone, joystick, or touch pad) also may be provided. Information may be displayed to the user on a monitor  446 . Computer  410  also may include peripheral output devices, such as speakers and a printer. One or more remote computers  448  may be connected to computer  410  over a local area network (LAN)  452 , and one or more remote computers  450  may be connected to computer  410  over a wide area network (WAN)  454  (e.g., the Internet).  
         [0055]     The foregoing Detailed Description of exemplary and preferred embodiments is presented for purposes of illustration and disclosure in accordance with the requirements of the law. It is not intended to be exhaustive nor to limit the invention to the precise form(s) described, but only to enable others skilled in the art to understand how the invention may be suited for a particular use or implementation. The possibility of modifications and variations will be apparent to practitioners skilled in the art. Other embodiments are within the scope of the claims. No limitation is intended by the description of exemplary embodiments which may have included tolerances, feature dimensions, specific operating conditions, engineering specifications, or the like, and which may vary between implementations or with changes to the state of the art, and no limitation should be implied therefrom. Applicant has made this disclosure with respect to the current state of the art, but also contemplates advancements and that adaptations in the future may take into consideration of those advancements, namely in accordance with the then current state of the art. It is intended that the scope of the invention be defined by the claims as written and equivalents as applicable. Reference to a claim element in the singular is not intended to mean “one and only one” unless explicitly so stated. Moreover, no element, component, nor method or process step in this disclosure is intended to be dedicated to the public regardless of whether the element, component, or step is explicitly recited in the claims. No claim element herein is to be construed under the provisions of 35 U.S.C. Sec. 112, sixth paragraph, unless the element is expressly recited using the phrase “means for . . . ” and no method or process step herein is to be construed under those provisions unless the step, or steps, are expressly recited using the phrase “comprising the step(s) of . . . ”