# UAS — Kecerdasan Artifisial (Kom-B) (2023) — Model Answers

> Final Exam · Odd Semester 2023/2024 · Universitas Gadjah Mada
> Answers to `UAS - AI - 2023 KOMB.md`. The exam is in English, so these answers are in English.

| Field | Value |
|---|---|
| **Course** | Kecerdasan Artifisial (Kom-B) |
| **Exam type** | Ujian Akhir Semester (UAS) |
| **Semester** | Gasal 2023/2024 |
| **Date** | Jumat, 8-Desember-2023 |
| **Time** | 07.30–09.30 (120 menit) |
| **Lecturer** | Retantyo Wardoyo |
| **Exam mode** | May open one page paper. DO NOT WORK TOGETHER |

**Institution:** Program Studi S1 Ilmu Komputer, Fakultas Matematika dan Ilmu Pengetahuan Alam, Universitas Gadjah Mada

> **Phrase correction note (Q2):** the transcription reads `abbdcdacbbc`, but that string is **derivable by no parse tree of this grammar** (machine-checked). The correct phrase, per the source scan, is **`abdbcdacbbc`** — which parses uniquely. Everything below uses the corrected phrase.

---

## Question 1 — Expert System Architecture (PLO 4; CO-4; 10%)

An expert system is a computer-based system that handles problems by reasoning like a human expert. Its architecture separates *what is known* (knowledge base) from *how to reason* (inference engine) and *how to communicate* (interfaces) — and this separation is precisely what allows several *different kinds of users* to interact with the system, each through a different door.

### a. Different users in expert systems, and how they interact

| # | User | Who they are | How they interact (which component) |
|---|---|---|---|
| 1 | **Client / end user (consultand)** | The person seeking advice — usually a *non-expert* (junior doctor, loan officer, technician, farmer) | Through the **user interface** only: runs a *consultation session* — enters case data (symptoms, applicant data), answers the system's questions during backward chaining, receives conclusions/recommendations, and asks for explanations (**WHY** did you ask that? **HOW** did you reach that?) |
| 2 | **Domain expert** | The human specialist whose knowledge is captured (e.g., the senior physician in MYCIN) | Through the **knowledge-acquisition subsystem** with the knowledge engineer: interviews, reviews the encoded rules, corrects the system when test consultations go wrong, supplies certainty factors and refinements |
| 3 | **Knowledge engineer** | The specialist in translating expertise into machine-usable form | Works with both the expert and the system: interviews the expert, encodes facts/rules/frames via the **knowledge-base editor**, runs traces and debuggers, validates with test cases, maintains consistency |
| 4 | **System programmer / tool builder** | The programmer who builds or customizes the **expert-system shell** (UI toolkit + inference engine + acquisition tools) | Through the shell's programming interface — implements the engine, explanation facility, integration; typically not involved in daily consultation |
| 5 | **Administrator / IT staff** | Keeps the deployed system operational | User management, backups, integration with databases/hospital or bank information systems, deployment of KB updates |

(One more is often listed: **students/trainees** who use the system's explanation facility as a tutorial — an expert system doubles as a teaching aid.)

**The architectural point:** because the knowledge base is deliberately decoupled from the inference engine, each user class touches a different component — the consultand only ever sees the UI; the expert and knowledge engineer only the KB and acquisition tools; the programmer only the shell. Knowledge can be updated without reprogramming, and the engine is domain-independent (the same shell hosts different KBs).

### b. Example of the use of an agenda in an expert system

The **agenda** is the inference engine's *priority queue of pending activations* — the set of rules whose premises are currently satisfied (produced by the MATCH step). The **scheduler** orders the agenda (conflict resolution) and the engine fires the top entry each **recognize–act cycle** (match → resolve → fire). Typical ordering criteria: **salience/priority** (explicit rule importance), **recency** (facts asserted most recently first), and **specificity** (more premises = more specific = first). MYCIN ordered its agenda by recency and specificity; OPS5/CLIPS expose salience explicitly.

**Worked example — loan-screening expert system (CLIPS-style salience):**

```
R1 (salience 100): IF late-payments >= 3                THEN risk = high
R2 (salience  90): IF risk = high AND collateral >= loan THEN risk = reduced
R3 (salience  50): IF risk = high                        THEN decision = reject
R4 (salience  50): IF risk = reduced                     THEN decision = manual-review
```

Facts entered by the loan officer: `late-payments = 5`, `collateral = 200M`, `loan = 150M`.

| Cycle | MATCH: rules satisfied | Agenda (ordered) | Fired | New fact |
|---|---|---|---|---|
| 1 | R1 | [R1(100)] | R1 | `risk = high` |
| 2 | R2, R3 | [R2(90), R3(50)] — salience puts the collateral rule first | R2 | `risk = reduced` |
| 3 | R3, R4 | [R3(50), R4(50)] — tie! broken by **recency**: R4's triggering fact (`risk = reduced`) is newer | R4 | `decision = manual-review` → goal reached |

**What the agenda buys us:** without it, the engine might fire R3 the moment it matches (cycle 2) and wrongly *reject* a fully-collateralized applicant. The agenda lets control knowledge (priority, recency) decide *when* each rule fires, while the rules themselves stay pure domain knowledge — control strategy is separated from knowledge content, exactly the agenda's role in the architecture.

### c. Certainty Factors vs Fuzzy Logic — differences and examples

Both handle **inexact reasoning**, but they attack two *different* kinds of imperfection:

| Aspect | Certainty Factors (CF) | Fuzzy Logic |
|---|---|---|
| **What it models** | **Uncertainty** — incomplete/ambiguous *evidence* about whether a proposition is true | **Vagueness** — concepts that are true only *to a degree* ("high fever", "tall", "hot") |
| **Origin** | Shortliffe & Buchanan (1975), MYCIN | Zadeh (1965), fuzzy sets |
| **Scale & meaning** | CF ∈ [−1, +1]: **belief minus disbelief** in a conclusion given evidence | μ ∈ [0, 1]: **degree of membership** of a value in a fuzzy set (a statement can be 70% *true*) |
| **Where numbers attach** | To **rules and inferred facts** (conclusions) | To **input values** via fuzzification of *linguistic variables* (temperature 38.5°C → `high = 0.7`, `moderate = 0.3`) |
| **Mathematics** | Heuristic combination: parallel `CF = CF₁ + CF₂ − CF₁·CF₂` (both > 0); chaining `CF_concl = CF_rule × CF_premise` | Fuzzy set operations (min = AND, max = OR), Mamdani/Sugeno inference, **defuzzification** (e.g., centroid) to a crisp output |
| **Typical applications** | Medical/diagnostic expert systems with unreliable evidence (MYCIN: "organism is Pseudomonas, CF 0.6") | **Control systems**: air conditioners, washing machines, automatic transmissions, the Sendai subway (1987); linguistic decision support |
| **The question it answers** | "How *sure* are we that X is true, given the evidence?" | "To what *degree* is X true?" |

**CF example (MYCIN-style diagnosis):**
- R1: IF fever AND cough THEN influenza (CF 0.6)
- R2: IF winter-season AND epidemic-reported THEN influenza (CF 0.7)
- A patient satisfies both rule sets → the two conclusions combine:
  `CF = 0.6 + 0.7 − (0.6 × 0.7) = 0.88` — strong *belief* the patient has influenza, despite uncertain evidence.
- Chaining: if the premise of R1 is itself only 80% certain, the conclusion carries `0.8 × 0.6 = 0.48`.

**Fuzzy example (air-conditioner controller):**
- Linguistic variables: `temperature ∈ {cold, cool, warm, hot}`, `humidity ∈ {low, high}`.
- Reading 30 °C fuzzifies to `hot = 0.7`, `warm = 0.3`; humidity 80% → `high = 0.8`.
- Rule: IF temperature IS hot AND humidity IS high THEN fan-speed IS fast.
- Firing strength = min(0.7, 0.8) = **0.7**; the output fuzzy set "fast" is clipped at 0.7 and defuzzified (centroid) to, say, a 72% duty cycle — a *graduated* control action, not an on/off decision.

**The classic contrast ("is this apple ripe?"):** CF asks *"how confident are we that it is ripe"* — the apple either is or isn't ripe, and our *evidence* (smell, colour readings) is incomplete; fuzzy asks *"how ripe is it"* — ripeness is inherently a matter of degree, and the statement "the apple is ripe" can be 70% true regardless of how much evidence we have.

---

## Question 2 — Parsing "abdbcdacbbc" + Parse Tree (PLO 3; CO-5; 10%)

### Grammar recap

Nonterminals: {S, A, B, C, G, I} — start symbol **S**; terminals: {a, b, c, d}.

| | | | |
|---|---|---|---|
| S → ABC | S → BA | A → GI | A → CG |
| B → AC | B → BCG | B → CI | C → aA |
| C → c | G → BB | G → b | I → d |

Useful facts about this grammar: only **C → aA** can produce an `a` (always as the first of a 2-symbol unit), `b` comes only from **G → b**, `c` only from **C → c**, `d` only from **I → d**. Phrase `abdbcdacbbc` = a×2, b×4, c×3, d×2 (11 symbols). Note **B → BCG is right-recursive** (not left-recursive), so a top-down parser terminates; with right-hand sides of up to three symbols, the systematic procedure is a **bottom-up chart (CYK-style) parse**, and the equivalent top-down leftmost derivation is shown below.

### Step 1 — Bottom-up chart: which substrings are which nonterminals

Building all derivable spans (substring positions w1–w11):

| Span | Substring | Nonterminal(s) — via | Used in final parse |
|---|---|---|---|
| w2 | b | G (G→b) | ✓ |
| w3 | d | I (I→d) | ✓ |
| w4 | b | G (G→b) | ✓ |
| w5 | c | C (C→c) | ✓ |
| w6 | d | I (I→d) | ✓ |
| w8 | c | C (C→c) | ✓ |
| w9 | b | G (G→b) | ✓ |
| w10 | b | G (G→b) | ✓ |
| w11 | c | C (C→c) | ✓ |
| w2–3 | bd | A (A→GI) | ✓ |
| w5–6 | cd | B (B→CI) | ✓ |
| w8–9 | cb | A (A→CG) | ✓ |
| w1–3 | abd | C (C→aA) | ✓ |
| w7–9 | acb | C (C→aA) | ✓ |
| w1–4 | abdb | A (A→CG) | ✓ |
| w1–5 | abdbc | B (B→AC) | — (decoy span, see below) |
| w5–10 | cdacbb | B (B→BCG) | ✓ |
| **w1–11** | **abdbcdacbbc** | **S (S→ABC)** | ✓ |

### Step 2 — Top-level choice for S

- **Try S → BA**: needs a B over w1–5 (`abdbc` — it exists!) and an A over w6–11 (`dacbbc`) — impossible. **Key invariant:** the only rule that produces `d` is **I → d**, and **I** only ever appears as the *second* symbol of a right-hand side (A → **G I**, B → **C I**); therefore **no nonterminal can derive a string that starts with `d`**, and `dacbbc` can never be an A. **Dead end → backtrack.**
- **Try S → ABC**: C must be the final `c` (its other production C→aA would have to start with `a` at w10 = `b` ✗), so A and B partition w1–10. The only A-span starting at w1 is w1–4 (`abdb`) — forcing **A = w1–4, B = w5–10 (`cdacbb`), C = w11 (`c`)**. All three spans exist. ✓

Every subsequent nonterminal also has exactly one viable production (verified exhaustively), so the parse is **forced** — the phrase is **unambiguous (exactly one parse tree)**.

### Step 3 — Decompose the nonterminals

- **A(w1–4, `abdb`)**: try A→GI — I must be exactly `d`, so G would have to span w1–3 (`abd`); but G's productions are G→b (exactly `b`) and G→BB (two B's, each of minimum length 2, so ≥ 4 symbols) — neither fits a 3-symbol span ✗. → **A→CG**: C(w1–3 `abd`) + G(w4 `b`). ✓
  - **C(w1–3, `abd`)**: C→aA: `a` + A(w2–3 `bd`).
  - **A(w2–3, `bd`)**: A→CG would need a C starting at w2 = `b` ✗ (C produces only `c` or `a…`) → **A→GI**: G(w2 `b`, via G→b) + I(w3 `d`, via I→d). ✓
- **B(w5–10, `cdacbb`)**: try B→AC — A would have to start at w5, but the chart shows the only A-spans are w2–3, w8–9, w1–4 (none starts at w5; concretely, A→CG would need a G starting at w6 = `d`, impossible by the d-invariant, and A→GI would need G over w5–9, whose only conceivable split B(`cd`) + B(`acb`) fails because no B covers `acb`) ✗. Try B→CI — C must start at w5 = `c`, and C→c is a *single* symbol, which would force I to cover w6–10 (`dacbb`) alone, impossible since I→d is one symbol ✗. → **B→BCG**: B(w5–6) + C(w7–9) + G(w10). ✓
  - **B(w5–6, `cd`)**: B→AC and B→BCG would need an A (or B) over the single `c` at w5 — impossible, every A/B production has ≥ 2 symbols ✗ → **B→CI**: C(w5 `c`, via C→c) + I(w6 `d`, via I→d). ✓
  - **C(w7–9, `acb`)**: C→aA: `a` + A(w8–9 `cb`).
  - **A(w8–9, `cb`)**: A→GI would need G(w8) = `c` ✗ (G produces only `b` or BB ≥ 4 symbols) → **A→CG**: C(w8 `c`, via C→c) + G(w9 `b`, via G→b). ✓
- **C(w11)**: C→c. ✓

### Step 4 — Leftmost top-down derivation (the parsing process)

```
S
⇒ A B C                      (S → ABC;  S → BA fails)
⇒ C G B C                    (A → CG)
⇒ a A G B C                  (C → aA)
⇒ a G I G B C                (A → GI)
⇒ a b I G B C                (G → b)
⇒ a b d G B C                (I → d)
⇒ a b d b B C                (G → b)
⇒ a b d b B C G C            (B → BCG)
⇒ a b d b C I C G C          (B → CI)
⇒ a b d b c I C G C          (C → c)
⇒ a b d b c d C G C          (I → d)
⇒ a b d b c d a A G C        (C → aA)
⇒ a b d b c d a C G G C      (A → CG)
⇒ a b d b c d a c G G C      (C → c)
⇒ a b d b c d a c b G C      (G → b)
⇒ a b d b c d a c b b C      (G → b)
⇒ a b d b c d a c b b c      (C → c)   ✓ = abdbcdacbbc
```

### Step 5 — The resulting parse tree

```
                            S
            ┌───────────────┼───────────────┐
            A                  B            C
       ┌────┴───┐     ┌────────┼────────┐   │
       C        G     B        C        G   c
    ┌──┴──┐     │   ┌─┴─┐   ┌──┴──┐     │
    a     A     b   C   I   a     A     b
          │         │   │         │
        ┌─┴─┐       c   d       ┌─┴─┐
        G   I                   C   G
        │   │                   │   │
        b   d                   c   b
```

Bracketed form:

`(S (A (C a (A (G b) (I d))) (G b)) (B (B (C c) (I d)) (C a (A (C c) (G b))) (G b)) (C c))`

Rules used — 17 productions (17 internal nodes + 11 terminal leaves): S→ABC; A→CG ×2; A→GI; C→aA ×2; C→c ×3; G→b ×4; I→d ×2; B→BCG; B→CI.

### Notes

- **Uniqueness:** an exhaustive chart parse finds **exactly one** derivation — the phrase is unambiguous under this grammar. The span `w1–5 abdbc → B` is a decoy: it exists (via B→AC over A(w1–4)+C(w5)) but participates in no S-derivation, because S→BA then requires an A over `dacbbc`, which is impossible.
- **Transcription check:** the transcribed string `abbdcdacbbc` admits **no** parse (0 derivations, machine-checked) — hence the correction to `abdbcdacbbc`.
- **Family note:** this is the probability-free 2023 variant of the same grammar Wardoyo used in the 2019 IUP paper (phrase `cbccdcbdcdcbbd`) and the 2020 IUP/Reg-B paper (`ccbccdabddabd`). For reference only (the 2023 exam asks no probabilities): with the 2019/2020 PCFG weights, this tree would carry probability ≈ **1.86 × 10⁻⁶** (0.6 · 0.45 · 0.7 · 0.55 · 0.35 · 1 · 0.35 · 0.35 · 0.4 · 0.3 · 1 · 0.7 · 0.45 · 0.3 · 0.35 · 0.35 · 0.3).

---

## Question 3 — Machine Learning within AI (PLO-4; CO-6; 10%)

### a. How Machine Learning relates to Artificial Intelligence

**Artificial Intelligence** is the broad field: making machines perform tasks that require intelligence — perceiving, reasoning, representing knowledge, understanding language, planning, acting, and *learning*. Historically it pursued two routes:

1. **Symbolic / knowledge-driven AI** — knowledge is hand-coded by humans (search, logic, expert systems — exactly the architecture of Question 1). Powerful when knowledge can be articulated, but it hits the **knowledge-acquisition bottleneck**: experts can't always state what they know, and rules can't cover every case.
2. **Data-driven AI** — the machine *extracts* the knowledge itself from data. This route is **Machine Learning**.

**Machine Learning** is the subfield of AI concerned with programs that improve their performance at a task through experience rather than through explicit programming. Classic definitions:

- Samuel (1959): "the field of study that gives computers the ability to learn without being explicitly programmed."
- Mitchell (1997): "A computer program is said to **learn** from **experience E**, with respect to some class of **tasks T** and **performance measure P**, if its performance at tasks in T, as measured by P, improves with experience E."

The relationship is containment plus complementarity:

```
Artificial Intelligence (reasoning, knowledge, perception, language, learning, acting)
└── Machine Learning  (knowledge acquired from data instead of hand-coded)
    └── Deep Learning (learning with multi-layer neural networks)
```

- **ML supplies the learning capability early AI lacked**, dissolving the knowledge-acquisition bottleneck: where MYCIN needed months of interviews, a modern classifier learns diagnostic patterns from 10,000 labeled cases.
- **Scale and robustness:** ML systems improve with more data and tolerate noise/variation (accents, lighting, typos) that breaks hand-written rules — this is why vision, speech, translation and game-playing (AlphaGo) are ML-based.
- **Not all AI is ML, and hybrids abound:** search, planning, and knowledge representation remain non-ML; and state-of-the-art systems combine both — AlphaGo = learned evaluation + symbolic tree search; LLM agents = learned language model + symbolic tools/planners. ML is *the dominant approach within* AI today, not the whole of it.

### b. The use of classification in Machine Learning in conjunction with AI

**Classification** is the supervised-learning task of mapping an input *x* to a discrete class label *y* from a fixed set (spam / not-spam; benign / malignant; pedestrian / cyclist / traffic-sign), learned from labeled examples. It is the workhorse prediction task that puts the "learning" to work inside AI systems:

1. **Perception — turning raw data into symbols.** Classifiers convert sub-symbolic input into symbolic labels that reasoning components can consume: vision (object/face recognition, OCR), speech (speaker and command recognition), NLP (spam filtering, sentiment analysis, topic classification, named-entity recognition). In a hybrid architecture, the classifier is the *perception→cognition bridge*: an autonomous car's CNN classifies "pedestrian vs cyclist vs sign", and the symbolic planner reasons over those labels.
2. **Replacing/augmenting hand-coded expertise.** Where a classical expert system's rules came from interviews (Question 1), a classifier *learns* the decision function from archived cases — e.g., learning credit-risk or diagnosis rules from historical data — solving the maintenance and acquisition problems of rule-based knowledge, and providing data-driven weights where experts could only give certainty factors.
3. **Adaptive agents.** Game and robotic agents use classifiers for state assessment and behavior selection, improving with experience — the "learning agent" of Russell & Norvig's taxonomy.
4. **Pattern recognition (this course's CO-6 link).** Essentially all applied pattern recognition — biometrics, medical image reading, fault detection, fraud screening — is classification: measure features, map to a category. Performance is judged with classification metrics (accuracy, precision/recall, confusion matrix), chosen according to the real cost of each error type.

**Example:** an email agent embeds a Naive-Bayes spam classifier; a hospital decision-support system combines an expert-system rule base with a CNN classifier that labels scans "suspected pneumonia" — the label then feeds the rules that recommend treatment.

### c. Example algorithms — Supervised vs Unsupervised Learning, and their usage

| | **Supervised Learning** | **Unsupervised Learning** |
|---|---|---|
| **Training data** | Labeled pairs (x, y) — a "teacher" gives the right answers | Unlabeled data x only — no teacher |
| **Goal** | Predict the label/value for new inputs | Discover hidden structure in the data |
| **Typical tasks** | Classification (discrete y), regression (continuous y) | Clustering, dimensionality reduction, association rules, anomaly detection |
| **Example algorithm** | **Decision Tree (C4.5/CART)** | **k-Means clustering** |
| **How it works** | Learns a tree of if–then tests on features, splitting data to purity; each leaf predicts a class; the tree reads as explicit, auditable rules | Partitions n points into k clusters by iteratively assigning each point to the nearest centroid and recomputing centroids until stable |
| **Example usage** | **Credit scoring:** train on past loans labeled repaid/defaulted → the tree predicts approve/reject for a new applicant, and the branch conditions ("income < 5M AND late-payments ≥ 3 → reject") are interpretable for regulators. Also: medical triage, churn prediction | **Customer segmentation:** an e-commerce firm clusters customers by purchase frequency/basket value into behavior groups (bargain hunters, loyal big-spenders, …) with *no predefined labels*, then targets each group with different campaigns. Also: document grouping, color quantization |
| **Other examples** | k-NN, Naive Bayes, SVM, Logistic Regression, Random Forest, Neural networks/CNN | Hierarchical clustering, DBSCAN, PCA, Apriori (market-basket association), autoencoders |

**The contrast in one line:** with labels you can *predict* ("this applicant will default: yes/no" — supervised, decision tree); without labels you can only *discover* ("there are four distinct customer-behavior groups" — unsupervised, k-means) — prediction vs exploration.

---

## References

1. Jackson, P. (1999). *Introduction to Expert Systems* (3rd ed.) — user classes of expert systems (client, domain expert, knowledge engineer, tool builder) and the acquisition subsystem.
2. Giarratano, J. & Riley, G. (2005). *Expert Systems: Principles and Programming* (4th ed., CLIPS) — the agenda, recognize–act cycle, and conflict resolution (salience, recency, specificity).
3. Shortliffe, E. & Buchanan, B. (1975). "A Model of Inexact Reasoning in Medicine." *Mathematical Biosciences* 23 — certainty factors and MB/MD combination in MYCIN.
4. Zadeh, L. (1965). "Fuzzy Sets." *Information and Control* 8(3) — membership degrees; Mamdani (1975) — fuzzy inference for control (the Sendai subway application, Hitachi 1987).
5. Russell, S. & Norvig, P. (2021). *Artificial Intelligence: A Modern Approach* (4th ed.) — AI vs ML taxonomy, learning agents, hybrid architectures.
6. Mitchell, T. (1997). *Machine Learning* — the T/E/P definition; Samuel (1959) for the classical phrasing.
7. Jurafsky, D. & Martin, J. *Speech and Language Processing* (3rd ed. draft) — chart parsing background for Question 2.
8. Verification: Question 2's chart, unique parse, derivation, and both bracketed forms were machine-checked with a local Python chart parser (CYK-style span enumeration + exhaustive derivation count); the transcribed string `abbdcdacbbc` was confirmed to have zero derivations, and the probability figure ≈1.86×10⁻⁶ recomputed rule-by-rule under the 2019/2020 PCFG weights.

---

*Model answers prepared for revision. Q1a–b are recycled from Wardoyo's 2020 IUP/Reg-B paper (Q2 there) and the grammar in Q2 is the probability-free 2023 variant of his 2019/2020 PCFG — see the notes in the source transcript.*