Tokenization discussions

[linas]

The discussion in #1310 wanders off into tokenization, and a distinct thread for that seems best. Specifically this comment from @akolonin

• On-the-fly expressions (disjuncts) !? #1310 (comment)

I just read the following:

• Jesse O. Wrenn, Peter D. Stetson, Stephen B. Johnson
  An Unsupervised Machine Learning Approach to Segmentation of Clinician-Entered Free Text
  AMIA Annu Symp Proc. 2007; 2007: 811–815.
  PMC2655800
  https://www.ncbi.nlm.nih.gov/pmc/articles/PMC2655800/

I found it frustratingly opaque and imprecise. Work items and clarifications suggest themselves:

• A precise mathematical, symbolic definition of peak freedom is needed. The
  informal definition is imprecise, prone to misunderstanding, and obscures
  relationships to other similar mathematical formulas.
• Peak freedom appears to be defined as a second difference, as the
  difference between the prior and the subsequent transition freedom.
  What if, instead, one worked with log2 of transition freedoms, so
  that a peak entropic freedom was a ratio instead of a difference?
• Given this variant, what other variants of freedom are possible, and
  how are they related to more traditional entropic definitions?
• Show distribution of peak freedom. That is, there are hundreds of
  thousands of transitions; what's the freedom of each? What's the peak
  freedom of each?
• How do things change, if one considers not just the next character, but
  the next pair of characters, or the next triple of characters?

@akolonin by "distribution" I mean this: consider taking the bar charts on page 5-6 of your paper (the https://arxiv.org/abs/2205.11443 one) and projecting them onto the right axis. This gives a distribution that shows how often any given height occurs. The questions: what's that distribution? Is it gaussian? Something else? What's the mean and deviation? ... Personally, I cannot get comfortable with any of this stuff until I see the distributions, and also the formal definitions, and the variants that use log2 of transition freedoms.

The Wrenn etal 2007 paper and the Kolonin 2022 paper seem to work with "transition freedoms" by exhaustively counting all possible transitions between substrings and single characters. What if instead, we worked with transitions between substrings and substrings? There are explosively many of these, and so perhaps a random subsampling is more computationally feasible? This is why I mentioned the "amy" language in #1310 (comment) : it provides a random sampling of transitions.

[linas]

@akolonin I tried to define transition freedom and peak freedom in a formal fashion, in the attached PDF. Is this correct? Hmm seem I cannot attach, I'm getting github error messages. The PDF is here: peak freedom PDF please comment.

[akolonin]

Hi Linas, I agree that the paper by Wrenn et.al. is pretty vague, speaking softly ;-)
So I was rather guessing what they are doing - see how I compute these metrics myself:
https://github.com/aigents/pygents/blob/main/pygents/token.py#L353

Notice, that the "peak" works good only for Chinese, the "variance" is better for English and Russian.

[nickm197]

I may have lost my ability to differentiate functions over dozens of years not using this ability that was pretty good around 1989. My previous comment on differentiation is an indication. Please feel free to compare notes. The term $\log⁡\Sigma_t(N^p (w,t))$ is intriguing anyway, and all this requires physical explanation.

The relationship of experiment and theory in physics is rather complicated. Basically, what you see in experiment depends heavily on a theory/hypothesis you use, and the difference between experiment and experience is that the first has to rely on some theory/try some defined hypothesis. If you occasionally read Russian and interested n the topic I can refer you to some good reading on that (unfortunately, I don't know English literature on the subject well enough).

I am not opposed to genetic search of a pseudonorm, but the search space is rather large and a norm found this way does not add to understanding the subject which is the goal for me personally.

[linas]

Oh! Ahh! Yes, that is actually the classic "fuzzy logic" generalization of set theory. And this is perhaps why things get "fuzzy" -- a strict step function gives you the Jaccard distances, but if you read the wikipedia article on Jaccard, you'll find several "probabilistic Jaccard" functions, including one that is entropy maximizing (or something like that). If you replace the step function by some sigmoid, then you can start slipping down the path of neural nets. Or you can insist that you are a right-proper Bayesianst, or an information theorist, and just work with probabilities. This is partly why I proposed "random" metrics.

I'm trying to learn Russian, very slowly, so, правоверный Байесианец I guess

[linas]

I'm half-joking about правоверный. You're presumably interested in AGI. You have to be very careful with beliefs. Once you start believing in something, it can blind you to the actual truth. Beliefs prevent realities from being perceived. It's like the drunk searching for his keys under a street lamp. The policeman asks "where did you lose them?" "Over there, but there's more light over here." This is why I want to run the experiments, to search for the answer: instead of just declaring that the solution is known and it is X. But it is difficult: how do you search? How do you know if you've found the answer? This is the metaphysics... perhaps this sounds simplistic, but I struggle with this daily.

[linas]

the search space is rather large

Yes, it is, but the search is automated: you just let the computer run for a few days or weeks. Perhaps it will discover a very classic formula from information theory, and perhaps it will discover something else. "Understanding" is like trying to hold water with your hands.

Derivatives

Here, try this:

$$ \begin {align} \frac{d}{dp} \left \Vert N \right \Vert_p &= \frac{d}{dp} \left [ \sum N^p \right ]^{1/p} \\ &= \frac{d}{dp} \exp \left( \frac{1}{p} \log \left[ \sum N^p \right] \right) \\ &= \left \Vert N \right \Vert_p \frac{d}{dp} \left( \frac{1}{p} \log \left[ \sum N^p \right] \right) \\ &= \cdots \end{align} $$

and if you finish that, you get a longer, complicated mess. Perhaps it has "physical meaning", and perhaps it is just a mess. Hard to say.

[linas]

If I didn't make any mistakes, then for the $p=1$ case I get

$$ \left . \frac{d}{dp} \left \Vert N \right \Vert_p \right |_{p=1} = \sum N\log N - \left \Vert N \right \Vert_1 \log \left \Vert N \right \Vert_1 $$

Note that if the count is normalized, so that $\left \Vert N \right \Vert_1 = 1$ then the second term is zero.

[akolonin]

@nickm197 @linas - we have extended the INLP workshop deadline https://aigents.github.io/inlp/2022/
Do you think this topic worth discussing there so I make submission on my latest results and you @nickm197 submit your latest considerations?

[nickm197]

@akolonin I see the current discussion as an introductory on a wide array of topics. I would expect it would branch into several more specific ones. As for the tokenization, this specific discussion seems to be rather early, although promising. As for my considerations, the most finalized relevant considerations are the ones on the context and criticism of Yuret dissertation. Please let me know what do you think worth submitting.

[linas]

I too got swamped ... Apologies for the late reply. Perhaps we could have a discussion panel reviewing these topics, with a goal of developing a strategy or plan to move forward?

[nickm197]

that is actually the classic "fuzzy logic" generalization of set theory

Indeed, one can look at it this way

You're presumably interested in AGI

Who is not these days?

Once you start believing in something, it can blind you to the actual truth. Beliefs prevent realities from being perceived.

This setting is the exact one where the classical Popperian discourse is valid (and it is valid until the knowledge field becomes so entangled that finally you can only falsify - in popperian terms - the whole mentis): You work with hypotheses and keep them falsifiable. In other words, there is no actual truth, but a succession of models that increasingly better describe reality. A model is an explanation of reality that accepts a certain viewpoint of the reality and, thus, compresses information about reality with losses. Occam's razor is a requirement to improve compression of information in a model.

Perhaps it will discover a very classic formula from information theory, and perhaps it will discover something else.

I am in no way an expert in genetic algorithms, but always considered them to be a descent in a rather fancy discrete space. Thus, the result depends on the way you construct this space more then on anything else. In math, one would need to prove that the optimal solution belongs to that space.

[linas]

A week ago, I prepared a long reply to the above as I prepared to go to sleep. Then matters intervened.

Some commentary on genetic algorithms, search spaces, and refining models that are ever-more accurate representations of reality. Consider the conventional decision tree: if X happens, you should do Y, unless of course Z and then you should do W (and still do Y sometimes, whenever Q is there..) This is a branching tree of decisions, and if you want to make it match "reality", it gets ever more complex.

The complexity of the tree is combinatorially exploding. If you have only two input variables, you can list all possibilities on a small piece of paper. Once you have more than 5 or 6, this becomes impractical. More than a few dozen, and even good software grinds to a halt. The space becomes much too large to explore exhaustively; there are too many possibilities to try.

The genetic-programming approach to solving the above is to find some small, simple trees that approximately model the situation, and then either make some small changes that improve accuracy (mutation) or combine two models to get a larger, more complex model (cross-over)

If you are training with a well-specified objective function, then, yes, it is a form of descent: one is looking to lower the score with each attempt. As to optimality: You can "prove" that there is an "optimal solution"; the hard part is actually finding it. This is the generic problem in machine learning.

---

Anyway, the proposal that I am making is to use genetic programming to explore the space of different possible text segmentation algorithms. The only benefit of using genetic programming is that it provides an existing software framework for managing a collection of trees, and for mutating them in a controlled way. So, instead of trying this and that segmentation algo by hand, the idea is to automate the search.

---

I can provide more detail on how genetic programming can be made to work, and what some of the traps and pitfalls are, if you are interested. My general goal is to build up enough software infrastructure to allow text segmentation to be automated, and to build it generally enough that audio and visual data can be segmented too. Or even arbitrary sensory data, e.g. magnetic field readings or whatever. ... anyway, the goal is to build the software that can confront the general case.

---

There are other things to talk about, but I'm trying to keep the discussion narrow.

[nickm197]

There is quite a wide literature on both unsuperwised text and image segmentation... Then, there are things like phoneme segmentation in speech etc. There are some recurrent topics, but at the moment I would say I lack understanding to generalize, even that I am no stranger to several of these tasks.

Keeping things narrow, I have played with @akolonin old (April?) notebooks a bit. My current perception is that the freedom-based aproach is a fancy way to detect seperators in a text.

Experimental protocol: remove whitespace from a corpus in Russian or English.

Theoretical ground: if we consider an end of a word, it is more likely to find a separator (say,
{' ','-','.',',','?','"',':',';','&','(',')','!','\n',' '})
after it, rather then find the same n-gram inside a different word. The effect of finding separators deteriorates as the corpus becomes larger and thus includes more rare words and typos. In a limit of an infinite corpus the freedom of all n-grams would become equal and equal to the size of alphabet.

It looks like it is possible to find separators explicitly in an unsuperwised manner. This can be approached by finding symbols that are most independent from their surrounding = minimum mutual information with the neighbours or minimum log likelihood ratio. But, unlike what Anton already did, this can be done across the corpus, not per locus. What do you @akolonin @linas think?

The above, if works, also does not solve the segmentation problem for writings without separators, like Chinese. To that end I was thinking about the definition of a word: "a speech sound or series of speech sounds that symbolizes and communicates a meaning usually without being divisible into smaller units capable of independent use". While the semantic part is hard to grasp computationally, the indivisability potentially can be. For example, I was thinking about the LZ78-type algorithm with some kind of corpus-wide optimization, but didn't quite come up with the target function (yet).

[akolonin]

Hi @linas can you email me your slides for your talk on August 19?
https://aigents.github.io/inlp/2022/
How long will it take?
Will 45 minutes for the talk and 14 minutes for discussion suit you?

[linas]

I haven't prepared the slide yet; i expect them to be similar to those of last year. yes, 45+14 is fine.

[akolonin]

@nickm197 we have got potentially relevant reference to our work https://www.researchgate.net/publication/361505964_Estimating_Sentence-like_Structure_in_Synthetic_Languages_Using_Information_Topology/references

[nickm197]

Interesting, thank you - I'll take a look

[linas]

Hi Nick, I want to continue the conversation but have been distracted by other matters. Are you in (or would you be able to get to) Europe next month?

[akolonin]

@linas @nickm197 we will meet on Aug 19, check your email and workshop agenda - need your slides by then ;-) https://aigents.github.io/inlp/2022/

[akolonin]

@linas - you are about to present on Aug 19 at https://aigents.github.io/inlp/2022/ and on Aug 22 at http://agi-conf.org/2022/schedule/
We need your slides and yourself to to the test Zoom call before. Please check your email and reply.