A rule learning method in machine learning includes distributing features to a given number of buckets based on a weight of the features which are correlated with a training example; specifying a feature with a maximum gain value as a rule based on a weight of the training example from each of the buckets; calculating a confidence value of the specified rule based on the weight of the training example; storing the specified rule and the confidence value in a rule data storage unit; updating the weights of the training examples based on the specified rule, the confidence value of the specified rule, data of the training example, and the weight of the training example; and repeating the distributing, the specifying, the calculating, the storing, and the updating, when the rule and the confidence value are to be further generated.