from tunny to the semantic web, via conditional random fields (and hidden markov models)


For Turing in 1939 faced with certain “programming” problems, he had of course under his belt his own programming language for pattern matching:

image

See http://www3.wittenberg.edu/bshelburne/Turing.htm

From his interaction with the rest of the Cambridge and Princeton schools of “programming” (folks researching abstract mathematical topology theory), he also had an underlying theory of networks and state machine (or “finite state automata” as we call them today)

see http://en.wikipedia.org/wiki/Von_Neumann_cellular_automata

While some of these research tools may have been focused on understanding and defining the nature of a universal machine (a programmable machine capable of replicating to “some degree”) and its logical limits, folks were not unfamiliar with more applied automata designs exploiting the notions, including local neighborhood analysis and probabilistic reasoning about “cliques”. The “generative” markov model is a nice analog of the kinds of generators learned in group theory, linking networks within abstract groups to language design. (See url: http://en.wikipedia.org/wiki/Markov_random_field.)

In particular:

image

image

image

See PowerPoint Presentation (doesn’t this last part in particular remind one of skipjack design!)

But the problem Turing faced in 1939 with cryptanalysis was a pattern recognition problem, not a pattern generation problem. How would we have seen the tools described above as being relevant to this shift of perspective?

If we look at the modern conception of the conditional random field

image

Majoros WH (2007) Conditional Random Fields. Online supplement to: Methods for Computational Gene Prediction, Cambridge University Press.

at http://geneprediction.org/book/CRFs.pdf

we get a glimpse of the tool s available to solving the cryptanalytical problems of the day, back in 1939. Given a set of depths of naval enigma indicators and the application of “scrithmus” to chains of resulting character mappings in the various part of the enigma mechanism, we see application of “network” programming models not only to the menus of the Bombe design but to inference more generally:

Scritchmus

Scritchmus was the part of the Banburismus procedure that could lead to the identification of the right-hand (fast) wheel. The Banburist might have evidence from various message-pairs (with only the third indicator letter differing) showing that “X = Q-2″, “H = X-4″ and “B = G+3″. He or she[20] would search the deciban sheets for all distances with odds of better than 1:1 (i.e. with scores ≥ +34). An attempt was then made to construct the ‘end wheel alphabet’ by forming ‘chains’ of end-wheel letters out of these repeats.[21] They could then construct a “chain” as follows:

G--B-H---X-Q

If this is then compared at progressive offsets with the known letter-sequence of an Enigma rotor, quite a few possibilities are discounted due to violating either the “reciprocal” property or the “no-self-ciphering” property of the Enigma machine:

G--B-H---X-Q
ABCDEFGHIJKLMNOPQRSTUVWXYZ  ......... is possible

 G--B-H---X-Q
ABCDEFGHIJKLMNOPQRSTUVWXYZ  ......... is impossible (G enciphers to B, yet B enciphers to E)

  G--B-H---X-Q
ABCDEFGHIJKLMNOPQRSTUVWXYZ  ......... is impossible (H apparently enciphers to H)

   G--B-H---X-Q
ABCDEFGHIJKLMNOPQRSTUVWXYZ  ......... is impossible (G enciphers to D, yet B enciphers to G)

    G--B-H---X-Q
ABCDEFGHIJKLMNOPQRSTUVWXYZ  ......... is impossible (B enciphers to H, yet H enciphers to J)

     G--B-H---X-Q
ABCDEFGHIJKLMNOPQRSTUVWXYZ  ......... is impossible (Q apparently enciphers to Q)

      G--B-H---X-Q
ABCDEFGHIJKLMNOPQRSTUVWXYZ  ......... is impossible (G apparently enciphers to G)

       G--B-H---X-Q
ABCDEFGHIJKLMNOPQRSTUVWXYZ  ......... is impossible (G enciphers to H, yet H enciphers to M)

        G--B-H---X-Q
ABCDEFGHIJKLMNOPQRSTUVWXYZ  ......... is possible

         G--B-H---X-Q
ABCDEFGHIJKLMNOPQRSTUVWXYZ  ......... is possible

          G--B-H---X-Q
ABCDEFGHIJKLMNOPQRSTUVWXYZ  ......... is possible

           G--B-H---X-Q
ABCDEFGHIJKLMNOPQRSTUVWXYZ  ......... is impossible (H enciphers to Q, yet Q enciphers to W)

            G--B-H---X-Q
ABCDEFGHIJKLMNOPQRSTUVWXYZ  ......... is impossible (X enciphers to V, yet Q enciphers to X)

             G--B-H---X-Q
ABCDEFGHIJKLMNOPQRSTUVWXYZ  ......... is impossible (B enciphers to Q, yet Q enciphers to Y)

              G--B-H---X-Q
ABCDEFGHIJKLMNOPQRSTUVWXYZ  ......... is impossible (X enciphers to X)

Q              G--B-H---X->
ABCDEFGHIJKLMNOPQRSTUVWXYZ  ......... is possible

-Q              G--B-H---X->
ABCDEFGHIJKLMNOPQRSTUVWXYZ  ......... is impossible (Q enciphers to B, yet B enciphers to T)

X-Q              G--B-H--->
ABCDEFGHIJKLMNOPQRSTUVWXYZ  ......... is possible

-X-Q              G--B-H-->
ABCDEFGHIJKLMNOPQRSTUVWXYZ  ......... is impossible (X enciphers to B, yet B enciphers to V)

--X-Q              G--B-H->
ABCDEFGHIJKLMNOPQRSTUVWXYZ  ......... is possible

---X-Q              G--B-H->
ABCDEFGHIJKLMNOPQRSTUVWXYZ  ......... is impossible (X enciphers to D, yet B enciphers to X)

H---X-Q              G--B->
ABCDEFGHIJKLMNOPQRSTUVWXYZ  ......... is impossible (Q enciphers to G, yet G enciphers to V)

-H---X-Q              G--B->
ABCDEFGHIJKLMNOPQRSTUVWXYZ  ......... is impossible (H enciphers to B, yet Q enciphers to H)

B-H---X-Q              G-->
ABCDEFGHIJKLMNOPQRSTUVWXYZ  ......... is possible (note the G enciphers to X, X enciphers to G property)

-B-H---X-Q              G->
ABCDEFGHIJKLMNOPQRSTUVWXYZ  ......... is impossible (B enciphers to B)

--B-H---X-Q              G->
ABCDEFGHIJKLMNOPQRSTUVWXYZ  ......... is possible

The so called “end-wheel alphabet” is already limited to just nine possibilities, merely by establishing a letter-chain of five letters derived from a mere four message-pairs. Hut 8 would now try fitting other letter-chains — ones with no letters in common with the first chain — into these nine candidate end-wheel alphabets.

Eventually they will hope to be left with just one candidate, maybe looking like this:

         NUP
F----A--D---O
--X-Q              G--B-H->
ABCDEFGHIJKLMNOPQRSTUVWXYZ

Not only this, but such an end-wheel alphabet forces the conclusion that the end wheel is in fact “Rotor I”. This is because “Rotor II” would have caused a mid-wheel turnover as it stepped from “E” to “F”, yet that’s in the middle of the span of the letter-chain “F—-A–D—O”. Likewise, all the other possible mid-wheel turnovers are precluded. Rotor I does its turnover between “Q” and “R”, and that’s the only part of the alphabet not spanned by a chain.

See http://en.wikipedia.org/wiki/Banburismus

Now, we must not forget the steps that got to Scrithmus. First, Turing built for a particular decoding problem (the size of overlaps and repeat rates of unigrams, bigrams, trigrams etc) his “factorization” model, reduced to the #decibans that any encountered n-gram would add to the accumulating weight of evidence (that a (indicator) depth had indeed been found). This of course means that the art of conditional probabalistic reasoning had already been built in, since he is using calculations based on conditional probabilities rather than joint probabilities.

This all of course gets us much closer to the research topics of the semantic web (url) =- concerning natural language processing, generating ontologically-sound statements, etc!

underlying all of this (in modern conceptions) is the conditional random field. What was the core of the method used in both enigma and tunny breaks? it was the ability to predict the bias due to the generating conditions and from the evidence of the observables (the ciphertext) compute the unobservables (the wheel on the pinwheels of tunny)

image

See PowerPoint Presentation

Folks were using “conditional random fields” all along, as a machine learning algorithm in its purest form – learning from the evidence the infer the generating conditions (the pin wheels).

image

image

see http://geneprediction.org/book/CRFs.pdf

In general, we have reached for and arrived at the art of machine learning, of course. we heard the argument given above before!

image

http://www.alanturing.net/turing_archive/archive/t/t07/TR07.php

Staying just within HMMs, one see his history of stochastic matrices that apply conditional reasoning:

image

image

image

From http://www.cs.sjsu.edu/faculty/stamp/RUA/HMM.pdf

Of course,we saw this all applied in the Tunny era (and the later Colossus era), when folks were “converging rectangles” whose cells contained the inner bias (conditional probability equation defining the “conditional random field”) of a particular two impulse streams, and from which one wanted to infer the generating conditions (the pin wheels)

image

See http://ellsbury.com/tunny/tunny-116a.htm, and http://www.alanturing.net/turing_archive/archive/t/t07/TR07.php

About these ads

About home_pw@msn.com

http://yorkporc.wordpress.com/about-2/
This entry was posted in colossus, crypto. Bookmark the permalink.

One Response to from tunny to the semantic web, via conditional random fields (and hidden markov models)

  1. Pingback: modern cake icing | Peter's ruminations

Comments are closed.