Re: QI and MQ Coder: First real-life experiences

> Look, I don't want to diminish your work, and that's why this
> "nothing but" is in quotes.

I am only concerned about misunderstanding. It tells me that,
however unlikely:), I might not be explaining it well (that is
indeed a complaint from almost everyone except for the few who
have spent lots of time and effort on the very same circle of
the EC problems, the coding or modeling aspects). In a way it
is a good sign, usually indicating some distance from the
ordinary. (Of course, there are two directions away from
the middle.)

> However, that's the QI coder model

ECMP: The QI "model" (modeling pattern, [T2] p.27) is to
partition (which is some form of decomposition) of the
input sequence into elements of some "enumerative classes"
(sets with ranking functions), followed by ranking of
the elements within their classes and encoding of the
class identifiers (class tags). The latter portion of
the output, can invoke [ECMP] with 'class tags' as
a new and separate input (iterative scheme called
"entropy pump" in [T2]).

> and the question remains why this is a good model.

Assuming the correct "this", the [ECMP], Davisson has answered
[31] this question over three decades ago: It is because
enumeration is "minimax universal". More specifically, consider
a set of all (decodable:) codes C(n,z) (where z labels different
code sets, or coders which compute them) for sequences limited
to n symbols, and where these n-sequences are emitted by some
parametrized class of sources S(n,t) (t=souce parameters). Now
you obtain the average redundancy for each coder 'z' for some
parameters t, the value R(n,z,t) in bits per symbol, then find
the source parameters value tz for which the average redundancy
R(n,z,tz)=[def]=R(n,z) is the largest for that coder (the "max"
part of minimax) i.e. R(n,z) is the worst average redundancy for
a given coder z over all source parameters t. Now you pick the
coder zm with the lowest R(n,z) among all possible coders z,
R(n,zm) =< R(n,z) for all z (the "min" part of minimax). If
R(n,zm) then goes to 0 when n->infinity, then this coder zm (or,
equivalently, its codes) is called minimax universal. And this
zm, the "most desirable" among them all, is the exact enumerative
coder, for variety of source types, including the arbitrary
finite order Markov sources ([28],[33]).

One can thus say that EC is the most resilient against
uncertainties among the coders (the unlimited precision AC, the
ACX, is merely an approximation of EC, hence EC _always_, for
any t, codes tighter than ACX, not just for the single tz value
that Davisson's minimax criterium requires). The QI, being the
_closest finite precision_ coder to the EC, is thus the most
resilient among the finite precision coders. And similarly to
their infinite precision counterparts, regarding the finite
precision AC, QI _always_, for any t, codes tighter than AC i.e.
it has lower redundancy R(n,z,t) for any t & n. In addition to
inheriting the EC vs ACX relation, due to the QI's optimal
quantization (with 4 or more times smaller 'quantization leak'
than AC), QI is doubly 'always tighter' than AC, at any given
arithmetic precision.

That's all without even getting to the QI's advantages in
speed and power consumption (A1), in output stability and
availability (A4), in richer and finer grained parametrization
of finite sequences (A2) (cf. [M1] for A1-A4).

At a more fundamental level, the reason behind the greater
'resilience' (the mimimax universality) of enumerative approach,
for the "real life" finite sequences, is the natural tendency
toward the economy in number of choices (standardization,
uniformization) that characterizes any "natural system" seeking
its optimum (homeostasis, omega point). Namely, the "natural
systems" (from genetic networks, cells, to human immune systems
and brains, to social networks, whole societies and ecosystems,
languages, formalisms and other networks in abstract realms)
are intelligent networks or 'complex systems' [SF], which model
their environments. These models include a model of "self",
which the network runs forward in a what-if game, like a chess
player looking at the moves ahead, enumerating the branching
tree of variants, pruning some and evaluating others, and
selecting the one which yields the optimum "punishments/rewards".
Reducing its cost for these computations, reducing the number
of possible variants that need to be examined, hence the time
and resources needed to compute the steps of its model, is a
very powerful omnipresent 'reward', hence all such systems
seek states with fewer variants to examine, which leads to
standardization and uniformization, and on individual "cell"
level to specializations and preference for routine, rhythms,
periodicity... etc.

The enumerative approach to modeling (ECMP) seeks to
identify the boundaries of these reduced choice spaces,
within which the number of choices is much smaller than
all that is allowed by the blind chance at that level.

The core premise of ECMP is that such boundaries and
the reduced choice sets (enumerative classes) enclosed
inside do exist. And the above is the fundamental reason
for that to be so. That is why the QI way of modeling is
a fundamentally sound method for modeling "real life"
sequences, regardless of particular technical definitions
of redundancy, resilence to "surprises"... etc.


>> For example, the bit planes would be coded much
>> better if one were coding separate fragments in
>> each bit plane, conditioned on the bit values above
>> (in the higher level bit planes),...
>
> Apparently, you haven't yet read thru the code completely
> since this is exactly what happens for the MQ *and* the
> QI implementation. Grey coding is exactly that: It
> "predicts" the value of the current bitplane with that
> of the bitplane above.

You didn't exactly hide it in the code, which says so
plainly:


** bitplane decorrelation by grey-coding
*/
code ^= (code >> 1);
/*

The problem is that Gray code is only a heuristic which may or
may not work, even as just an approximate decorrelator. And
it certainly is not the exact decorrelator as the A-1 node full
tree decomposition to bit planes and their precise plane
fragments (cf [T1]) that I was suggesting. For AC, and
especially for MQ, the coder noise and excess, along with the
coarse grained parametrization, for the small outputs makes the
separate plane fragment coding out of reach. Hence, the whole
bitplane is melded into one coding input, with a little bit of
Gray code on top, as a 'lucky charm'.

Just consider what the "melding" of the two plane fragments
(these are normally interleaved) F0=000...0 and F1=111..1 of n
bits each does to the output size: the 2*log(n) bit output blows
up into a 2*n bit output (which is the phenomenon illustrated in
the row "Vary" in [T4] and p.10 [T3]). These kinds of problems
with "melding" of exact bit plane fragments into a single bit
plane are even more pronounced in the image coding.

As pointed out in (A2), the high precision, low noise coder
allows one to code optimally these kinds of small (which are
also often interleaved) bit plane fragments, provided one does
no rounding up of the encoded fragments to the next whole bit,
or god forbid, to the next whole byte. These AC rounding up
habits are mostly automated unconscious actions since the AC
index normalization to 1.0 obliterates the index 'bit fraction',
hence the concept of 'index bit fraction' is completely foreign
to most AC programmers (unless they read Rissanen's early AC
papers [5],[27], where the codeword bit fractions and codeword
overlaps have a key part in the story on generalized Kraft
inequality).

The neat part with the enumerative coding of bit plane fragments
is that the original symbol counts give the exact bit fragments,
their uncompressed interleaved layouts, their 'counts of ones'
and their precise compressed sizes (so one can e.g. code them in
one pass into precomputed tightly packed back-to-back slots
ready to ship).


>> Due to non-stationarity, the key problem is how to get
>> a good segmentation.
>
> Yes, sure. For MQ, this is not a problem since it is
> an adaptive AC coding algorithm: It "finds" the
> statistics by slowly adapting into it, and by using
> a "fast attack" entry cycle to it is able to find the
> initial distribution quickly.

There is no basis to claim that "adaptive" way of determining
the segment boundaries is the "best" or even a "good" way to do
it, in any sense, let alone in every sense. It is just one way,
a round about and imprecise, done in half hearted nudges (it's
also done bit by bit in the middle of the coding loop, hence
dragging the speed down), to state a very simple fact such as:
this is where segment S0 ends and where segment S1 starts, which
is how descriptive modeler would say it, once it determined the
segment boundaries in a straightforward manner (e.g. via the
methods suggested earlier).

Finding it and transmitting it 'adaptively' is "simple" because
it is so coarse and leaky and, even more importantly, because
someone had already thought it up decades ago and it was
implemented in the coders, taught to students and it comes ready
to use, so one doesn't need to invent it. In every other
respect, it is inferior to directly measuring the property of
interest in a way suited to the property itself, and then
plainly reporting the precise results in terms closest to the
quantity measured.



-- References ( http://www.1stworks.com/ref/RefLib.htm )

28. L.D. Davisson "Universal noiseless coding"
IEEE Trans. Inform. Theory IT-19 (6), 783-795, 1973
http://cg.ensmp.fr/~vert/proj/bibli/local/Davisson1973Universal.pdf

33. R. Krichevsky, V. Trofimov
"The performance of universal encoding"
IEEE Trans. Inform. Theory IT-27 (2), 199-207, 1981

http://cg.ensmp.fr/~vert/proj/bibli/local/Krichevsky1981performance.pdf

12. J.C. Lawrence "A new universal coding scheme for the
binary memoryless source"
IEEE Trans. Inform. Theory IT-23 (4), 466-472, 1977
http://citeseer.ist.psu.edu/lawrence77new.html

T1. R.V. Tomic "Fast, optimal entropy coder"
1stWorks TR04-0815, 52p, Aug 2004
http://www.1stworks.com/ref/TR/tr04-0815b.pdf

T2. R.V. Tomic "Quantized indexing: Background information"
1stWorks TR05-0625, 39p, Jun 2005
http://www.1stworks.com/ref/TR/tr05-0625a.pdf

T3. R.V. Tomic "Quantized Indexing: Beyond Arithmetic Coding"
arXiv cs.IT/0511057, 10p, Nov 2005
http://arxiv.org/abs/cs.IT/0511057

T4. One page summary of [T3]
http://www.1stworks.com/ref/TR/DCC2006.pdf


M1. -- Summary of QI algorithmic advances (A1)-(A4)
http://groups.google.com/group/comp.compression/msg/27c6f329038a1bdc

SF. Santa Fe Institute (of "Complexity science")
http://www.santafe.edu/

.

Relevant Pages

  • Re: QI and MQ Coder: First real-life experiences
    ... to compress as well. ... Now, if you want some other coding conditions, e.g. to include ... That's the gap that a competing coder has ... precision of g bits, and requiring that the codewords satisfy Kraft ...
    (comp.compression)
  • Re: QI and MQ Coder: First real-life experiences
    ... > enumeration is "minimax universal". ... > you obtain the average redundancy for each coder 'z' for some ... enumerative coding is best for "interesting" sources. ... > the segment boundaries is the "best" or even a "good" way to do ...
    (comp.compression)
  • QI and MQ Coder: First real-life experiences
    ... The test application is a mildly drilled-up QI coder source from 1st Works, as found on their web-page, ported for Unix and equipped with a very simplistic audio codec front-end, consisting of a linear predictor and a bitplane context modelling. ... QI was used in the largest possible block size, MQ coding with its default context update tables. ... int code = 0; unsigned char outbuffer; /* ** Encode the number of bits. ...
    (comp.compression)
  • Re: QI and MQ Coder: First real-life experiences
    ... the information theory or coding classes, ... Or do a pure order-0 tests, using QI's bit counting and flagging ... Or measure nanosec/sym on your MQ coder and compare to similar ... On each of these C segments, say a segment of size N bits, one ...
    (comp.compression)
  • Re: QI and MQ Coder: First real-life experiences
    ... the general approach used here is typical for my applications for entropy coder back-ends: Decorrelation, context modelling and entropy coding. ... To test speeds, I would change MQ to code memory ...
    (comp.compression)