An $\mathbf{L^*}$ Algorithm for Deterministic Weighted Regular Languages
Extracting finite state automata (FSAs) from black-box models offers a powerful approach to gaining interpretable insights into complex model behaviors. To support this pursuit, we present a weighted variant of Angluin's (1987) $\mathbf{L^*}$ algorithm for learning FSAs. We stay faithful to the original algorithm, devising a way to exactly learn deterministic weighted FSAs whose weights support division. Furthermore, we formulate the learning process in a manner that highlights the connection with FSA minimization, showing how $\mathbf{L^*}$ directly learns a minimal automaton for the target language.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Deterministic Coreset for Lp Subspace
We introduce the first iterative algorithm for constructing a $\varepsilon$-coreset that guarantees deterministic $\ell_p$ subspace embedding for any $p \in [1,\infty)$ and any $\varepsilon > 0$. For a given full rank ma…
On the Optimal Weighted $\ell_2$ Regularization in Overparameterized Linear Regression
We consider the linear model $\mathbf{y} = \mathbf{X} \mathbf{\beta}_\star + \mathbf{\epsilon}$ with $\mathbf{X}\in \mathbb{R}^{n\times p}$ in the overparameterized regime $p>n$. We estimate $\mathbf{\beta}_\star$ via ge…
regressionEnergy-Weighted Flow Matching for Offline Reinforcement Learning
This paper investigates energy guidance in generative modeling, where the target distribution is defined as $q(\mathbf x) \propto p(\mathbf x)\exp(-\beta \mathcal E(\mathbf x))$, with $p(\mathbf x)$ being the data distri…
Offline RLreinforcement-learningReinforcement LearningReinforcement Learning (RL)Piecewise Linearity of Min-Norm Solution Map of a Nonconvexly Regularized Convex Sparse Model
It is well known that the minimum $\ell_2$-norm solution of the convex LASSO model, say $\mathbf{x}_{\star}$, is a continuous piecewise linear function of the regularization parameter $\lambda$, and its signed sparsity p…
Deterministic and Probabilistic Conditions for Finite Completability of Low-rank Multi-View Data
We consider the multi-view data completion problem, i.e., to complete a matrix $\mathbf{U}=[\mathbf{U}_1|\mathbf{U}_2]$ where the ranks of $\mathbf{U},\mathbf{U}_1$, and $\mathbf{U}_2$ are given. In particular, we invest…
Matrix Completion