A feature-converting device that provides good features quickly. The device includes first and second feature construction units and first and second feature selection units. The first feature construction unit receives one or more first features and constructs one or more second features that represent the results of applying a unary function to the respective first features. The first feature selection unit computes relevance between the first and second features and a target variable that includes elements associated with elements included in the first features and selects one or more third features that represent highly relevant features. The second feature construction unit constructs one or more fourth features that represent the results of applying a multi-operand function to the third features. The second feature selection unit computes the relevance between the third and fourth features and the target variable and selects at least one fifth feature that represents highly relevant features.