Computational Intelligence (AD-702 (C)) Unit 4 Notes

How unit 4 is examined

This unit covers rough sets (indiscernibility, approximations, membership, reducts) and then HMMs and decision trees; none of the six topics was asked in the supplied papers, so learn the definitions, formulas and one worked example each.

Introduction, Fundamental Concepts

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Not asked since 2022</span>

Definition. <mark>Rough set theory, proposed by Pawlak, describes a vague set by a pair of crisp sets, its lower and upper approximation, built from classes of objects that the available attributes cannot tell apart.</mark>

Key points.

Data is stored in an information table in which rows are objects and columns are attributes, and a decision table adds one decision attribute.
Two objects $x,y$ are indiscernible under an attribute set $B$ if $a(x)=a(y)$ for every $a\in B$, which is written $x\,IND(B)\,y$.
Indiscernibility is an equivalence relation, so it partitions the universe $U$ into equivalence classes $[x]_B$, called elementary granules of knowledge.
Rough sets need no prior membership function or probability, only the data itself, which is their main advantage over fuzzy sets.
The theory is used for feature selection, rule generation, data mining and handling of incomplete or inconsistent data.

Example. Let $U=\{1,\dots,8\}$ and let the attributes split it into classes $\{1,2\}$, $\{3,4,5\}$, $\{6\}$, $\{7,8\}$. Objects 3, 4 and 5 look identical, so any knowledge about them must treat them together.

Set approximation

Definition. <mark>For a target set $X\subseteq U$, the lower approximation is the union of all classes wholly contained in $X$, and the upper approximation is the union of all classes that overlap $X$.</mark>

Formula.

$$\underline{B}X=\{x:[x]_B\subseteq X\},\qquad \overline{B}X=\{x:[x]_B\cap X\ne\emptyset\}$$

Boundary $BN_B(X)=\overline{B}X-\underline{B}X$, and accuracy $\alpha_B(X)=\dfrac{|\underline{B}X|}{|\overline{B}X|}$.

Key points.

The lower approximation holds the objects that certainly belong to $X$ on the available knowledge.
The upper approximation holds the objects that possibly belong to $X$.
The boundary region holds the objects that cannot be classified as inside or outside $X$ with certainty.
$X$ is crisp (exact) if the boundary is empty, and rough if it is not.
Accuracy lies between 0 and 1; it equals 1 for a crisp set, and the outside region is $U-\overline{B}X$.
Always $\underline{B}X\subseteq X\subseteq\overline{B}X$.

Example. With the classes above and $X=\{1,2,3,6\}$: the classes inside $X$ are $\{1,2\}$ and $\{6\}$, so the lower approximation is $\{1,2,6\}$. The classes touching $X$ are $\{1,2\}$, $\{3,4,5\}$ and $\{6\}$, so the upper approximation is $\{1,2,3,4,5,6\}$. The boundary is $\{3,4,5\}$ and the outside is $\{7,8\}$.

Accuracy $=3/6=\mathbf{0.5}$, so $X$ is rough.

Answer frame. Open with the definition of both approximations; state the formulas; give the boundary and accuracy; work the small example; close by saying the set is rough exactly when the boundary is non-empty.

Rough membership

Definition. <mark>Rough membership gives the degree to which an object $x$ belongs to $X$ as the fraction of its indiscernibility class that lies in $X$.</mark>

Formula.

$$\mu_X^B(x)=\frac{|[x]_B\cap X|}{|[x]_B|}$$

Key points.

The value always lies in $[0,1]$, so it behaves like a fuzzy membership value.
Unlike a fuzzy membership function, it is computed from the data and not assumed by an expert.
$\mu=1$ means $x$ is in the lower approximation, and $\mu=0$ means $x$ is outside the upper approximation.
$0<\mu<1$ means $x$ is in the boundary region, and this is how the uncertainty is measured.
The approximations can be rewritten: lower $=\{x:\mu=1\}$ and upper $=\{x:\mu>0\}$.

Example. With the same classes and $X=\{1,2,3,6\}$: for object 3, $[3]=\{3,4,5\}$ and only object 3 lies in $X$, so $\mu=1/3$. For object 1, $\mu=2/2=1$. For object 7, $\mu=0/2=0$.

Answer frame. Open with the definition; write the formula; explain the three cases $\mu=1$, $0<\mu<1$ and $\mu=0$; give the example; close by contrasting with fuzzy membership.

Attributes, Optimization

Definition. <mark>A reduct is a minimal subset of attributes that classifies the objects exactly as the full attribute set does, and the core is the intersection of all reducts.</mark>

Formula. Dependency of decision $D$ on attribute set $B$:

$$\gamma(B,D)=\frac{|POS_B(D)|}{|U|}$$

where $POS_B(D)$ is the union of the lower approximations of the decision classes.

Key points.

An attribute is redundant if removing it leaves the classification, and so $\gamma$, unchanged.
A reduct keeps only the non-redundant attributes, so the table and the rules generated from it become smaller.
A table can have several reducts, and finding the shortest one is the optimization problem (it is NP-hard, so heuristics are used).
The core attributes are indispensable and appear in every reduct.
$\gamma=1$ means the decision depends fully on $B$, and $\gamma<1$ means only partial dependency.

Example. Take 6 objects with condition attributes $a,b,c$ and decision $d$:

Object	a	b	c	d
1	0	0	1	0
2	0	1	1	0
3	1	0	0	1
4	1	1	0	1
5	0	0	0	1
6	1	1	1	0

The value $c=1$ always gives $d=0$ and $c=0$ always gives $d=1$, while $a$ alone and $b$ alone do not decide $d$. So $\{c\}$ is a reduct, it is also the core, and $\gamma(\{c\},d)=\mathbf{1}$.

Answer frame. Open with the definitions of reduct and core; write the dependency formula; list the points; show the table example; close by saying reducts cut redundant attributes without losing accuracy.

Hidden Markov Models

Definition. <mark>A Hidden Markov Model is a Markov chain whose states are hidden and can be inferred only from the observations that each state emits with some probability.</mark>

Key points.

It is specified by $\lambda=(A,B,\pi)$, where $A$ holds the state transition probabilities, $B$ the emission probabilities and $\pi$ the initial state distribution.
The Markov assumption says the next state depends only on the current state, and each observation depends only on the current state.
Evaluation asks for $P(O\mid\lambda)$ and is solved by the forward algorithm.
Decoding asks for the most likely hidden state sequence and is solved by the Viterbi algorithm.
Learning estimates $\lambda$ from observations using the Baum-Welch (EM) algorithm.
Typical uses are speech recognition, handwriting recognition and gene sequence analysis.

Diagram.

<figure class="ds-fig" style="margin:1.4rem 0;overflow-x:auto"><svg xmlns="http://www.w3.org/2000/svg" id="dsfig-u4-01" viewBox="0 0 338 252" width="338" height="252" role="img" aria-label="Two-state HMM. R = Rainy, S = Sunny (hidden); wk = walk, sh = shop (observed). Self-transitions R to R = 0.7 and S to S = 0.6; also P(walk given R) = 0.1 and P(shop given S) = 0.2."><style>#dsfig-u4-01 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u4-01 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u4-01 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u4-01 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u4-01 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u4-01 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u4-01 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u4-01 .t{fill:#16181D;font-weight:500}#dsfig-u4-01 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u4-01 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u4-01 .dot{fill:#16181D}#dsfig-u4-01 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u4-01 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u4-01 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u4-01 .ah{fill:#454C5A}#dsfig-u4-01 .ah.hi{fill:#2340B8}#dsfig-u4-01 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u4-01 .wl .t{font-size:12px;font-weight:700}#dsfig-u4-01 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u4-01 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u4-01 .e{stroke:#B1B7C3}html.dark #dsfig-u4-01 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u4-01 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u4-01 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u4-01 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u4-01 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u4-01 .t{fill:#E6E8ED}html.dark #dsfig-u4-01 .t.inv{fill:#0F1115}html.dark #dsfig-u4-01 .kd{stroke:#E6E8ED}html.dark #dsfig-u4-01 .dot{fill:#E6E8ED}html.dark #dsfig-u4-01 .ann{fill:#8FA3FF}html.dark #dsfig-u4-01 .lbl{fill:#858D9C}html.dark #dsfig-u4-01 .ptr{fill:#8FA3FF}html.dark #dsfig-u4-01 .ah{fill:#B1B7C3}html.dark #dsfig-u4-01 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u4-01 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u4-01 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u4-01 .wl.hi .t{fill:#0F1115}</style><defs><marker id="ah5" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah" d="M0,1 L9,5 L0,9 z"/></marker><marker id="ahh5" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah hi" d="M0,1 L9,5 L0,9 z"/></marker></defs><path class="e" d="M58.4,44.6 Q169,72 277.6,45.1" marker-end="url(#ah5)"/><path class="e" d="M279.6,35.4 Q169,8 60.4,34.9" marker-end="url(#ah5)"/><path class="e" d="M55.8,50.5 L280.5,200.4" marker-end="url(#ah5)"/><path class="e" d="M282.2,50.5 L57.5,200.4" marker-end="url(#ah5)"/><g class="wl"><rect x="151.7" y="49.4" width="33.6" height="18" rx="9"/><text class="t" x="168.5" y="58.4" dy=".35em" text-anchor="middle">0.3</text></g><g class="wl"><rect x="152.7" y="12.6" width="33.6" height="18" rx="9"/><text class="t" x="169.5" y="21.6" dy=".35em" text-anchor="middle">0.4</text></g><g class="wl"><rect x="152.2" y="117" width="33.6" height="18" rx="9"/><text class="t" x="169" y="126" dy=".35em" text-anchor="middle">0.9</text></g><g class="wl"><rect x="152.2" y="117" width="33.6" height="18" rx="9"/><text class="t" x="169" y="126" dy=".35em" text-anchor="middle">0.8</text></g><circle class="n" cx="40" cy="40" r="18"/><text class="t" x="40" y="40" dy=".35em" text-anchor="middle">R</text><circle class="n" cx="298" cy="40" r="18"/><text class="t" x="298" y="40" dy=".35em" text-anchor="middle">S</text><circle class="n" cx="40" cy="212" r="18"/><text class="t" x="40" y="212" dy=".35em" text-anchor="middle">wk</text><circle class="n" cx="298" cy="212" r="18"/><text class="t" x="298" y="212" dy=".35em" text-anchor="middle">sh</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">Two-state HMM. R = Rainy, S = Sunny (hidden); wk = walk, sh = shop (observed). Self-transitions R to R = 0.7 and S to S = 0.6; also P(walk given R) = 0.1 and P(shop given S) = 0.2.</figcaption></figure>

Example. Take $\pi=(R:0.6,\,S:0.4)$, the transitions and emissions above with $P(\text{walk}\mid R)=0.1$, $P(\text{shop}\mid R)=0.9$, $P(\text{walk}\mid S)=0.8$, $P(\text{shop}\mid S)=0.2$. For the sequence walk, shop the forward values after the first symbol are $\alpha(R)=0.06$ and $\alpha(S)=0.32$. After the second symbol $\alpha(R)=0.153$ and $\alpha(S)=0.042$, so $P(O\mid\lambda)=\mathbf{0.195}$.

Answer frame. Open with the definition; draw the state diagram; list $A$, $B$, $\pi$; name the three problems with their algorithms; close with applications.

Decision tree model

Definition. <mark>A decision tree is a classifier in which each internal node tests an attribute, each branch is an outcome of the test and each leaf holds a class label.</mark>

Formula.

$$H(S)=-\sum_i p_i\log_2 p_i,\qquad Gain(S,A)=H(S)-\sum_v\frac{|S_v|}{|S|}H(S_v)$$

Key points.

ID3 builds the tree top-down and at each node splits on the attribute with the highest information gain.
Entropy measures the impurity of a set, and it is 0 when all examples share one class.
C4.5 improves ID3 by using gain ratio (gain divided by split information), handling continuous attributes and missing values, and pruning the tree.
Growth stops when a node is pure, no attributes remain or no examples remain.
Every root-to-leaf path is an IF-THEN rule, so the model is easy to read.
Without pruning the tree can overfit the training data.

Diagram.

<figure class="ds-fig" style="margin:1.4rem 0;overflow-x:auto"><svg xmlns="http://www.w3.org/2000/svg" id="dsfig-u4-02" viewBox="0 0 450 130" width="450" height="130" role="img" aria-label="First split of the play-tennis data (14 examples: 9 Yes, 5 No). Sunny and Rain are split further; Overcast is pure."><style>#dsfig-u4-02 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u4-02 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u4-02 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u4-02 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u4-02 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u4-02 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u4-02 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u4-02 .t{fill:#16181D;font-weight:500}#dsfig-u4-02 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u4-02 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u4-02 .dot{fill:#16181D}#dsfig-u4-02 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u4-02 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u4-02 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u4-02 .ah{fill:#454C5A}#dsfig-u4-02 .ah.hi{fill:#2340B8}#dsfig-u4-02 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u4-02 .wl .t{font-size:12px;font-weight:700}#dsfig-u4-02 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u4-02 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u4-02 .e{stroke:#B1B7C3}html.dark #dsfig-u4-02 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u4-02 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u4-02 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u4-02 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u4-02 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u4-02 .t{fill:#E6E8ED}html.dark #dsfig-u4-02 .t.inv{fill:#0F1115}html.dark #dsfig-u4-02 .kd{stroke:#E6E8ED}html.dark #dsfig-u4-02 .dot{fill:#E6E8ED}html.dark #dsfig-u4-02 .ann{fill:#8FA3FF}html.dark #dsfig-u4-02 .lbl{fill:#858D9C}html.dark #dsfig-u4-02 .ptr{fill:#8FA3FF}html.dark #dsfig-u4-02 .ah{fill:#B1B7C3}html.dark #dsfig-u4-02 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u4-02 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u4-02 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u4-02 .wl.hi .t{fill:#0F1115}</style><defs><marker id="ah6" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah" d="M0,1 L9,5 L0,9 z"/></marker><marker id="ahh6" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah hi" d="M0,1 L9,5 L0,9 z"/></marker></defs><line class="e" x1="215" y1="37" x2="75" y2="101"/><line class="e" x1="215" y1="37" x2="217" y2="101"/><line class="e" x1="215" y1="37" x2="355" y2="101"/><rect class="n" x="177.5" y="22" width="75" height="30" rx="8"/><text class="t" x="215" y="37" dy=".35em" text-anchor="middle">Outlook</text><rect class="n" x="14" y="86" width="122" height="30" rx="8"/><text class="t" x="75" y="101" dy=".35em" text-anchor="middle">Sunny (2Y,3N)</text><rect class="n" x="152" y="86" width="130" height="30" rx="8"/><text class="t" x="217" y="101" dy=".35em" text-anchor="middle">Overcast (Yes)</text><rect class="n" x="298" y="86" width="114" height="30" rx="8"/><text class="t" x="355" y="101" dy=".35em" text-anchor="middle">Rain (3Y,2N)</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">First split of the play-tennis data (14 examples: 9 Yes, 5 No). Sunny and Rain are split further; Overcast is pure.</figcaption></figure>

Example. For the play-tennis data, $H(S)=0.940$ for 9 Yes and 5 No. Splitting on Outlook gives subsets (2,3), (4,0), (3,2), so $Gain=0.940-\tfrac{5}{14}(0.971)-\tfrac{4}{14}(0)-\tfrac{5}{14}(0.971)=\mathbf{0.247}$.

Answer frame. Open with the definition; draw the tree; state entropy and gain; describe the ID3 steps; close by naming C4.5 and pruning.

Steps (ID3).

Step 1: Compute the entropy of the whole training set S.
Step 2: For every unused attribute A, compute Gain(S, A).
Step 3: Pick the attribute with the highest gain and make it the node.
Step 4: Create one branch per value and send the matching examples down it.
Step 5: If a branch is pure, make it a leaf; otherwise repeat from Step 1 on that subset.

Pitfall: Information gain favours attributes with many values (such as an ID column); this is why C4.5 divides by split information.

Reading the rough-set toolkit together. Indiscernibility gives the granules, approximations bound a concept by them, rough membership grades each object, and reducts trim the attributes that do not change any of these results. HMMs and decision trees are the two learning models that complete the unit: one models hidden sequences, the other builds classification rules from labelled data.

Last-minute revision

Indiscernibility is an equivalence relation: same values on all attributes in $B$.
Lower approximation is certain, upper approximation is possible.
Boundary is upper minus lower, and a non-empty boundary makes the set rough.
Accuracy $\alpha=|\text{lower}|/|\text{upper}|$; the worked example gives $3/6=0.5$.
Rough membership $=|[x]\cap X|/|[x]|$; it is 1 in lower, 0 outside upper.
A reduct is a minimal attribute set preserving classification; the core is the intersection of all reducts.
Dependency $\gamma=|POS|/|U|$.
HMM is $\lambda=(A,B,\pi)$ with forward (evaluation), Viterbi (decoding) and Baum-Welch (learning).
Entropy is $-\sum p\log_2 p$; gain is the entropy drop from a split.
ID3 uses information gain; C4.5 uses gain ratio and pruning.
Play-tennis: $H=0.940$, Gain(Outlook) $=0.247$.

Memory hooks

Lower is Locked in (certain), Upper is Unsure (possible).
The core is in every reduct, like a core in every apple.
HMM problems in order: Evaluate, Decode, Learn (forward, Viterbi, Baum-Welch).
ID3 picks Information gain; C4.5 picks the Ratio and Prunes.

Coverage checklist

Introduction, Fundamental Concepts: no past questions.
Set approximation: no past questions.
Rough membership: no past questions.
Attributes, Optimization: no past questions.
Hidden Markov Models: no past questions.
Decision tree model: no past questions.

Account

Computational Intelligence (AD-702 (C)) - Unit 4 Short Notes

How unit 4 is examined

Introduction, Fundamental Concepts

Set approximation

Rough membership

Attributes, Optimization

Hidden Markov Models

Decision tree model

Last-minute revision

Memory hooks

Coverage checklist