Grammatical inference as a principal component analysis problem

ABSTRACT

One of the main problems in probabilistic grammatical inference consists in inferring a stochastic language, i.e. a probability distribution, in some class of probabilistic models, from a sample of strings independently drawn according to a fixed unknown target distribution p. Here, we consider the class of rational stochastic languages composed of stochastic languages that can be computed by multiplicity automata, which can be viewed as a generalization of probabilistic automata. Rational stochastic languages p have a useful algebraic characterization: all the mappings up: v → p(uv) lie in a finite dimensional vector subspace V_p* of the vector space ℝ ⟨⟨Σ⟩⟩ composed of all real-valued functions defined over Σ*. Hence, a first step in the grammatical inference process can consist in identifying the subspace V_p*. In this paper, we study the possibility of using Principal Component Analysis to achieve this task. We provide an inference algorithm which computes an estimate of this space and then build a multiplicity automaton which computes an estimate of the target distribution. We prove some theoretical properties of this algorithm and we provide results from numerical simulations that confirm the relevance of our approach.

REFERENCES

• 1: Amos Beimel , Francesco Bergadano , Nader H. Bshouty , Eyal Kushilevitz , Stefano Varricchio, Learning functions represented as multiplicity automata, Journal of the ACM (JACM), v.47 n.3, p.506-530, May 2000 [doi>10.1145/337244.337257]
• 2: Rafael C. Carrasco , José Oncina, Learning Stochastic Regular Grammars by Means of a State Merging Method, Proceedings of the Second International Colloquium on Grammatical Inference and Applications, p.139-152, September 21-23, 1994
• 3: Clark, A., Florêncio, C. C., & Watkins, C. (2006). Languages as hyperplanes: Grammatical inference with string kernels. 17th European Conference on Machine Learning (pp. 90--101). Springer.
• 4: François Denis , Yann Esposito, On Rational Stochastic Languages, Fundamenta Informaticae, v.86 n.1,2, p.41-77, October 2008
• 5: Denis, F., Esposito, Y., & Habrard, A. (2006). Learning rational stochastic languages. 19th Conference on Learning Theory (pp. 274--288). Springer.
• 6: Shawe-Taylor, J., Cristianini, N., & Kandola, J. S. (2001). On the concentration of spectral properties. Advances in Neural Information Processing Systems, 14 (pp. 511--517). MIT Press.
• 7: Alex Smola , Arthur Gretton , Le Song , Bernhard Schölkopf, A Hilbert Space Embedding for Distributions, Proceedings of the 18th international conference on Algorithmic Learning Theory, October 01-04, 2007, Sendai, Japan [doi>10.1007/978-3-540-75225-7_5]
• 8: Franck Thollard , Pierre Dupont , Colin de la Higuera, Probabilistic DFA Inference using Kullback-Leibler Divergence and Minimality, Proceedings of the Seventeenth International Conference on Machine Learning, p.975-982, June 29-July 02, 2000

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.3 Deduction and Theorem Proving
          Subjects: Inference engines

Additional Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Statistical computing; Stochastic processes; Probabilistic algorithms (including Monte Carlo)

  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.0 General
  I.6 SIMULATION AND MODELING
      I.6.4 Model Validation and Analysis
      I.6.5 Model Development
          Subjects: Modeling methodologies

General Terms:
Algorithms, Design, Performance, Theory