An information processing apparatus for selecting, from a plurality of features, for each of which a feature value is calculated, wherein said features are extracted from input data items, one or more features that are to be used to classify the input data items, the information processing apparatus comprising: generating means for generating a plurality of combinations each having a predetermined number of features by selecting the predetermined number of features from the plurality of features for each of the plurality of combinations; first calculating means for calculating, for each of the plurality of combinations, a first evaluation value for evaluating a suitability for classification of the input data items based on the corresponding feature values of said extracted features; and characterized by further comprising: second calculating means for generating a plurality of groups of combinations, the combinations in each group including a respective one common feature, selecting the best combination with respect to the first evaluation value from combinations in each of the plurality of groups, adding a predetermined value to a second evaluation value of each feature other than the respective one common feature in the selected combination in each group and obtaining the second evaluation values for respective features by accumulating the second evaluation value in each group with respect to the plurality of groups of combinations; and selection means for selecting, on the basis of the second evaluation values for respective features, from the plurality of features, the one or more features that are to be used to classify the input data item (S205, S206). generating means for generating a plurality of combinations each having a predetermined number of features by selecting the predetermined number of features from the plurality of features for each of the plurality of combinations; first calculating means for calculating, for each of the plurality of combinations, a first evaluation value for evaluating a suitability for classification of the input data items based on the corresponding feature values of said extracted features; and characterized by further comprising: second calculating means for generating a plurality of groups of combinations, the combinations in each group including a respective one common feature, selecting the best combination with respect to the first evaluation value from combinations in each of the plurality of groups, adding a predetermined value to a second evaluation value of each feature other than the respective one common feature in the selected combination in each group and obtaining the second evaluation values for respective features by accumulating the second evaluation value in each group with respect to the plurality of groups of combinations; and selection means for selecting, on the basis of the second evaluation values for respective features, from the plurality of features, the one or more features that are to be used to classify the input data item (S205, S206). second calculating means for generating a plurality of groups of combinations, the combinations in each group including a respective one common feature, selecting the best combination with respect to the first evaluation value from combinations in each of the plurality of groups, adding a predetermined value to a second evaluation value of each feature other than the respective one common feature in the selected combination in each group and obtaining the second evaluation values for respective features by accumulating the second evaluation value in each group with respect to the plurality of groups of combinations; and selection means for selecting, on the basis of the second evaluation values for respective features, from the plurality of features, the one or more features that are to be used to classify the input data item (S205, S206).