We present a novel method to enhance training set for face detection with nonlinearly generated examples from the original data. The motivation is from Support Vector Machines (SVM) that, for classification problems, examples lying close to class boundary usually have more influence and thus are more informative than those far from the boundary. We utilize a nonlinear technique - reduced set (RS) method and a new image distance metric to generate new examples, and then add them to the original collected database to enhance it. Extensive experiments show that the proposed approach has an encouraging performance.