In this paper we apply semifield-based Formal Concept Analysis (FCA) to the analysis of Information Harmoniums. These are unsupervised graphical models that, similarly to energy-based models, are written in terms of information functions, but whose expression is linear in an information semifield. In particular we concentrate in the case of the limit information semifields that are the completed max-plus and min-plus semifields for which strong representation theorems in relation to Galois connections and semifield-valued FCA have been proven. We center our contribution in the analysis of the representation spaces for visible and hidden nodes of Information Harmoniums and the lattices related to them.
Restricted Boltzmann Machines (RBM) [
RMBs are, in fact, a type of harmonium [
In this paper we put in evidence some discrepancies in the definition of harmoniums (Section 2.1) that suggest that a more natural point of view is to consider their energy functions as based in an information semifield (Section 2.2). If this is the case, a particular instance of the information semifields are the Rmax,+ and Rmin,+ semifields over which a multi-valued generalization of FCA can be defined, Rmax,+-FCA (Section 2.3). In Section 3 we present our results and contend that FCA in general, and Rmax,+-FCA in particular, provides a framework for the visualization and understanding of information harmoniums that could also provide clues for other types of harmoniums. Finally we provide some conclusions. ? Corresponding author.
The basic model. Technically speaking a harmonium is an undirected graphical model for the generation of a joint probability distribution. Their graphical model can be seen in Fig. 1.
state vectors ~ h ~v
~c ~ b
One type of nodes tagged with vl labels are the set of L input or observed nodes. The other type is the set of K output or hidden nodes, tagged with hk. Conventionally we will use indices l ∈ [1 . . . L] and k ∈ [1 . . . K] to go over them.
Harmoniums are generative models: consider random vectors V = {Vi | i ∈ I} and H = {Hj | j ∈ J } with component random variables Vi and Hj associated to the visible and hidden nodes, respectively. We posit that for a particular pair of random vector (values) (~v, ~h) ∈ V × H the joint probability distribution pV H of Figure 1 takes the form of a Boltzmann distribution, pV H (~v, ~h) =
e−βE(~v,~h) P ~v∈V
P~h∈H e−βE(~v,~h) where β ∈ (0, ∞] is a formal parameter, the coldness, and E(~v, ~h) is a provided energy function, given in terms of bias vectors ~b ∈ V , ~c ∈ H and the weight matrix W :
E(~v, ~h) = ~vt~c + ~bt~h + ~vtW~h
Several points are worth making here:
– The coldness parameter β is in the context of Physics often written as its
inverse, the temperature T = 1/β respecting the original form of the
Boltzmann’s function. It was not originally introduced in the Harmonium [
E0(~v, ~h | W 0) = a + E(~v, ~h | W |a=0) and it may be used, for instance, to ensure that the joint distribution is positive, that is, non-null for any ~v ∈ V, ~h ∈ H. We will not distinguish between these two forms and consider the W = W 0|a=0, including ~b and ~c, but not a, to be the set of parameters of the model pV H (~v, ~h | W 0|a=0). – Z(W ) = P~v∈V P~h∈H e−E(~v,~h|W ) is the well-known partition function that ensures the normalization of pV H|W . As argued, we will use sometimes Z(W 0) = e−βa · Z(W ) to make it explicit that we include all possible parameters, including the minimal offset. In fact, the partition function can be included in the energy function by defining a = Fβ (W |k=0) = β1 loge Z(W |k=0) in which case
Z(W 0) = e−βFβ(W ) · Z(W |k=0) = Z(W |k=0)−1 · Z(W |k=0) = 1
so that pV H (~v, ~h) = e−βE(~v,~h|W 0) with an explicit normalization.
– With this encoding, the number of free parameters of this model is (L +
1)(K + 1) − 1 [
Inference in harmoniums. As mentioned, RBM are harmoniums that can
also be seen as PoE [
Y pHj|V (hj | ~v0, W ) pV |H (~v | ~h0, W ) = j i Y pVi|H (vi | ~h0, W ) (3)
In fact, RBMs are harmoniums with Bernouilli-distributed binary visible and
hidden variables (see below) [
Positive semifields. A technical requisite for the energy function is that it
is always positive [
1 ur + vr r u ⊗r v =
1
ur × vr r
1
ur
1
r
u∗ =
= u−1
(4)
where the basic operations are to be interpreted in R≥0 and the dotted notation
is adopted from that used by Moreau for convex analysis [
R−≥01 r . In particular: – if r ∈ [−∞, 0) then u⊗r v = u ⊗r v = u × v, ⊥r = ∞, er = 1, and >r = 0, and the complete positive semifield generated, dually order-aligned with R≥0, is: (R≥0)−r = h[0, ∞], ⊕r, ⊗r, ·∗, ⊥r∗ = ∞, e, >r∗ = 0i Therefore, (R≥0)r and (R≥0)−r are inverse, completed positive semifields, (R≥0)1 = R≥0 lim (R≥0)r = Rmax,× r→∞ (R≥0)−1 = R−≥01 lim (R≥0)r−1 = Rmin,× r→−∞
Note that: – these semifields are able to capture the usual concept of a “positive quantity”, like a mass, length, etc. – All these semifields have the same product, and the same “extreme” points, {0, 1, ∞} . Their only difference lies in the addition. Sometimes, when only the product is important in an application, the addition remains in the background and we are not really sure in which algebra we are working on. – Instead of using the abstract notation for the inversion ·∗, since R≥0 is the paragon originating all other behaviours, we have decided to use the original notation for the inversion in the (incomplete) semifield.
The need for information functions. If we were to use the semifields (R≥0)r to build the energy function of the harmonium model (1), despite the fact that these semifields are positive, and they generate models that are products of positive terms, from a physical point of view there is a mismatch between them (5) (6) (7) (8) tu and the numbers required in the model: these semifields describe natural measurements of mass, length, etc., but model (1) demands that we use logarithmic magnitudes.
A first step is to use an information function to transform normalized masses,
that is, something akin to probabilities, into (quantity of ) information. Hartley’s
information function h(p) = − log2 p, p ∈ [
Hr = h[−∞, ∞], ⊕r, ⊗r, −·, ⊥ = −∞, e = 0, > = ∞i −Hr = h[−∞, ∞], ⊕r, ⊗r, −·, −⊥ = ∞, e = 0, −> = −∞i whose elements can be considered as generalized information values and operated accordingly. We will typically consider b = e1 so that loge(m) = log(m) and the informations and entropies are measured in nats.
It is easy to see that addition is a very complicated operation in information semifields in general: For r ∈ R/{0} we expand the notation for addition as: Xr
i X i
hi , hi ⊕r h2 ⊕r . . . = − 1r log(X e−rhi ) r hi , hi ⊕r h2 ⊕r . . . = − 1r log(X e−rhi ) i i r ∈ (0, ∞] r ∈ [−∞, 0)
Xr It is easy to see that Xri hi smoothly approximates the maximum, since:
i hi is smooth approximation to the minimum while i X• hi , lim r→∞
Xr i hi = min hi i
i • X hi , Xr hi = max hi
i i In this case, the dually ordered complete positive semifields have an idempotent addition, and are normally called the (completed) max-plus Rmax,+ and min-plus Rmin,+ semifields, or tropical semirings. (9) (10) (11) (12) (13) (14) h~x|W |~yir =4 ~xt ⊗r W ⊗r ~y = xi ⊕r wij ⊕r yj = −1 log r
X e−r(xi + wij + yj) i,j h~x|W |~yir =4 ~xt ⊗r W ⊗r ~y = X 1 r xi ⊕r wij ⊕r yj = r log
X er(xi + wij + yj)
Note that when ~h is a vector of generalized informations, the additions in (13) are clearly entropies—more precisely, cross entropies—hence the name assigned to this type of semifield. tu
It is difficult to ascertain in what algebra the computations inside the
logsum-exp functions in (13) are carried out. The following result was proven in [
Theorem 1 (The four-fold connection). Let G and M be sets of formal objects and formal attributes, respectively, with |G| = g and |M | = m . Let (cGom,Mple,tRe )iKdebmepaotefonrtmsaelmciofineltdexKt.wChoosnesiidnecridtehnecveecRto∈r sKpagc×ems Xtak=esKvgalauneds Yin =a Km, an invertible element ϕ = γ ⊗ μ ∈ K and the scaled spaces Xeγ = γ−1 ⊗ X and Yeμ = μ−1 ⊗ Y . Then 1. The bracket hx | R | yioi = x∗ ⊗ R ⊗ y−1 induces a Galois connection (·↑R, ·↓R) : Xeγ (* Yeμ between the scaled spaces through the polars x↑R = Rt ⊗ x−1 yR↓ = R ⊗ y−1 which define two bijective sets, the system of extents BγG and the system of μ intents BM
BγG = (Ye μ)↓
R
BM = (Xe γ )↑ μ
R (15) and whose composition generate closure operators: πR(x) = (x↑R)↓R = R ⊗(R∗ ⊗ x) πRt (y) = (yR↓)↑R = Rt ⊗(R−1 ⊗ y) which are the identities on BγG and BμM , respectively. 2. The bracket hx | R | yiio = xt ⊗ R ⊗ y induces a co-Galois connection (·↑R−1 , ·↓R−1 ) : Xeγ +) Yeμ between the scaled spaces through the maps: x↑R−1 = R∗ ⊗ x−1 yR↓−1 = R−1 ⊗ y−1 γ which define two bijective sets the systems of neighbourhoods of objects NG and neighbourhoods of attributes NμM (17) (18) (19) (20) (21) (22) (23) and whose composition generate interior operators:
NγG = (Ye μ)↓R−1
NμM = (Xe γ )↑R−1 κR−1 (x) = (x↑R−1 )↓R−1 = R−1 ⊗(Rt ⊗ x)
↑ κR∗ (y) = (yR↓−1 )R−1 = R∗ ⊗(R ⊗ y) which are the identities on NγG and NμM , respectively. 3. The bracket hx | R | yioo = x∗ ⊗ R ⊗ y induces a left adjunction (·∃R, ·∀R) : Xeγ Yeμ between the scaled spaces through the left adjunct pair of maps: x∃R = R∗ ⊗ x yR∀ = R ⊗ y which define another bijection between the systems of extents BγG and neighμ bourhoods of attributes NM
BγG = (Ye μ)∀
R πR(x) = (x∃R)∀R
NμM = (Xe γ )∃
R κR∗ (y) = (yR∀)∃R and whose compositions are the closure of extents and interior of attributes: 4. The bracket hx | R | yiii = xt ⊗ R ⊗ y−1 induces an adjunction on the right (·∀Rt , ·∃Rt ) : Xeγ Yeμ between the scaled spaces through the pair of adjunct maps: x∀Rt = Rt ⊗ x yR∃t = R−1 ⊗ y which define anothers bijection between the systems of neighbourhood of objects NγG and intents BM
μ NγG = (Ye μ)∃Rt
BM = (Xe γ )∀Rt μ and whose compositions are the interior of objects and the closure of attributes: κR−1 (x) = (x∀Rt )∃Rt πRt (y) = (yR∃t )∀Rt (26) Therefore, it makes sense to define the following (meta) concept: Definition 1. For a formal coγntext (G, M, R)K, thγe 4-formal conμcept (a, b, c, d) is a 4-tuple such that a ∈ BG, b ∈ BμM , c ∈ NG, and d ∈ NM and all the following relations hold: a = (b)↓R = (d)∀R d = (c)↑R−1 = (a)∃R b = (a)↑R = (c)∀Rt c = (d)↓R−1 = (b)∃Rt 3
(25)
(27)
(28)
(29)
Given the distinction between probability-based and information-based
semifields in Section 2.2, and considering that many sensorial magnitudes are
“logarithmically perceived”—despite the criticism to the Weber-Fenchner law [
Information Measures from Mass Measures We may further generalize R´enyi’s information function ϕ0−1(·) and its inverse ϕ0(·) to vectors, so if we consider a mass measure m ∈ [0, ∞]I , we have its related information measure: hr(·) : [0, ∞]I → [−∞, ∞]I −1 logb mi}i∈I m = {mi}i∈I 7→ hr(m) = {ϕ0−1(mi)}i∈I = { r whereas if we consider an information measure h ∈ [−∞, ∞]n, then we have its related mass measure: mr(·) : [−∞, ∞]I → [0, ∞]I h = {hi}i∈I 7→ mr(h) = {e−rhi }i∈I Note that the mr(·) and hr(·) thus defined are mutually inverse bijections of tuple spaces between the semifields. In particular we state without proving: Proposition 2. Let r ∈ [−∞, ∞] \ {0}. Then hr(·) : (R≥0)n → (Hr)n is a dual isomorphism of semivector spaces over their corresponding semifields, with inverse mr(·) : (Hr)n → (R≥0)n.
The duality mentioned in Proposition 2 concerns their natural orders. The Hartley information function, e.g. R´enyi’s function with r = 1 is a very special case: Corollary 1. The Hartley information function is a dual isomorphism of semivectors spaces h1(·) : (R≥0)n → (H)n .
The following is much more interesting and admits the previous one as a particular case: Proposition 3. The Hartley information function is a dual isomorphism of semivectors spaces hr(·) : ((R≥0)r)n → (Hr)n .
rj Proof. Let {αj ∈ R≥0 | j ∈ J } and {~vj ∈ (R≥0)rn − log αj and ~xj = − log ~vj . Then, a linear combination o|f jve∈ctoJrs} inwi(tRh≥a0j)rn=, X αj ⊗r ~vj is transformed into a linear combination of vectors in (Hr)n as − log X j 1/r r αj ⊗r ~vj = − log X αjr × ~vir
j = −1 log r
j X e−r(aj + ~xj) = −1 log r
X e−raj × e−r~xj =
X e−r(aj ⊗ ~xj) =
j = −1 log
r =
Xr j
j aj ⊗r ~xj which is a linear combination of vectors with modified scalars. Since the transformations are equalities and biunivocal it describes an isomorphism which is inverted by taking the negative exponential function on each of the terms. tu
In fact, we have also the following corollary: Corollary 2. Let {β~, ~v} ⊂ ((R≥0)r)n and {~b, ~x} ⊂ (Hr)n where β~ = exp(−~b) and ~v = exp(−~x). Then: ~b∗ ⊗ ~x = − log(β~∗ ⊗ ~v) β~∗ ⊗ ~v = exp(−~b∗ ⊗ ~x) (30) Proof. Just collect n of the scalars αj on a single vector β~ = {αj−1}in=1 and multiply by ~v as β~∗ ⊗ ~v. Then by the previous procedure we get ~b∗ ⊗ ~x = − log(β~∗ ⊗ ~v). The second equality comes from the isomorphism. tu 3.2
The relation between mass measures and information measures suggests we define harmoniums using information: Definition 2. Let X ≡ Hrn and Y ≡ Hrm be semivector spaces over the informational semifield Hr. Let ~x ∈ X and ~y ∈ Y be generalized information functions. We call an informational harmonium one whose joint information function is a scalar product between the spaces, with W ∈ (Hr)n×m, r hXY (·, · | W ) : X × Y → Hr
r (~x, ~y) 7→ hXY (~x, ~y | W ) = h~x|W |~yir
If the information functions are related to the mass distributions mX = m(~x) and mY = m(~y) by Hartley’s function, then the information harmonium is the associated mass function over the whole product space (~x, ~y) ∈ X × Y that is mXY (~x, ~y) = m(hXY (~x, ~y | W )) = {e−hrXY (~x,y~|W ) | ~x ∈ X , ~y ∈ Y} r with associated partition function and distribution kmXY k1 =
X
X e−hrXY (~x,y~|W ) ~x∈X y~∈Y q1(mXY ) = e−hrXY (~x,y~|W ) kmXY k1 (31) (32) tu Proposition 4. In the conditions of Definition 2, let ~v = exp(−~x), ~h = exp(−~y) and U = exp(W ) whereby we mean the entry-wise exponentiation. Then: r r mV H (~v, ~h | U ) = exp(−hXY (~x, ~y | W )) hXY (~x, ~y | W ) = − log(mV H (~v, ~h | U )) (33) Proof. This is just a repeating of the proof for Proposition 3.
When r → ∞ we have the following corollary: Corollary 3. In the conditions of Definition 2, let ~v = exp(−~x), ~h = exp(−~y) and U = exp(W ) whereby we mean the entry-wise exponentiation. Then: (~x)∗ ⊗ W ⊗ ~y = − log((~v)∗ × U × ~h) (~v)∗ × U × ~h = exp(−(~x)∗ ⊗ W ⊗ ~y) where the dotted notation refers to the Rmin,+ semifield. 3.3
The FCA in Informational Harmoniums From Theorem 1 in Section 2.3 we have: Theorem 2. Informational harmoniums over the Rmax,+ semifields are cryptomorphic to Rmax,+-formal contexts. Proof. It is clear that harmoniums are in general bipartite graphs, as shown in Fig. 1. This is one of the isomorphisms of standard formal contexts. With the provisions we made after (1), we can gather the bias information into one extra visible and one extra hidden node vo and ho extending the sets of nodes to L0 and K0. Therefore we extend W as suggested by including the biases into the incidence W 0 so that (L0, K0, W 0) is a weighted bipartite graph, that is, a formal context with entries in the carrier set of Rmax,+ or Rmin,+, which is the lookedfor cryptomorphism. tu If the informational harmonium uses the particular form in (31), h~x | W | ~yioo = (~x)∗ ⊗ W ⊗ ~y) this allows us to borrow the results from part 3 of Theorem 1 and we know that there is a left adjunction (·∃W , ·∀W ) : Xe Ye between the spaces through the left adjunct pair of maps: ~x∃W = W ∗ ⊗ ~x ~y∀W = W ⊗ ~y which define a bijection between the systems of visible nodes BL0 (L0, K0, W 0) and neighbourhoods of hidden nodes NK0 (L0, K0, W 0)
BL0 (L0, K0, W 0) = (Ye )∀W
NK0 (L0, K0, W 0) = (Xe )∃W
Regarding learning the harmonium, this type seems to resemble a heteroassociative memory, for if (a, d) is a neighbourhood concept of the pair of lattices then by the definition of the polars we have W ≥ ~a ⊗ d~∗, and in general the harmonium can be built (not efficiently) as the join:
W ≥
_ (~a,d~)∈N(L0,K0,W 0) ~a ⊗ d~∗ (34) 4
Conclusions and Further Research We have introduced the information harmoniums as a way to “patch” the magnitude problems of harmoniums: the energy function is not written in an algebra of logarithmic quantities, whence the “dimensions” in natural units (probabilities) of the harmonium generative model are incorrect.
By means of defining generalized information and mass functions we have been able to related the informational harmoniums to non-normalized harmoniums defined in positive semifields obtained from the basic R≥0 semifield.
If we further concentrate on the informational semifields of order r = ±∞ we recover the Rmax,×, Rmin,×, Rmax,+ and Rmin,+. When the harmoniums are described with these semirings they relate to one of the four types of Galois connection definable over the matrix of weights (W or U ): they are the scalar products that defined the Galois connections, so that the posterior “mass measures” and “information measures” are simply the polars.
This opens up a number of avenues of research into the representation of the spaces associated to r = ±∞-harmoniums, and suggest that K-FCA has points to make relating to inference and learning of these, including the consideration of the other three types of connections between spaces. Also, more efficient ways to build harmoniums, as well as approximate building in the absence of the supervision provided by the intents, d~ will be explored in future work.