PE1-6.2 Knowledge Representation

What this is and why it exists

Writing down everything a system knows, when everything is uncertain, is harder than it sounds. A full joint distribution over even a modest number of variables is astronomically large.

One idea makes it possible. Declare what does not depend on what, and the description collapses to something you can both write and compute with.

The vocabulary

• Joint distribution — the probability of every combination of every variable.
• Conditional independence — two variables being unrelated once a third is known.
• Bayesian network — a graph whose structure declares those independences.
• Parent — a variable another one depends on directly.
• Exact inference — computing an answer precisely.
• Approximate inference — estimating it, usually by sampling.
• Hidden Markov model — a model of a hidden state changing over time, observed indirectly.
• Semantic network — knowledge as a graph of concepts joined by relations.
• Frame — a concept represented as a bundle of named slots with default values.

The mental model

Start with why the graph exists. Describing the joint behaviour of many uncertain variables directly means a number for every combination, and that count multiplies with each variable added. It is unwritable and unlearnable.

Almost all of those numbers are unnecessary, because most variables do not affect each other directly. A network states that structure. Each variable has arrows from those it depends on directly, and given those it is independent of everything else not downstream of it. You then supply a probability for each variable given its direct parents, which is a small table rather than an enormous one.

So the graph is the point. It is not decoration on the numbers. It states which independences you are assuming, and that is what makes the whole thing tractable.

Construction is where the judgement lies, and variable ordering is the detail worth seeing. The network is built by taking variables one at a time and connecting each to those already present that it depends on. Order them so that causes come before effects and the graph is sparse and readable. Order them the other way and the network is correct, dense and useless. Almost every variable connects to almost every other, with tables too large to fill in.

That is a genuinely instructive failure. Both networks describe the same distribution. Only one of them is usable, and the difference was made by an ordering choice before any probability was entered.

Inference is answering questions: given what has been observed, how likely is something else? Exact methods do this precisely, and in the general case the work grows too fast to be practical. That is why approximate methods exist. They sample from the network many times and count, trading a precise answer for one that is close and obtainable.

The temporal case is the reason this topic sits in an electronics course. A hidden Markov model describes something whose true state changes over time and which you cannot see directly, only through observations that depend on it. The state at each moment depends on the previous state and nothing earlier, and each observation depends only on the current state.

That is exactly the shape of speech. What was said changes over time, you cannot observe it, and what you have is a sequence of acoustic measurements that depend on it. The model reappears in the final topic doing precisely that job, so it is worth solid attention here.

The last three items are older symbolic representation. The honest framing is that they preceded the probabilistic turn rather than being current practice.

A semantic network represents knowledge as concepts joined by labelled relations. It is intuitive and it draws well. Its weakness is that the meaning of a link is never quite pinned down. A labelled relation means whatever its author intended, and two authors mean different things. Extended versions add the precision that addresses exactly that, and comparing before and after is the content.

A frame represents a concept as a bundle of named slots with default values, which can be overridden and inherited from more general frames. That description will sound familiar. It is the ancestor of the object idea in programming, and making that connection beats memorising the scheme.

What you should now be able to explain or do

Say why a full joint description is unusable and what the graph replaces it with. Explain what the structure of a network actually asserts. Build a network and say why variable ordering decides whether it is usable. Say why approximate inference exists. Describe a hidden Markov model and say why its shape fits speech.

Check yourself