Flood-counting

[linas]

One of the "deep" conceptual problems with LG parsing is that there are usually either not enough parses (i.e. null words) or there are too many (count overflow) and its hard to strike a middle ground. This particularly affects linkage generation: there (currently) isn't any way to know the cost of a linkage, without actually computing it.

This issue is meant to be a place to daydream about possible solutions to this.

I have only one very vague and not really workable suggestion, for right now. During counting, instead of counting 1 for each link, instead do a weighted count of $2^{-cost}$ for each link.

Counting in this way replaces a grand-total by a weighted count, hinting at how many of these potential linkages are low-cost, vs. how many are high-cost. We could even make it smell more like simulated annealing by using $exp(-\beta \times cost)$ instead of $2^{-cost}$ where $\beta$ is a user-supplied "inverse temperature" parameter $\beta=1/kT$.

What is not yet clear to me is how to use this to replace the random sampling of linkages (when there is a count overflow) by a weighted random sampling, that would make lower-cost linkages more likely to be sampled.

[ampli]

Can we just ignore the count overflow?
As each linkage is a path in the parse-set/parse-choice graph, maybe we can apply a heuristic algo to find the shortest (lower metric cost) paths. It is known that it is NP-hard, but I understood there are approximate algos that are fast and give results that are close to the optimum.

---

From Wikipedia:

Various heuristics and approximation algorithms, which quickly yield good solutions, have been devised. These include the Multi-fragment algorithm. Modern methods can find solutions for extremely large problems (millions of cities) within a reasonable time which are with a high probability just 2–3% away from the optimal solution.

---

(The parse-set graph may also have special properties that enable shortcuts in these algos, but I guess it could be very time-consuming to investigate that.)

[linas]

Idea two: issue-links in sorted order.

Currently, in extract-links.c the exctract_links() calls list_links() with an index. This walks the left and right trees using a modulo numbering scheme. This modulo scheme always explores the left parse-set exhaustively, before taking the next step on the right. I thought that perhaps it could work in a quasi-sorted order, by stepping left or right, depending on which one has lower cost. So I tried this:

--- a/link-grammar/parse/extract-links.c
+++ b/link-grammar/parse/extract-links.c
@@ -838,8 +845,16 @@ static void list_links(Linkage lkg, Parse_set * set, int index)
        }
        assert(pc != NULL, "walked off the end in list_links");
        issue_links_for_choice(lkg, pc, set);
+
+float lcost = pc->set[0]->first->md->cost;
+float rcost = pc->set[1]->first->md->cost;
+if (lcost < rcost) {
        list_links(lkg, pc->set[0], index % pc->set[0]->count);
        list_links(lkg, pc->set[1], index / pc->set[0]->count);
+} else {
+       list_links(lkg, pc->set[0], index / pc->set[1]->count);
+       list_links(lkg, pc->set[1], index % pc->set[1]->count);
+}
 }
 
 static void list_random_links(Linkage lkg, unsigned int *rand_state,

This is not quite enough to make it work. The linked lists pc->first would need to be kept in cost-sorted order. ... and Parse_set_struct does not hold a cost. I did experiment with sorting based on md disjunct cost, but this was not enough. The full code of what I tried is here: https://github.com/linas/link-grammar/tree/sorting-experiment

[linas]

I have a very dumb question; excuse me if it is incredibly dumb: why are we counting, anyway? Is there some kind of info being recorded, during counting? Where? If not, why can't we just jump straight into extract? I feel like there is something obvious that I should know but have forgotten. It's embarrassing.

[ampli]

Here is how I see it:
In the counting stage, there are many dead-ends in which one of the multiplications terms is 0 and the other is not but its result is kept in Table_tracon to save its recomputation in case it is needed again. So the table is big.
In the extraction stage, all the pair results are already known, and only those with both non-zero terms are used, resulting in a smaller data table.

BTW, it seems possible to just point the parse-set elements to the corresponding Table_tracon elements, and save memory. However, I don't know if this will not trash the CPU cache (unless I try that).

[linas]

I made some progress. The code in the sorting-experiment branch now gives an almost-but-not-quite sorted sequence of linkages.

It is not obvious to me if this can be improved on, or not (while keeping that general idea implemented there). It's not clear that I've handled totcost correctly, or whther it should be a totmincost or some other function of the left and right branches. I'm done for tonight. @ampli you seem to understand this code better than I; can you see what it is that I am trying to do here, and can you see any way of fixing it to provide a true total order?

Here are two clues as to what is going wrong:

• It seems as if the even-numbered and odd-numbered linkages got swapped. The costs alternate up/down with each linkage. (I'm looking at the duuude i= prints, which are printed just after the linkages are completely enumerated, but before they are sorted.)
• The order in which the linkages are enumerated seems to (almost) not depend on the inequality chosen at line 895 -- either greater-than or less-than gives almost the same results. Which seems surprising.

[linas]

Hmm. My "almost works" code seems to almost not work, depending on the sentence. So for example:

this is an exceptionally long wired test that perhaps might have more linkages than you might think

generates linkages in "almost sorted order". However,

Let's try some other kind of long strange sentence that might be something or maybe it can be something else

does not do very well, with almost randomized results, i.e. almost not sorted at all. So, clearly, I've been fooling myself, with what I thought I was doing here. What am I doing wrong? Is this fixable?

[ampli]

So, clearly, I've been fooling myself, with what I thought I was doing here.

I think so.

What am I doing wrong?

A local sorting of disjunct costs cannot let you find linkages with the total lowest costs, as the nested parse-sets (inside a parse-choice) lead to other parse-choice lists that contain arbitrary and unknown costs, and thus has a zero prediction ability on the rest of the costs that will be found until the end of the graph.

This is similar to the traveler to the Travelling_salesman_problem, in which following the shortest link to the next node doesn't lead, in general, to the shortest local path.

Is this fixable?

I think that it is not fixable in the way you did it, but has to be done using one of the shortest path finding algos.

[ampli]

BTW, I forgot to add that I looked at your sorting-experiment changes.

[ampli]

You once added a comment in extract-links.c on getting the lower cost parse, with a partial implementation under #ifdef FINISH_THIS_IDEA_MAYBE_LATER.

link-grammar/link-grammar/parse/extract-links.c

Lines 358 to 364 in acb424d

	/**
	* Sort the match-list into ascending disjunct cost. The goal here
	* is to issue the lowest-cost disjuncts first, so that the parse
	* set ends up quasi-sorted. This is not enough to get us a totally
	* sorted parse set, but it does guarantee that at least the very
	* first parse really will be the lowest cost.
	*/

I finished its implementation 4 years ago in commit c1b4d78. The code is enabled by -test=sort-match-list. It doesn't seem to do anything useful! I think this is because of the same reason. So you may want to revisit this comment.

[linas]

sort-match-list

Hmm. In that case, the code for sort-match-list, and the comment, should be removed. Any objections to removing it?

[ampli]

It can indeed be removed.

[linas]

A local sorting of disjunct costs cannot let you find linkages with the total lowest costs, as the nested parse-sets (inside a parse-choice) lead to other parse-choice lists that contain arbitrary and unknown costs, and thus has a zero prediction ability on the rest of the costs that will be found until the end of the graph.

I'm still struggling to understand the parse set. To begin doing this, I started by making some measurements, like so:

uint64_t pset_size(Parse_set * pset)
{
   if (pset->first == NULL) return 0;

   uint64_t tot = 0;
   for (Parse_choice *pc = pset->first; pc != NULL; pc = pc->next) {
      tot ++;
      tot += pset_size(pc->set[0]);
      tot += pset_size(pc->set[1]);
   }
   return tot;
}

For the Bainite test sentence I get that the tree seize is 1153392 -- about 1.1 million, while there are 10201832 linkages -- 10M (Pset_bucket_pool size= 1321 and Parse_choice_pool size= 2698)

For the Tagalog test sentence, I get a parse tree size of 1.74e9 and a parse-count overflow. I changed count_t to 64-bit, and it seems there are 2.4e13 linkages (Pset_bucket_pool size= 3483 and Parse_choice_pool size= 13150)

For the Cortes sentence, and 32-bit counts, I get an overflow and 1.2e10 tree size. For 64-bit counts, Cortes gives

49128286530384 linkages -- 49T = 4.9e13 at null count 0
3065210334826656 linkages -- 3065T = 3.0P = 3.0e15 -- null count=1
85107253873160528 linkages -- 85P = 8.5e16 -- null-count=2
1432754044150117546 linkages -- 1.4H = 1.5e18 -- null-count=3

and I don't know how big a parse-tree -- it is still counting, as I write this. At least 1e12, if not more.

Obviously, counting such humongous trees does NOT require lots of RAM -- most of the branches in the tree seem to be rearranged copies of one-another, pulled out of hash tables (the RSS of LG during the Cortes counting is 278 MBytes ; the Pset_bucket_pool size is 90571 and the Parse_choice_pool size is 874347; added together, these two pools total less than a million entries.)

Thus, even though the count is explosive, the Parse_set tree is much smaller, although it is still huge. But this tree has vast amounts of repetition in it.

Rephrased as a traveling salesman problem, Its as if the salesman has to visit certain houses in certain towns in certain counties in certain states, but most of the towns are identical to one-another, and most of the counties are identical to one-another, and most of the states are identical, just with permutations that skyrocket the number of possibilities. Somehow, the same-ness should be exploitable.

(counting code is here )