Methods, systems, and media for automatically classifying face images are provided. In some embodiments, features of the face image to be classified for an attribute are selected, wherein each of the features corresponds to a different region of the face image and specifies one or more of a type of pixel data to be evaluated for the region, a normalization to be applied for the region, and an aggregation to be applied for the region. The face image is classified with respect to the attribute based on the features of the image, and the attribute and a confidence value are assigned to the face image based on the classifying. A query is received from a user, and the attribute is identified as corresponding to the query. The face image is determined as corresponding to the attribute, and the face image is identified to the user as corresponding to the query.