.. _`inference algorithms`:

Inference algorithms
====================

An *inference algorithm* is a procedure that takes as its inputs an arbitrary :ref:`probabilistic model <models>`, a *query variable*
:math:`X` (or a set of those) and an observation :math:`E{=}e`. Its output is the probability distribution :math:`\cprob{X}{E{=}e}`.

In |symfer|, this works a little differently. Instead of directly outputting probabilities, the inference algorithm outputs a
:ref:`factor algebra expression <factor algebra>`. No actual multiplications or additions are made yet; this is done at the moment
that we choose to *evaluate* this expression.

Each expression in factor algebra can be read as a script. For example, the expression :math:`\sumproj_{A} ( (f \prodjoin g) \prodjoin h))`
(or in Python: ``SumProd(['A'],[SumProd([],[SumProd([],[f,g]),h])])``) tells the evaluator to perform these steps:

1. multiply :math:`f` with :math:`g`
2. multiply the result of (1) with :math:`h`
3. sum out variable :math:`A` from the result of (2)

These steps are performed when we execute

    >>> s.evaluate(expr)
    
However, first it is the task of an inference algorithm to cleverly construct ``expr``.
The most basic inference algorithm is defined as follows::

    def naive(facs,query,obs):
        return I().product(*facs).index(obs).sumto(query)

It simply multiplies all factors to construct the joint, then selects only those values consistent with the assignment ``obs``, and
from these sums out all variables except those in ``query``.
Note that this calculates the distribution :math:`\prob{X,E{=}e}`. It is easy to derive the sought for conditional probabilities
:math:`\cprob{X}{E{=}e}` from this by normalizing; however, |symfer| does not do this for you (as of yet). This is the case for all
the inference algorithms.

More about the other algorithms in the future, for now take a look at :mod:`symfer.inference`.