The task of estimating “good” predictive models from available finite data is common in virtually all fields of science and engineering. The paper proposes an approach for building logistic regression models by adaptively constructing their basis functions depending on the data at hand. In this approach, to attempt to achieve acceptable model accuracy, instead of adjusting model’s maximal degree and building a model using subset selection (as done in many existing approaches), the model is built using a combinatorial search in infinite model space using four state-transition operators which not only are able to add and delete basis functions but also can modify any of the functions as training the data requires.