Rewrote README.md; still needs work.
authorYeGoblynQueenne@splinter <ep50@uni.brighton.ac.uk>
Fri, 25 Nov 2016 12:30:29 +0000 (12:30 +0000)
committerYeGoblynQueenne@splinter <ep50@uni.brighton.ac.uk>
Fri, 25 Nov 2016 12:30:29 +0000 (12:30 +0000)
* I seem to be getting the escaping of underscores wrong? Or is that a
  problem with the way Swi (or Firefox) renders the escapes? Needs
  pickign at.

README.md

index 7d06e2d..f240a3d 100644 (file)
--- a/README.md
+++ b/README.md
 # THELEMA
 A TEHory LEarning MAchine for grammar induction. 
 
-THELEMA is an inductive logic programming algorithm and a program based on that
-algorithm. The algorithm learns a graph structure from sequential data, for
-instance a grammar from examples of sentences in a tagret language. 
+THELEMA is a structure learning algorithm. The algorithm learns a graph
+structure from sequential data. This "skeleton graph" is then transformed to a
+grammar in a number of different formats, including right-regular and Greibach
+Normal Form grammars. 
 
-For the time being THELEMA is taking its first baby steps in its very own blocks
-world: the Controlled Natural Language at the heart of the Collectible Card Game
-Magic: the Gathering known as "Ability Text" (no affiliation between this
-project and the publishers of that game). 
+THELEMA is entirely unsupervised (unless one counts tokenisation as a form of
+weak supervision) and can learn deterministic or stochastic grammars,
+lexicalised or not.
 
-The image below is a diagram of a grammar THELEMA learned from a small set of 18
-examples of Ability Text. 
-
-![Alt text](/../images/readme_image_files/destroy_short_lexicalised_rgnf.png?raw=true "Lexicalised Restricted-Greibach Normal Form")
+In this dissertation THELEMA is used for grammar induction over the Magic the
+Gathering Controlled Natural Language (Ability Text). 
 
 Using THELEMA
 =============
 
 THELEMA is written in Prolog. You will need to have Swi-Prolog 7.0 or later
-installed on your system. 
+installed on your system. 64-bit versions are recommended, in order to allow
+large corpora to be loaded in memory without breaking the Prolog global stack. 
+
+The current version of THELEMA was developed with Swi-Prolog version 7.3.25 and
+runs on Windows 7, 8.1 and 10, Fedora Linux and Mac OS (El Capitan). 
+
+On platforms other than Windows you may not be able to load source files in the
+Swi-Prolog IDE as described below but other functionality should remain intact. 
 
 Start THELEMA by loading the file: 
 
 ```
-tree_learning/load_tree_learning.pl
+<project-root>/load_project.pl
 ```
 
 On a windows machine you can double-click the file and it will open the Prolog
-console and the Swi-Prolog IDE. On Linux: 
+console and the Swi-Prolog IDE. 
+
+On Mac or Linux you may have to do this: 
+
+ 1. change directory to <project-root> 
+ 2. start Swi-Prolog 
+ 3. enter "[load\_project]."
+
+On Mac or Linux that will *probably* not bring up the IDE. On a Windows machine
+you should see output similar to the following:
+
+```
+% Started server at http://localhost:52874/
+% Started Prolog Documentation server at port 52874
+% You may access the server at http://localhost:52874/
+Finished loading project. Opening source files in IDE...
+Global stack limit:512004096
+Current configuration options:
+% examples_file_name = mtg_hand_simulation
+% graph_arity = 1
+% language_file_name = ability_text
+% training_set_size = 1.0
+% transformation_format = right_regular
+% Grammar output file:
+% output(right_regular_k_1_mtg_hand_simulation_ability_text_dcg.pl)
+```
+
+Additionally the Swi-Prolog documentation server should start and your browser
+open a new page to its top-level, displaying this file with some nice formatting.
 
-1. change directory to tree\_learning
-2. start Swi-Prolog,  and 
-3. enter "[load\_tree\_learning]."
+# A first induction run with a toy corpus
 
-On Linux that will *probably* not bring up the IDE. But you never know. 
+One controls THELEMA in two steps: 
 
-The shiny happy path through the application
-============================================
+ 1. Edit the configuration file. 
+ 2. Enter queries at the Prolog top-level.
 
-To begin training THELEMA you need to edit the configuration file: 
+Editing the configuration file is how one chooses a training corpus, grammar
+formalism, output file etc, including algorithm hyperparameters (graph fitting
+k, graph transformation j, lexicalisation l etc; see included dissertation
+report for details).
+
+The main project configuration file is in:
 
 ```
 tree_learning/configuration.pl
 ```
 
-You should read the comments in that file. They will probably make sense after a
-while. To begin with, make sure you have the following options set: 
+Structured comments in that file provide useful information about the various
+options and can be viewed with the Swi documentation browser (look for the path
+ending in "grammar\_learning" in the drop down at the top of the documentation
+page). 
+
+To follow through with this short guide, make sure you have the following
+options set: 
 
 ```
-examples_file_name(examples_mtg_hand_simulation).
-language_file_name(language_mtg_hand_simulation).
-lexicalisation_strategy(none).
+edit_output_grammar(true).
+examples_file_name(mtg_hand_simulation).
 output_type(dcg).
-production_augmentation(greibach).
-production_composition(synonym).
-rename_built_ins(n_).
+graph_arity(1)
+language_file_name(ability_text).
+lexicalisation_strategy(none).
+training_set_size(1.0)
+transformation_format(right_regular)
 ```
 
-If you need to change a setting, remember to enter: 
+Except for edit\_output\_grammar(true) these options will already be set by
+default and will allow training a right-regular grammar with a *k* value of 1
+and with no lexicalisation.
+
+To train such a grammar from our toy corpus, enter the following in the Prolog
+listener:
+
+```
+print_grammar.
+```
+
+This will print out a short right-regular grammar and open the file in the
+Swi-Prolog IDE. Alternatively, you can output the grammar on the command line
+with:
+
+```
+print_productions.
+```
+
+It is really not advised to do this with a larger corpus, resulting in a very
+large number of productions printing out for a long time.
+
+
+### Inspecting current configuration options
+
+You can always inspect the most relevant options to the current configuration
+by entering this at the Prolog listener:
+
+```
+utilities:dynamic_configuration.
+```
+
+Or, to see *all* configuration options, enter:
+
+```
+utilities:current_configuration.
+```
+
+If you need to change a configuration option, remember to enter the following at
+the Prolog top-level: 
 
 ``` 
-make. 
+reload. 
 ```
 
-At the Prolog top-level, or the changes won't take. 
+Otherwise, the changes won't take. 
+
 
-With these settings, THELEMA will learn a non-lexicalised Context-Free Grammar
-from the "examples\_mtg\_hand\_simulation" mini-corpus (as its name implies this
-corpus was used for hand-simulations which explains why it's so tiny).
+### Killing Prolog (to get out of a difficult spot)
+This is a good time to note that sometimes the Prolog top-level can hang or
+appear to take a very long time to process. If a minute or so passes without any
+feedback at all, especially if you're following through with this guide with
+only small variations, you should kill Prolog and start again.
 
-Start training by entering this query at the Prolog top-level: 
+Start training our toy grammar by entering this query at the Prolog top-level: 
 
 ```
 print_grammar. 
 ```
 
 THELEMA will place a grammar file in tree\_learning/output/ named after the
-configured examples and language file so that you can easily identify it.  
+configured examples and language file so that you can easily identify it:
 
-Parsing and generating Ability Text with Definite Clause Grammars
-=================================================================
+```
+right_regular_k_1_mtg_hand_simulation_ability_text_dcg.pl
+```
 
-THELEMA's "native" grammar format is Prolog's Definite Clause Grammars notation.
-DCGs have a direct translation to Horn Clauses so in most Prologs and indeed in
-Swi-Prolog, DCG rules will automatically compile to ordinary Prolog predicates
-when you load their source file. This might sound like a load of jargon but the
-upshot of this is that the grammar that THELEMA learns is really a program in
-Prolog. In fact, it's a parser and also generator for strings in the language
-described by the grammar. 
 
-You can verify this if by doing the following: 
+### Training with a larger corpus 
+To train a grammar on a different training corpus, edit the configuraiton
+option:
 
-1. Load the output grammar file from the Shiny Happy Path section into a new
-Prolog instance (don't use the old one or you'll get told off)
-2. Enter this query at the Prolog top-level: 
-   
 ```
-forall(phrase(ability, P), writeln(P)). 
+examples_file_name(mtg_hand_simulation).
 ```
 
-If you followed the Shiny Happy Path to the letter, the above query should give
-you a set of nice little derivations reproducing the examples in the training
-corpus and even generalising a little. 
+The configuration file already includes a number of different corpora, commented
+out. Most of them exist as Prolog source files inside the tree\_learning/corpus/
+directory.
 
-If you *didn't* follow the Shiny Happy Path then woe is you. Larger datasets
-tend to produce grammars with recursive paths running though them. If you try to
-geneate new text from such a grammar Prolog will lock. If... when that happens
-you can abort execution with "Ctrl + C" and then "a", or by killing the Prolog
-instance. 
+Uncomment the line declaring the full M:tG corpus as the current training
+corpus:
 
-You can also use the induced grammar as a recogniser, to accept or reject
-strings. 
+```
+%examples_file_name(all_sets_tokenised).
+```
 
-Try this; at the Prolog top-level, on the same instance where you loaded the
-output of the Shiny Happy Path, enter the following queries: 
+Remember to reload the project at the Prolog listener:
 
 ```
-phrase(ability, [destroy,target,artifact]).
-phrase(ability, [destroy,target,X]).
-phrase(ability, [destroy,target,stassa]). 
+?- reload.
 ```
 
-The first query should say "true" and then wait for input. Press "enter" to end
-the search for more answers (if you press ";" the query exits with "false"
-because it can't find more results that match its pattern). 
+Now train a grammar with:
 
-The second query should bind "X" to "artifact" and wait for input. Press ";" or
-the space bar for more results and "X" will bind to "creature". Press enter to
-end the search or ";" to see the "false". 
+```
+?- time(print_grammar).
+```
 
-The third query lived in a house of stone. There is no such derivation possible
-in the grammar you loaded, therefore Prolog will immediately say "false" and
-end its search for answers. In any case, you should never destroy stassas, they
-don't like that. They do like chocolate, however. Do you have chocolate? If you
-have chocolate then you can proceed to the next section.
+The time/1 predicate will give you some statistics on the time taken to learn a
+grammar. On the machine used for development, with 16 GB of RAM, this takes
+under 10 seconds: 
 
-Grammar formalisms and output formats
-=====================================
+```
+?- time(print_grammar).
+Split corpus to training and test sets
+================ Composing Productions ================ 
+% 71,890,063 inferences, 8.266 CPU in 8.463 seconds (98% CPU, 8697475 Lips)
+true.
+```
 
-For now, THELEMA only learns one type of grammar, a determinstic Context-Free
-Grammar in a restricted Greibach Normal Form, where all rules are of the form: 
+### What to do when the global stack breaks
 
-``` 
-a → aA 
+As mentioned earlier, training with a reasonably sized corpus can break the
+Prolog global stack, at which point you will receive this error and training
+will stop:
+
+```
+ERROR: Out of global stack
 ```
 
-In other words, a single terminal followed by a single nonterminal. Note that
-the single terminal is always the synonym of the production's left-hand side;
-essentially the solitary terminal is a label annotating the node on the
-retrieved graph that the production represents. A non-restricted form of GNF and
-possibly other grammar formalisms will follow in the future. 
+The Prolog global stack is where compound terms live. Training examples
+(sentences) are stored as compound terms and it's easy to overwhelm the default
+stack capacity while processing a large corpus, depending on other configuration
+options. 
 
-The fact that THELEMA models its input as a grammar is a happy coincidence. It's
-trivial to represent a context-free grammar as a graph with arcs mapping the
-relations between nonterminals. 
+The global stack size is already set to 512 MB by default, and it can be
+increased further by editing the project load file, "load\_project.pl" at the
+project root directory. 
 
-To see this in action, set the following option in configuration.pl:
+Find the line, near the end of that file, where the global stack limit is set:
 
-``` 
-output_type(dcg). 
+```
+:-set_prolog_stack(global, limit(2**9*10**6)).
+```
+
+And change the first power to something else than 9. For instance, the following
+sets the global stack size to 1024 MB:
+
+```
+:-set_prolog_stack(global, limit(2**10*10**6)).
+```
+
+Remember to enter "reload" at the listener (or "make") after this change or it
+won't have any effect.
+
+### Examining trained grammars
+Instructions above guided you to make sure this option is set to true:
+
+```
+edit_output_grammar(true).
+```
+
+This tells the system to open a trained grammar in the Prolog IDE. If you
+followed the steps above, you should see a file beginnig with the following
+lines:
+
+```
+:-module(right_regular_k_1_all_sets_tokenised_ability_text_dcg,[ability//0]).
+
+% examples_file_name = all_sets_tokenised
+% graph_arity = 1
+% language_file_name = ability_text
+% training_set_size = 1.0
+% transformation_format = right_regular
+% Grammar output file:
+% output(right_regular_k_1_all_sets_tokenised_ability_text_dcg.pl)
+
+ability-->'n_('.
+ability-->'n_+'.
+ability-->'n_-'.
+ability-->n_0.
+ability-->n_1.
+ability-->n_2.
+ability-->n_3.
+ability-->n_4.
+ability-->n_5.
+ability-->n_6.
+ability-->n_7.
+ability-->n_8.
+ability-->n_9.
+ability-->n_A.
+```
+
+"ability" is the start symbol of the trained grammar, defined in a language
+file named <project root>/grammar\_learning/language/ability\_text.pl. This can
+be configured with option language\_file\_name/1.
+
+The grammar file echoes a short set of configuration options. This way, it's a
+little easier to tell how a particular grammar came to be.
+
+
+Parsing and generating Ability Text with the query interface 
+============================================================
+
+Once a grammar is trained, it can be queried with the predicates in the
+query\_interface module (in directory grammar\_learning). These are there for
+convenience, to avoid having to load and re-load trained grammars at the
+top-level (which may sometimes give errors about redefined predicates; the query
+interface modules should help avoid that). Additionally, trained grammars are
+"sanitised" with a prefix character that ensures nonterminal symbols are valid
+prolog identifiers. By default this prefix is the characters "n\_" which makes
+parsing and generating strings a bit cumbersome, without the query interface
+predicates.
+
+The query interface module is loaded by default at project startup. If you've
+been following through with our guide so far, you should now have a
+deterministic grammar trained from the entire M:tG corpus. 
+
+To start parsing and generating strings from it, enter the following query at
+the Prolog top-level:
+
+```
+?- sentence_completion(current, max(21)).
+```
+
+You should be presented with an input prompt, "|:". Enter an AT string, as in
+the example (or whatever string you prefer):
+
+```
+|: Return
+```
+
+If the string you enter is a valid string, you should see some activity. If you
+give a partial sentence, this will be completed, as follows:
+
+```
+Return it 
+true ;
+Return : Kavu 
+true ;
+Return : Wall 
+true ;
+Return Cage . 
+true ;
+Return Crovax . 
+true ;
+Return Evershrike . 
+true ;
+Return Field . 
+true .
+```
+
+A partial sentence can include variables, prefixed with "$" and starting with a
+capital letter (unlike Prolog variables that don't use the "$" prefix): 
+
+```
+?- sentence_completion(current, max(21)).
+|: Exile $X creature
+Exile Giant creature 
+true ;
+Exile X creature 
+true ;
+Exile a creature 
+true ;
+Exile all creature 
+true ;
+Exile another creature 
+true .
+```
+
+You can also simply check whether a string is accepted or rejected by the
+grammar:
+
+```
+?- sentence_completion(current, max(3)).
+|: Exile target creature
+Exile target creature 
+true ;
+false.
+
+?- sentence_completion(current, max(3)).
+|: Exile target thingamajigg  
+false.
+```
+
+The second argument of sentence\_completion/2 limits the length of derivation,
+and therefore the depth of parsing. This is necessary to control right-recursion
+which may cause parsing to "go infinite". 
+
+There are three limit types: minimum, maximum and exact: 
+
+```
+?- sentence_completion(current, max(1)).
+|: Exile target creature
+false.
+
+?- sentence_completion(current, min(1)).
+|: Exile target creature
+Exile target creature 
+true ;
+Exile target creature " 
+true ;
+Exile target creature . 
+true .
+
+?- sentence_completion(current, just(3)).
+|: Exile target creature
+Exile target creature 
+true ;
+false.
+```
+
+Care should be taken when using the 'min' option- the DCG "parser" can take a
+very long time to find a correct string of the required *minimum* length
+(because it will generate all possible strings of at least that length). 
+
+If this happens (or if anything else goes wrong) you can always stop execution
+with Ctrl-D.
+
+### Query interface: known bugs 
+There is a bug in the query interface module, that may result in the following
+error right after you enter a sentence\_completion/2 query for the first time in
+a single Prolog session:
+
+```
+ERROR: c:/.../grammar_learning/output/right_regular_k_1_all_sets_tokenised_ability_text_dcg.pl:413:
+        Unknown message: inference_limit_exceeded
+```
+
+While this is a bit unsightly, it does not affect functionality. Press ";" to
+ignore it and start generating derivations.
+
+### Training more types of grammar
+Deterministic right-regular grammars are only one type of grammar the THELEMA
+can learn. Different types of grammar can be trained with configuration options
+detailed in the documentation of the configuration module. 
+
+For a short example, to train a grammar in Greibach Normal Form, set the
+following options (and enter "reload") then train a grammar with
+"grammar\_printing" as before:
+
+```
+graph_arity(2).
+transformation_format(gnf).
+```
+
+Or, to train a *stochastic* GNF grammar, use:
+
+```
+graph_arity(2).
+transformation_format(stochastic_gnf).
+```
+
+It is also possible to translate grammars in BNF or dot-language formats (the
+latter used for visualisation with the Graphviz package, the former for parser
+generation in yacc etc):
+
+```
+output_type(bnf).
+output_type(lean_dot).
+```
+
+Additionally, you can train a *bootstrapped* grammar with:
+
+```
+bootstrapping(4,0.3).
+```
+
+### Grammar Evaluation
+Predicates in module grammar\_evaluation were used to produce the results
+reported in Section 5 of the dissertation report. 
+
+To perform nested k-fold cross-validation, train a stochastic right-regular
+grammar and enter this in the Prolog top-level:
+
+```
+nested_k_fold_cross_validation.
 ```
 
-Then train THELEMA with "print\_grammar" as above. THELEMA will then print out
-its induced grammar in the dot-language format used for visualisation (the file
-is still placed in tree\_learning/output). You can feed that file directly into
-a visualisation package such as Graphviz to generate a diagram of the induced
-grammar. This is how the image at the start of this file was created. 
+With default options (other than the stochastic format) this will perform
+nested 10-fold cross validation and report results using the Kullbert-Leibler
+Divergence metric. 
 
-THELEMA can also print out its grammar in the BNF and EBNF formats used in
-parser generators such as Yacc and Bison. Neither of these formats is
-particularly strictly implemented at this point, but you can always play around
-with them a bit and see if you can get them to work with your favourite compiler
-compiler. 
+Be warned that this can take a very long time for a large corpus.