GA and ILS for optimizing the size of NFA models
Grammatical inference consists in learning a formal grammar (as a set of rewrite rules or a finite state machine). We are concerned with learning Nondeterministic Finite Automata (NFA) of a given size from samples of positive and negative words. NFA can naturally be modeled in SAT. The standard model [1] being enormous, we also try a model based on prefixes [2] which generates smaller instances. We also propose a new model based on suffixes and a hybrid model based on prefixes and suffixes. We then focus on optimizing the size of generated SAT instances issued from the hybrid models. We present two techniques to optimize this combination, one based on Iterated Local Search (ILS), the second one based on Genetic Algorithm (GA). Optimizing the combination significantly reduces the SAT instances and their solving time, but at the cost of longer generation time. We, therefore, study the balance between generation time and solving time thanks to some experimental comparisons, and we analyze our various model improvements.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Cost-Sensitive Approach to Batch Size Adaptation for Gradient Descent
In this paper, we propose a novel approach to automatically determine the batch size in stochastic gradient descent methods. The choice of the batch size induces a trade-off between the accuracy of the gradient estimate …
General ClassificationMetaOptimize: A Framework for Optimizing Step Sizes and Other Meta-parameters
This paper addresses the challenge of optimizing meta-parameters (i.e., hyperparameters) in machine learning algorithms, a critical factor influencing training efficiency and model performance. Moving away from the compu…
Optimizing Cox Models with Stochastic Gradient Descent: Theoretical Foundations and Practical Guidances
Optimizing Cox regression and its neural network variants poses substantial computational challenges in large-scale studies. Stochastic gradient descent (SGD), known for its scalability in model optimization, has recentl…
Model OptimizationregressionScaling Laws for Precision in High-Dimensional Linear Regression
Low-precision training is critical for optimizing the trade-off between model quality and training costs, necessitating the joint allocation of model size, dataset size, and numerical precision. While empirical scaling l…
Tuning Learning Rates with the Cumulative-Learning Constant
This paper introduces a novel method for optimizing learning rates in machine learning. A previously unrecognized proportionality between learning rates and dataset sizes is discovered, providing valuable insights into h…