1. A feature conversion device comprising: a learning pair selector that inputs a plurality of learning feature vectors thereto and selects a plurality of pairs of learning feature vectors from the learning feature vectors; a bit code converter that transforms the learning feature vector using a transformation matrix and converts the transformed learning feature vector into a bit code; a cost function calculator that calculates a cost function indicating a sum of differences between a distance between the learning feature vectors input to the learning pair selector and a distance between the bit codes into which the transformed learning feature vectors are converted by the bit code converter with respect to all the pairs of learning feature vectors; and a transformation matrix update unit that selects an element of the transformation matrix used in the bit code converter and substitutes a substitution candidate for the selected element to update the transformation matrix, wherein the bit code converter transforms the learning feature vector using the transformation matrix updated by the transformation matrix update unit and converts the transformed learning feature vector into a bit code, the cost function calculator fixes the element by selecting one element from the substitution candidate and the original element based on the cost function when the transformation matrix update unit substitutes the substitution candidate for the element of the transformation matrix, the transformation matrix update unit selects the element while sequentially changing the elements and the cost function calculator fixes the selected element every time the transformation matrix update unit selects the element, thereby finally fixing the optimum transformation matrix, and the substitution candidate is specified such that a speed of transformation processing that the bit code converter performs using the transformation matrix is enhanced.