Factors: operations, theory and other names?

Proph. Daphne Koller talks a lot about factors in her PGM course: youtube video

She defines product & marginalization operation for them. However this factor entity is either not widespread or called differently. At least wikipedia page for Factor doesn't seem to have a page for these factors.

So I'm interested in:

• How else is this construction called? What are best analogies?
• What are other operations defined for them? Is there a theory that studies factors?
• Are there any smart algorithms for doing these operations?
-

1 Answer

The use of the term 'factor' in the context of PGM is computer science lingo and is practically never used in mathematics circles.

The factors you are talking about are just functions. In more detail, a factor $F$ of scope $X_1,\cdots, X_n$ (where the $X_i$ are sets) is a function $F:X_1\times \cdots X_n \to \mathbb R$. So, a different name for factors is: a real valued function on the cartesian product of sets.

Since this is such a general concept you can define a million different and crazy operations on factors. In the context of PGM there are some natural operations to consider since most factors encountered are either probability distributions, or unnormalized such, or somehow related to such.

In particular, the common operations performed directly on factors are, as you mention, product factors and marginalizations (and also nomrlizations etc.). The most straightforward algorithms for these operations are the most efficient ones and are very fast (often $O(n^2)$). If the factors are known to have certain properties (e.g., sparsity) then faster algorithms can be developed.

-
Ittay, thanks for the answer. I have a follow up questions though: while you are right that these a functions, you could claim that matrix is simply a linear function. But they do have a number of interesting properties & algorithms and operations and a special name. Do you think these "factors" have interesting properties too? – mikea Jan 16 '13 at 1:59
You're welcome. A matrix is a representation of a linear transformation. A linear transformation is a very special kind of function, which is why it has nice properties. When all you have is just a function on a cartesian product you can't expect to do anything clever with it. Note that in PGM factors are used to decorate DAGs, and that is where you need clever algorithms: because graphs are insanely complicated. – Ittay Weiss Jan 16 '13 at 2:02
Ittay, what about tensors? Are they related here? Doesn't cartesian product look alike tensor dot product? – mikea Jan 30 '13 at 19:20
In the context of category theory the cartesian product is a special kind of tensor product. But in factors the cartesian product. But factors use particular properties of the cartesian product so I don't know if it makes much sense to speak of factors related to other tensor product.s – Ittay Weiss Jan 30 '13 at 20:19