×

zbMATH — the first resource for mathematics

Latent semantic analysis of game models using LSTM. (English) Zbl 1423.68086
Summary: We are proposing a method for identifying whether the observed behaviour of a function at an interface is consistent with the typical behaviour of a particular programming language. This is a challenging problem with significant potential applications such as in security (intrusion detection) or compiler optimisation (profiling). To represent behaviour we use game semantics, a powerful method of semantic analysis for programming languages. It gives mathematically accurate models (’fully abstract’) for a wide variety of programming languages. Game-semantic models are combinatorial characterisations of all possible interactions between a term and its syntactic context. Because such interactions can be concretely represented as sets of sequences, it is possible to ask whether they can be learned from examples. Concretely, we are using LSTM, a technique which proved effective in learning natural languages for automatic translation and text synthesis, to learn game-semantic models of sequential and concurrent versions of Idealised Algol (IA), which are algorithmically complex yet can be concisely described. We will measure how accurate the learned models are as a function of the degree of the term and the number of free variables involved. Finally, we will show how to use the learned model to perform latent semantic analysis between concurrent and sequential Idealised Algol.

MSC:
68N15 Theory of programming languages
68Q55 Semantics in the theory of computing
68T05 Learning and adaptive systems in artificial intelligence
Software:
GNMT; Haskell; QuickCheck
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Abramsky, Samson; Jagadeesan, Radha; Malacaria, Pasquale, Full abstraction for PCF, Inf. Comput., 163, 2, 409-470, (2000) · Zbl 1006.68028
[2] Abramsky, Samson; Jung, Achim, Domain theory, (Handbook of Logic in Computer Science, vol. 3, (1994)), 1-168
[3] Abramsky, Samson; McCusker, Guy, Linearity, sharing and state: a fully abstract game semantics for Idealized Algol with active expressions, Electron. Notes Theor. Comput. Sci., 3, 2-14, (1996) · Zbl 0909.68029
[4] Abramsky, Samson; McCusker, Guy, Game semantics, (Computational Logic, (1999), Springer), 1-55 · Zbl 0961.68080
[5] Abramsky, Samson, Semantics of interaction: an introduction to game semantics, (Pitts, A.; Dybjeer, P., Semantics and Logics of Computation, (1997), Cambridge University Press), 1-33 · Zbl 0938.91500
[6] Baroni, Marco; Dinu, Georgiana; Kruszewski, Germán, Don’t count, predict! A systematic comparison of context-counting vs. context-predicting semantic vectors, (Proceedings of the 52nd Annual Meeting of the Association for Computational Linguistics. Proceedings of the 52nd Annual Meeting of the Association for Computational Linguistics, ACL 2014, June 22-27, 2014, Baltimore, MD, USA. Proceedings of the 52nd Annual Meeting of the Association for Computational Linguistics. Proceedings of the 52nd Annual Meeting of the Association for Computational Linguistics, ACL 2014, June 22-27, 2014, Baltimore, MD, USA, Long Papers, vol. 1, (2014)), 238-247
[7] Bengio, Y.; Simard, P.; Frasconi, P., Learning long-term dependencies with gradient descent is difficult, IEEE Trans. Neural Netw., 5, 2, 157-166, (1994)
[8] Bengio, Yoshua; Ducharme, Réjean; Vincent, Pascal; Jauvin, Christian, A neural probabilistic language model, J. Mach. Learn. Res., 3, 1137-1155, (Feb. 2003)
[9] Brown, Peter F.; Della Pietra, Stephen; Della Pietra, Vincent J.; Lai, Jennifer C.; Mercer, Robert L., An estimate of an upper bound for the entropy of English, Comput. Linguist., 18, 1, 31-40, (1992)
[10] Caliskan, Aylin; Bryson, Joanna J.; Narayanan, Arvind, Semantics derived automatically from language corpora contain human-like biases, Science, 356, 6334, 183-186, (2017)
[11] Claessen, Koen; Hughes, John, QuickCheck: a lightweight tool for random testing of Haskell programs, (Proceedings of the Fifth ACM SIGPLAN International Conference on Functional Programming (ICFP ’00). Proceedings of the Fifth ACM SIGPLAN International Conference on Functional Programming (ICFP ’00), Montreal, Canada, September 18-21, 2000, (2000)), 268-279
[12] De Mulder, Wim; Bethard, Steven; Moens, Marie-Francine, A survey on the application of recurrent neural networks to statistical language modeling, Comput. Speech Lang., 30, 1, 61-98, (2015)
[13] Fan, Yuchen; Qian, Yao; Xie, Feng-Long; Soong, Frank K., TTS synthesis with bidirectional LSTM based recurrent neural networks, (Fifteenth Annual Conference of the International Speech Communication Association, (2014)), 1964-1968
[14] Francez, Nissim; Hoare, C. A.R.; Lehmann, Daniel J.; de Roever, Willem P., Semantics of nondeterminism, concurrency, and communication, J. Comput. Syst. Sci., 19, 3, 290-308, (1979) · Zbl 0434.68066
[15] Gabbay, Murdoch; Ghica, Dan R., Game semantics in the nominal model, Electron. Notes Theor. Comput. Sci., 286, 173-189, (2012) · Zbl 1342.68195
[16] Ghica, Dan R., Applications of game semantics: from program analysis to hardware synthesis, (Proceedings of the 24th Annual IEEE Symposium on Logic in Computer Science. Proceedings of the 24th Annual IEEE Symposium on Logic in Computer Science, LICS 2009, 11-14 August 2009, Los Angeles, CA, USA, (2009)), 17-26
[17] Ghica, Dan R.; Bakewell, Adam, Clipping: a semantics-directed syntactic approximation, (Proceedings of the 24th Annual IEEE Symposium on Logic in Computer Science. Proceedings of the 24th Annual IEEE Symposium on Logic in Computer Science, LICS 2009, 11-14 August 2009, Los Angeles, CA, USA, (2009)), 189-198 · Zbl 1234.68069
[18] Ghica, Dan R.; McCusker, Guy, The regular-language semantics of second-order idealized \(A_{L G O L}\), Theor. Comput. Sci., 309, 1-3, 469-502, (2003) · Zbl 1070.68083
[19] Ghica, Dan R.; Murawski, Andrzej S., Compositional model extraction for higher-order concurrent programs, (Tools and Algorithms for the Construction and Analysis of Systems, Proceedings. Tools and Algorithms for the Construction and Analysis of Systems, Proceedings, 12th International Conference, TACAS 2006 Held as Part of the Joint European Conferences on Theory and Practice of Software, ETAPS 2006 Vienna, Austria, March 25-April 2, 2006, (2006)), 303-317 · Zbl 1180.68115
[20] Ghica, Dan R.; Murawski, Andrzej S., Angelic semantics of fine-grained concurrency, Ann. Pure Appl. Logic, 151, 2-3, 89-114, (2008) · Zbl 1133.68011
[21] Ghica, Dan R.; Murawski, Andrzej S.; Luke Ong, C.-H., Syntactic control of concurrency, Theor. Comput. Sci., 350, 2-3, 234-251, (2006) · Zbl 1086.68087
[22] Ghica, Dan R.; Tzevelekos, Nikos, A system-level game semantics, Electron. Notes Theor. Comput. Sci., 286, 191-211, (2012) · Zbl 1342.68196
[23] Grefenstette, Edward; Dinu, Georgiana; Zhang, Yao-Zhong; Sadrzadeh, Mehrnoosh; Baroni, Marco, Multi-step regression learning for compositional distributional semantics, (Proceedings of the 10th International Conference on Computational Semantics. Proceedings of the 10th International Conference on Computational Semantics, IWCS 2013, March 19-22, 2013, University of Potsdam, Potsdam, Germany, (2013)), 131-142, Available at
[24] Harman, Mark; Afshin Mansouri, S.; Zhang, Yuanyuan, Search-based software engineering: trends, techniques and applications, ACM Comput. Surv., 45, 1, 11:1-11:61, (2012)
[25] Harmer, Russell; McCusker, Guy, A fully abstract game semantics for finite nondeterminism, (14th Annual IEEE Symposium on Logic in Computer Science. 14th Annual IEEE Symposium on Logic in Computer Science, Trento, Italy, July 2-5, 1999, (1999)), 422-430
[26] Hochreiter, Sepp; Schmidhuber, Jürgen, Long short-term memory, Neural Comput., 9, 8, 1735-1780, (1997)
[27] Hyland, J. M.E.; Luke Ong, C.-H., On full abstraction for PCF: I, II, and III, Inf. Comput., 163, 2, 285-408, (2000) · Zbl 1006.68027
[28] Isberner, Malte; Howar, Falk; Steffen, Bernhard, Learning register automata: from languages to program structures, Mach. Learn., 96, 1-2, 65-98, (2013) · Zbl 1317.68097
[29] Joulin, Armand; Mikolov, Tomas, Inferring algorithmic patterns with stack-augmented recurrent nets, (Advances in Neural Information Processing Systems, (2015)), 190-198
[30] Landauer, Thomas K., Latent Semantic Analysis, (2006), Wiley Online Library
[31] Lipton, Zachary C.; Berkowitz, John; Elkan, Charles, A critical review of recurrent neural networks for sequence learning, (2015)
[32] Markou, Markos; Singh, Sameer, Novelty detection: a review - part 1: statistical approaches, Signal Process., 83, 12, 2481-2497, (2003) · Zbl 1145.94402
[33] Markou, Markos; Singh, Sameer, Novelty detection: a review - part 2: neural network based approaches, Signal Process., 83, 12, 2499-2521, (2003) · Zbl 1145.94403
[34] Murawski, Andrzej S., About the undecidability of program equivalence in finitary languages with state, ACM Trans. Comput. Log., 6, 4, 701-726, (2005) · Zbl 1367.68024
[35] Murawski, Andrzej S.; Walukiewicz, Igor, Third-order Idealized Algol with iteration is decidable, Theor. Comput. Sci., 390, 2-3, 214-229, (2008) · Zbl 1134.68017
[36] O’Hearn, Peter; Tennent, Robert, ALGOL-Like Languages, (2013), Springer Science & Business Media · Zbl 0882.68023
[37] Olah, Christopher, Understanding LSTM networks
[38] Luke Ong, C.-H., Observational equivalence of 3rd-order Idealized Algol is decidable, (Proceedings. Proceedings, 17th IEEE Symposium on Logic in Computer Science (LICS 2002), 22-25 July 2002, Copenhagen, Denmark, (2002)), 245-256
[39] Pitts, Andrew M., Operational semantics and program equivalence, (Applied Semantics, Advanced Lectures. Applied Semantics, Advanced Lectures, International Summer School, APPSEM 2000, Caminha, Portugal, September 9-15, 2000, (2000)), 378-412 · Zbl 1065.68067
[40] Pitts, Andrew M., Nominal Sets: Names and Symmetry in Computer Science, (2013), Cambridge University Press · Zbl 1297.68008
[41] Plotkin, Gordon D., Call-by-name, call-by-value and the lambda-calculus, Theor. Comput. Sci., 1, 2, 125-159, (1975) · Zbl 0325.68006
[42] Plotkin, Gordon D., LCF considered as a programming language, Theor. Comput. Sci., 5, 3, 223-255, (1977) · Zbl 0369.68006
[43] Reynolds, John C., The Essence of Algol, 67-88, (1997), Birkhäuser Boston: Birkhäuser Boston Boston, MA
[44] Tennent, Robert D., The denotational semantics of programming languages, Commun. ACM, 19, 8, 437-453, (1976) · Zbl 0337.68010
[45] Wu, Yonghui; Schuster, Mike; Chen, Zhifeng; Le, Quoc V.; Norouzi, Mohammad; Macherey, Wolfgang; Krikun, Maxim; Cao, Yuan; Gao, Qin; Macherey, Klaus, Google’s neural machine translation system: bridging the gap between human and machine translation, (2016), arXiv preprint
[46] Yu, Liangye, On the Accuracy of Machine Learning for Equivariant Patterns, (2018), University of Birmingham, MSc. thesis
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.