4. Measurement


This sectionPlanetmathPlanetmathPlanetmathPlanetmathPlanetmath adapts Definitionย 1 (http://planetmath.org/1introduction#Thmdefn1) to distributed stochastic systems. The first step is to replace elements of state spacePlanetmathPlanetmath X with stochastic maps diโขn:โ„โ†’๐’ฑโขS๐ƒ, or equivalently probability distributions on S๐ƒ, which are the systemโ€™s inputs. Individual elements of S๐ƒ correspond to Dirac distributions.

Second, replace function f:Xโ†’โ„ with mechanism ๐”ช๐ƒ:๐’ฑโขS๐ƒโ†’๐’ฑโขA๐ƒ. Since we are interested in the compositional structureMathworldPlanetmath of measurements we also consider submechanisms ๐”ช๐‚. However, comparing mechanisms requires that they have the same domain and range, so we extend ๐”ช๐‚ to the entire system as follows

๐”ช๐‚=๐’ฑโขS๐ƒโ†’๐œ‹๐’ฑโขS๐‚โ†’๐”ช๐‚๐’ฑโขA๐‚โ†’ฯ€โ™ฎ๐’ฑโขA๐ƒ. (1)

We refer to the extensionPlanetmathPlanetmath as ๐”ช๐‚ by abuse of notation. We extend mechanisms implicitly whenever necessary without further comment. Extending mechanisms in this way maps the quale into a cloud of points in Homโก(๐’ฑโขA๐ƒ,๐’ฑโขS๐ƒ) labeled by objects in ๐š‚๐šข๐šœ๐ƒ.

In the special case of the initial objectMathworldPlanetmath โŠฅ๐ƒ, define

๐”ชโŠฅ=๐’ฑโขS๐ƒโ†’๐œ”โ„โ†’ฯ‰โ™ฎ๐’ฑโขA๐ƒ.
Remark 3.

Subsystems differing by non-existent edges (Remarkย 2 (http://planetmath.org/3distributeddynamicalsystems#Thmrem2)) are mapped to the same mechanism by this construction, thus making the fact that the edges do not exist explicit within the formalism.

Composing an input with a submechanism yields an output doโขuโขt:=๐”ช๐‚โˆ˜diโขn:โ„โ†’๐’ฑโขA๐ƒ, which is a probability distribution on A๐ƒ. We are now in a position to define

Definition 8.

A measuring device is the dual ๐”ช๐‚โ™ฎ to the mechanism of a subsystem. An output is a stochastic map doโขuโขt:โ„โ†’๐’ฑโขA๐ƒ. A measurement is a composition ๐”ช๐‚โ™ฎโˆ˜doโขuโขt:โ„โ†’๐’ฑโขS๐ƒ.

Recall that stochastic maps of the form โ„โ†’๐’ฑโขX correspond to probability distributions on X. Outputs as defined above are thus probability distributions on A๐ƒ, the output alphabetMathworldPlanetmath of ๐ƒ. Individual elements of A๐ƒ are recovered as Dirac vectors: โ„โ†’ฮดa๐’ฑโขA๐ƒ.

Definition 9.

The effective information generated by ๐‚1 in the context of subsystem ๐‚2โŠ‚๐‚1 is

ei(๐”ช๐‚2โ†’๐”ช๐‚1,doโขuโขt):=H[๐”ช๐‚1โ™ฎโˆ˜doโขuโขtโˆฅ๐”ช๐‚2โ™ฎโˆ˜doโขuโขt]. (2)

The null context, corresponding to the empty subsystem โŠฅ=โˆ…โŠ‚V๐ƒร—V๐ƒ, is a special case where ๐”ช๐‚โ™ฎโˆ˜doโขuโขt is replaced by the uniform distributionMathworldPlanetmath ฯ‰๐ƒโ™ฎ on S๐ƒ. To simplify notation define

ei(๐”ช๐‚,doโขuโขt):=ei(๐”ชโŠฅโ†’๐”ช๐‚,doโขuโขt).

Here, H[pโˆฅq]=โˆ‘ipilog2piqi is the Kullback-Leibler divergence or relative entropyMathworldPlanetmath [1]. Eq.ย (2) expands as

ei(๐”ช๐‚2โ†’๐”ช๐‚1,doโขuโขt)=โˆ‘sโˆˆS๐ƒโŸจ๐”ช๐‚1โ™ฎโˆ˜doโขuโขt|ฮดsโŸฉโ‹…log2โŸจ๐”ช๐‚1โ™ฎโˆ˜doโขuโขt|ฮดsโŸฉโŸจ๐”ช๐‚2โ™ฎโˆ˜doโขuโขt|ฮดsโŸฉ. (3)

When doโขuโขt=ฮดa for some aโˆˆA๐ƒ we have

ei(๐”ช๐‚2โ†’๐”ช๐‚1,ฮดa)=โˆ‘sโˆˆS๐ƒp๐”ช๐‚1(s|a)โ‹…log2p๐”ช๐‚1(s|a)p๐”ช๐‚2(s|a). (4)

Definitionย 8 requires some unpacking. To relate it to the classical notion of measurement, Definitionย 1 (http://planetmath.org/1introduction#Thmdefn1), we consider system ๐ƒ={vXโ†’๐‘“vY} where the alphabets of vX and vY are the sets AvX=X and AvY=Y respectively, and the mechanism of vY is ๐”ชY=๐’ฑโขf. In other words, system ๐ƒ corresponds to a single deterministicMathworldPlanetmath function f:Xโ†’Y.

Proposition 5 (classical measurement).

The measurement (Vโขf)โ™ฎโˆ˜ฮดy performed when deterministic function f:Xโ†’Y outputs y is equivalentMathworldPlanetmathPlanetmathPlanetmathPlanetmathPlanetmath to the preimageMathworldPlanetmath f-1โข(y). Effective information is eโขiโข(Vโขf,ฮดy)=log2โก|X||f-1โข(y)|.

Proof: By Corollaryย 2 (http://planetmath.org/2stochasticmaps#Thmthm2) measurement (๐’ฑโขf)โ™ฎโˆ˜ฮดy is conditional distribution

p๐’ฑโขf(x|y)={1|f-1โข(y)|ifย โขfโข(x)=y0else.

which generalizes the preimage. Effective information follows immediately. โ– 

Effective information can be interpreted as quantifying a measurementโ€™s precision. It is high if few inputs cause f to output y out of many โ€“ i.e. f-1โข(y) has few elements relative to |X| โ€“ and conversely is low if many inputs cause f to output y โ€“ i.e. if the output is relatively insensitive to changes in the input. Precise measurements say a lot about what the input could have been and conversely for vague measurements with low eโขi.

The point of this paper is to develop techniques for studying measurements constructed out of two or more functions. We therefore present computations for the simplest case, distributed system Xร—Yโ†’๐‘”Z, in considerable detail. Let ๐ƒ be the graph

with obvious assignments of alphabets and the mechanism of vZ as ๐”ชZ=๐’ฑโขg. To make the formulasMathworldPlanetmathPlanetmath more readable let ๐”ชXโขY=๐’ฑโขg, ๐”ชXโฃโˆ™=๐’ฑโขgโˆ˜ฯ€XโขY,Xโ™ฎ and ๐”ชโˆ™Y=๐’ฑโขgโˆ˜ฯ€XโขY,Yโ™ฎ. We then obtain latticeMathworldPlanetmath

The remainder of this section and most of the next analyzes measurements in the lattice.

Proposition 6 (partial measurement).

The measurement performed on X when g:Xร—Yโ†’Z outputs z, treating Y as extrinsic noise, is conditional distribution

p(x|z)={|gxร—Y-1โข(z)||g-1โข(z)|ifย โขgโข(x,y)=zโขย for someย โขyโˆˆY0else, (5)

where gxร—Y-1โข(z):=pโขrYโข(g-1โข(z)โˆฉ{x}ร—Y). The effective information generated by the partial measurement is

ei(๐”ชXโฃโˆ™โ™ฎ,ฮดz)=log2|X|+โˆ‘xโˆˆXp(x|z)โ‹…log2p(x|z).ฮดz)|g-1(z)|โ‹… (6)

Proof: Treating Y as a source of extrinsic noise yields ๐’ฑโขXโ†’ฯ€โ™ฎ๐’ฑโขXโŠ—๐’ฑโขYโ†’๐’ฑโขg๐’ฑโขZ which takes ฮดxโ†ฆ1|Y|โขโˆ‘yโˆˆYฮดgโข(x,y). The dual is

๐”ชXโฃโˆ™โ™ฎ=ฯ€XโขY,Xโˆ˜(๐’ฑโขg)โ™ฎ:ฮดzโ†ฆโˆ‘xโˆˆX|gxร—Y-1โข(z)||g-1โข(z)|โ‹…ฮดx.

The computation of effective information follows immediately. โ– 

A partial measurement is precise if the preimage g-1โข(z) has small or empty intersectionMathworldPlanetmathPlanetmath with {x}ร—Y for most x, and large intersection for few x.

PropositionsPlanetmathPlanetmathย 5 and 6 compute effective information of a measurement relative to the null context provided by completePlanetmathPlanetmathPlanetmathPlanetmathPlanetmath ignorance (the uniform distribution). We can also compute the effective information generated by a measurement in the context of a submeasurement:

Proposition 7 (relative measurement).

The information generated by measurement Xร—Yโ†’๐‘”Z in the context of the partial measurement where Y is unobserved noise, is

ei(๐”ชXโฃโˆ™โ†’๐”ชXโขY,ฮดz)=โˆ‘xโˆˆXgxร—Y-1โข(z)g-1โข(z)log2|Y|gxร—Y-1โข(z). (7)

Proof: Applying Propositionsย 5 and 6 obtains

ei(๐”ชXโฃโˆ™โ†’๐”ชXโขY,ฮดz)=โˆ‘(x,y)โˆˆg-1โข(z)1|g-1โข(z)|log2[1|g-1โข(z)|โ‹…|g-1โข(z)|โ‹…|Y||gxร—Y-1โข(z)|]

which simplifies to the desired expression. โ– 

To interpret the result decompose Xร—Yโ†’๐‘”Z into a family of functions โ„›={Yโ†’gxร—YZ|xโˆˆX} labeled by elements of X, where gxร—Yโข(y):=gโข(x,y). The precision of the measurement performed by gxร—Y s log2โก|Y|gxร—Y-1โข(z). It follows that the precision of the relative measurement, Eq.ย (7), is the expected precision of the measurements performed by family โ„› taken with respect to the probability distribution p(x|z)=gxร—Y-1โข(z)g-1โข(z) generated by the noisy measurement.

In the special case of g:Xร—Yโ†’Z relative precision is simply the difference of the precision of the larger and smaller subsystems:

Corollary 8 (comparing measurements).
ei(๐”ชXโฃโˆ™โ†’๐”ชXโขY,ฮดz)=ei(๐”ชXโขY,ฮดz)-ei(๐”ชXโฃโˆ™,ฮดz)

Proof: Applying Propositionsย 5, 6, 7 and simplifying obtains

eโขiโข(๐”ชXโขY,ฮดz)-eโขiโข(๐”ชXโฃโˆ™,ฮดz) =log2โก|X|โ‹…|Y||g-1โข(z)|-โˆ‘x|gxร—Y-1โข(z)||g-1โข(z)|โขlog2โก|X|โ‹…|gxร—Y-1โข(z)||g-1โข(z)|
=log2โก|Y||g-1โข(z)|+โˆ‘(x,y)โˆˆg-1โข(z)1|g-1โข(z)|โขlog2โก|g-1โข(z)||gxร—Y-1โข(z)|
=ei(๐”ชXโฃโˆ™โ†’๐”ชXโขY,ฮดz).โ– 

References

  • 1 Eย T Jaynes (1985): EntropyMathworldPlanetmath and Search Theory. In CRย Smith & WTย Grandy, editors: Maximum-entropy and Bayesian Methods in Inverse Problems, Springer.
Title 4. Measurement
Canonical name 4Measurement
Date of creation 2014-04-22 19:36:22
Last modified on 2014-04-22 19:36:22
Owner rspuzio (6075)
Last modified by rspuzio (6075)
Numerical id 6
Author rspuzio (6075)
Entry type Feature