Learning rule weights

 

The "learn­ing rule weights" fea­ture was imple­ment­ed in the first ver­sion of the Bol Processor (BP1) a long time ago. It was designed in response to a prob­lem that arose dur­ing field­work ses­sions while Jim Kippen was devel­op­ing gram­mars capa­ble of iden­ti­fy­ing the "lan­guage" con­veyed by qa‘ida com­po­si­tions of tabla. Citing Jim (Kippen & Bel, 1992):

[…] some­times a gram­mar would reach a point of stag­na­tion where computer-generated vari­a­tions were judged to be nei­ther very good nor incor­rect. Consequently there was no sim­ple way of refin­ing or improv­ing the mod­el. We felt that a solu­tion lay in attribut­ing to each pro­duc­tion rule a coef­fi­cient of like­li­hood (or weight) where the prob­a­bil­i­ty that cer­tain gen­er­a­tive paths would be cho­sen in pref­er­ence to oth­ers could be examined.

The prob­a­bilis­tic mod­el that has been imple­ment­ed on the BP is derived from prob­a­bilis­tic grammars/automata as defined by Booth & Thompson (1973), the dif­fer­ence being that a weight rather than a prob­a­bil­i­ty is attached to every rule. The rule prob­a­bil­i­ty is com­put­ed as fol­lows: if the weight is zero then the prob­a­bil­i­ty is zero; if the weight is pos­i­tive then the infer­ence engine cal­cu­lates the sum of weights of all can­di­date rules, and the rule prob­a­bil­i­ty is the ratio of its own weight to the sum.

Another remark­able fea­ture of Bol Processor gram­mars is that rule weights can be inferred from a set of sen­tences (Maryanski & Booth 1977:525). The algo­rithm imple­ment­ed in the BP is more pow­er­ful than the one devised by Maryanski and Booth, since the lat­ter required the choice of a sam­ple set in which all rules had been used. Given a gram­mar and a sub­set of the lan­guage that this gram­mar gen­er­ates (for instance a sam­ple sequence tak­en from a per­for­mance of an expert musi­cian), rule weights may be inferred as fol­lows: let all weights be reset to zero; then analyse every sen­tence and incre­ment by one unit the weights of all rules used in the derivation.

We will demon­strate the infer­ence of rule weights using gram­mars and data dis­trib­uted in the ‘ctests’ fold­er. These gram­mars are real exam­ples from field work.

Infer weights in the "-gr.dhadhatite" grammar

The ‘ctests’ fold­er con­tains both "-gr.dhahatite" and "-dha.dhahatite". The lat­ter is a set of 15 exam­ples designed for the demon­stra­tion. They are not musi­cal­ly rel­e­vant because they were all pro­duced by the gram­mar and will there­fore be parsed suc­cess­ful­ly. However, you can try mod­i­fy­ing details to observe failed parsing.

In addi­tion the first eight ones are iden­ti­cal, except for their nota­tion. Items can be typed with­out spaces, giv­en that the ter­mi­nal alpha­bet in "-al.dhahatite" will cre­ate a cor­rect seg­men­ta­tion. They can be set out on sev­er­al lines sep­a­rat­ed by sin­gle line feeds. Beats can be marked with peri­ods (the peri­od nota­tion) which the poly­met­ric algo­rithm will con­vert into iden­ti­cal sym­bol­ic dura­tions (see this page).

Let us have a look at the "-gr.dhahatite" gram­mar which we already used for pars­ing vari­a­tions. First cre­ate its tem­plates as explained ear­li­er. Then add "-dha.dhahatite" and "-wg.dhahatite" in its dec­la­ra­tions and save the page. This mod­i­fy the dis­play of the top of the grammar:

We only need to click the LEARN weights but­ton to launch the infer­ence of weights from the sam­ple set in "-dha.dhahatite":

The pro­duc­tion win­dow shows that all 15 items were suc­cess­ful­ly parsed although
"13 item(s) failed in the pars­ing after match­ing a tem­plate"… We knew that this gram­mar would accept all items, so we need an expla­na­tion for the failed parsing.

Click the Show trace but­ton to get more details:

🔎 Analyzing new selec­tion…
dhad­hatit­ed­had­had­heenad­heenatit­ed­heena­teenad­had­hatit­ed­had­had­heenad­had­hatit­ed­had­ha­teenatatatite­tata­teena­teenatite­teena­teenad­had­hatit­ed­had­had­heenad­had­hatit­ed­had­had­heena
▶︎ Analyzing item [Single line]
👉 Item [Single line] matched tem­plate [1]
• Subgrammar 6/6
• Subgrammar 5/6
• Subgrammar 4/6
• Subgrammar 3/6
• Subgrammar 2/6
• Subgrammar 1/6
Item [Single line] match­ing tem­plate [1] reject­ed by gram­mar… ❌
Result of failed analy­sis:
S1F +V8(= S1F) +S2F *(= S1F ++A2 V6)(: S1F) S1F
👉 Item [Single line] matched tem­plate [2]
• Subgrammar 6/6
• Subgrammar 5/6
• Subgrammar 4/6
• Subgrammar 3/6
• Subgrammar 2/6
• Subgrammar 1/6
Item [Single line] match­ing tem­plate [2] reject­ed by gram­mar… ❌
Result of failed analy­sis:
(= ++S2F) +V8 S1F +S2F *(: ++S2F) *(= ++A2 V6) S1F S1F
👉 Item [Single line] matched tem­plate [3]
• Subgrammar 6/6
• Subgrammar 5/6
• Subgrammar 4/6
• Subgrammar 3/6
• Subgrammar 2/6
• Subgrammar 1/6
Item [Single line] match­ing tem­plate [3] accept­ed by gram­mar… ✅
Etc.

The trace shows that the first item failed to match two tem­plates, but suc­ceed­ed with tem­plate [3], after which it was cor­rect­ly parsed. A sim­i­lar behav­iour is dis­played by oth­er items. The trace is detailed because the option "Trace pro­duc­tion or pars­ing" is checked in the settings.

Now, move down to the bot­tom of the gram­mar and click the "-wg.dhatite" but­ton. This file was cre­at­ed by the BP3 con­sole upon com­ple­tion of its analy­sis. It con­tains the new weights of the gram­mar, i.e. for each rule, the orig­i­nal weight (usu­al­ly 100) plus the num­ber of times the rule has been used in the pars­ing process.

For exam­ple, the weight of rule [1] of gram#1 would be raised from 100 to 115, since it was used for all items. However, the weight of rule [5] of gram#1 would stay at 100, since it was not used in this analy­sis. Changes are easy to check com­par­ing the con­tent of "-wg.dhatite" with weights in the grammar.

The "-wg.dhatite" dis­play includes sev­er­al but­tons that are easy to understand:

• The COPY cur­rent weights but­ton will save all the weights in the gram­mar in the file "-wg.dhatite";
• The SET rule weights and RESET rule weights but­tons will set or reset all weights in the file "-wg.dhatite", yet not in the grammar.
• The COPY BACK rule weights but­ton will copy weights from "-wg.dhatite" to the "-gr.dhatite" gram­mar. Beware that this can­not be undone!

In real life…

This "-wg.dhatite" lay­out shows how to pro­ceed in real-life sit­u­a­tions. You have a work­ing Bol Processor gram­mar, as well as a large set of exam­ples pro­duced by the gram­mar or pro­vid­ed by the expert you are work­ing with. Proceed as follows:

1. Open the "-wg" file and RESET all weights to 0;
2. Click the LEARN weights but­ton;
3. Keep an eye on items that are reject­ed. These may indi­cate an incom­plete gram­mar. They may also be incor­rect. If so, make changes and go back to step 1;
4. Open the "-wg" file and click the COPY BACK rule weights button;
5. You can repeat this process with more sets of exam­ples, as rule weights will add up.

Although rule weights can be very large inte­gers, we find it more prac­ti­cal to keep them with­in a small range, such as 0 to 127. The 127 lim­it is just a con­ven­tion that can be changed in the PHP inter­face. Currently, if a weight is invis­i­ble, its val­ue is 127, and vice versa.

---

References

Kippen, Jim, & Bernard Bel (1992) Modelling music with gram­mars: for­mal lan­guage rep­re­sen­ta­tion in the Bol Processor. In A. Marsden & A. Pople (eds.): Computer Representations and Models in Music, London, Academic Press, 1992, p. 207-238.

Booth, T.L. and R.A. Thompson (1973). 'Applying Probability Measures to Abstract Languages’, IEEE Transactions on Computers, Vol.C-22, n°5, p. 442-450.

Maryanski, F.J., and T.L. Booth (1977). ‘Inference of Finite-State Probabilistic Grammars’, IEEE Transactions on Computers, Vol.C-26, n°6, p. 521-536.
[Some anom­alies of this paper are cor­rect­ed in B.R. Gaine's paper ‘Maryanski's Grammatical Inferencer’, IEEE Transactions on Computers, Vol.C-27, n°1, 1979:62-64]