SYLLABUS
Search: informed, uninformed, adversarial; logic, propositional, predicate; reasoning under uncertainty topics — conditional independence representation, exact inference through variable elimination, and approximate inference through sampling.
Q1 – Let ℎ1 and ℎ2 be two admissible heuristics used in 𝐴∗ search.
Which ONE of the following expressions is always an admissible heuristic?
(A) ℎ1 + ℎ2
(B) ℎ1 × ℎ2
(C) ℎ1/ℎ2, (ℎ2 ≠ 0)
(D) |ℎ1 − ℎ2|
(GATE DS&AI 2024)
Ans – (D)
Explanation – The heuristic function h(n) refers to a logical estimation of the cost of the shortest path to the goal from the given node, which is the true cost. The function h(n) is less than or equal to double h*(n) function.
There are two admissible heuristics, namely, h1 and h2. So, the next task is to always check which of the combinations is admissible.
Option (A) – h1 + h2
The heuristic is not always admissible. If the sum of the two heuristics is less than or equal to the true cost, then it will always be admissible, the example of that is both are equal to the exact cost. So may overestimate.
Option (B) – h1 × h2
If either one is too big, then the result will be too big too. Again, can overestimate that’s why it is not always admissible.
Option (C) – h1/h2 (when ℎ2 ≠ 0)
If division the two heuristics will not guarantee the result to be less than or equal to the true cost.
Example – h*(n) = 10, h1 = 5 and h2 = 0.2 then h1/h2 = 25. That is why it is not always admissible.
Option (D) – ∣h1 − h2∣
The absolute difference between two admissible heuristics. Since the result is always positive and the heuristics are both less than the true cost, the difference between them is also always less than the true cost. Therefore this will not mislead the cost and it is always admissible.
So, option (D) is the answer.
Q2 – Consider five random variables 𝑈, 𝑉, 𝑊, 𝑋, and 𝑌 whose joint distribution satisfies:
𝑃(𝑈,𝑉,𝑊,𝑋,𝑌) = 𝑃(𝑈)𝑃(𝑉)𝑃(𝑊|𝑈,𝑉)𝑃(𝑋|𝑊)𝑃(𝑌|𝑊)
Which ONE of the following statements is FALSE?
(A) 𝑌 is conditionally independent of 𝑉 given 𝑊
(B) 𝑋 is conditionally independent of 𝑈 given 𝑊
(C) 𝑈 and 𝑉 are conditionally independent given 𝑊
(D) 𝑌 and 𝑋 are conditionally independent given 𝑊
(GATE DS&AI 2024)
Ans – (C)
Explanation – This is a Bayesian Network Design or a Probabilistic Graphical Model Design in which
- U is independent
- V is independent
- W is dependent on both U and V.
- X is dependent on W
- Y is also dependent on W
Option A – True because Y and V having no edge.
Option B – True because X and U having no edge.
Option C – False because U and V are dependent on W.
Option D – True because W having and edge and is dependent on X and Y not vice versa.
Q3 – Consider the following statement:
In adversarial search, 𝛼–𝛽 pruning can be applied to game trees of any depth where 𝛼 is the (m) value choice we have formed so far at any choice point along the path for the MAX player and 𝛽 is the (n) value choice we have formed so far at any choice point along the path for the MIN player.
Which ONE of the following choices of (m) and (n) makes the above statement valid?
(A) (m) = highest, (n) = highest
(B) (m) = lowest, (n) = highest
(C) (m) = highest, (n) = lowest
(D) (m) = lowest, (n) = lowest
(GATE DS&AI 2024)
Ans – (C)
Explanation – α–β pruning helps to minimize the number of nodes that need to be visited in a minimax game tree.
- α (alpha) means (m) is the highest value found along the path for MAX (the player who tries to get the maximum value).
- β (beta) means (n) is the lowest value found along the path for MIN (the player who tries to get the minimum value).
Q4 – Let 𝑥 and 𝑦 be two propositions. Which of the following statements is a tautology /are tautologies?
(A) (¬𝑥∧𝑦 )⟹(𝑦⟹𝑥)
(B) (𝑥∧¬𝑦 )⟹(¬𝑥⟹𝑦)
(C) (¬𝑥∧𝑦 )⟹(¬𝑥⟹𝑦)
(D) (𝑥∧¬𝑦 )⟹(𝑦⟹𝑥)
(GATE DS&AI 2024)
Ans – (B, C, D)
Explanation –
Option A – Not a tautology
x | y | ¬𝑥 | ¬𝑦 | ¬𝑥∧𝑦 | 𝑦⟹𝑥 | (¬𝑥∧𝑦) ⟹(𝑦⟹𝑥) |
F | F | T | T | F | T | T |
F | T | T | F | T | F | F |
T | F | F | T | F | T | T |
T | T | F | F | F | T | T |
Option B – Tautology
x | y | ¬𝑥 | ¬𝑦 | 𝑥∧¬𝑦 | ¬𝑥⟹y | (𝑥∧¬𝑦) ⟹(¬𝑥⟹𝑦) |
F | F | T | T | F | F | T |
F | T | T | F | F | T | T |
T | F | F | T | T | T | T |
T | T | F | F | F | T | T |
Option C – Tautology
x | y | ¬𝑥 | ¬𝑦 | ¬𝑥∧𝑦 | ¬𝑥⟹y | (¬𝑥∧𝑦 )⟹(¬𝑥⟹𝑦) |
F | F | T | T | F | F | T |
F | T | T | F | T | T | T |
T | F | F | T | F | T | T |
T | T | F | F | F | T | T |
Option D – Tautology
x | y | ¬𝑥 | ¬𝑦 | 𝑥∧¬𝑦 | y ⟹ x | (𝑥∧¬𝑦 )⟹(𝑦⟹𝑥) |
F | F | T | T | F | T | T |
F | T | T | F | F | F | T |
T | F | F | T | T | T | T |
T | T | F | F | F | T | T |
Q5 – Let game(ball, rugby) be true if the ball is used in rugby and false otherwise.
Let shape(ball, round) be true if the ball is round and false otherwise.
Consider the following logical sentences:
s1: ∀ball ¬ game(ball, rugby) ⟹ shape(ball, round)
s2: ∀ball ¬ shape(ball, round) ⟹ game(ball, rugby)
s3: ∀ball game(ball, rugby) ⟹ ¬ shape(ball, round)
s4: ∀ball shape(ball, round) ⟹ ¬ game(ball, rugby)
Which of the following choices is/are logical representations of the assertion,
“All balls are round except balls used in rugby”?
(A) 𝑠1∧𝑠3
(B) 𝑠1∧𝑠2
(C) 𝑠2∧𝑠3
(D) 𝑠3∧𝑠4
(GATE DS&AI 2024)
Ans – (A, C)
Explanation – P = game(ball, rugby) Q = shape(ball, round)
(S1) ¬P ⟹ Q
- P V Q
(S2) ¬Q ⟹ P
- Q V P
(S3) P ⟹ ¬Q
- ¬P V ¬Q
(S4) Q ⟹ ¬P
- ¬Q V ¬P
The statement – “All balls are round except balls used in rugby”
- (Q ⟹ ¬P) Λ (¬P ⟹ Q)
- (¬Q V ¬P) Λ (P V Q)
Option A – S1ΛS3
- (P V Q) Λ (¬P V ¬Q) Correct.
Option B – S1ΛS2
- (P V Q) Λ (Q V P) Not Correct.
Option C – S2ΛS3
- (Q V P) Λ (¬P V ¬Q) Correct.
Option D – S3ΛS4
- (¬P V ¬Q) Λ (¬Q V ¬P) Not Correct.
Q6 – Details of ten international cricket games between two teams “Green” and “Blue” are given in Table C. This table consists of matches played on different pitches, across formats along with their winners. The attribute Pitch can take one of two values: spin-friendly (represented as 𝑆) or pace-friendly (represented as 𝐹). The attribute Format can take one of two values: one-day match (represented as 𝑂) or test match (represented as 𝑇).
A cricket organization would like to use the information given in Table C to develop a decision-tree model to predict outcomes of future games between these two teams.
To develop such a model, the computed InformationGain(C, Pitch) with respect to the Target is ______ (rounded off to two decimal places).
Table C Match Number | Pitch | Format | Winner (Target) |
1 | 𝑆 | 𝑇 | Green |
2 | 𝑆 | 𝑇 | Blue |
3 | 𝐹 | 𝑂 | Blue |
4 | 𝑆 | 𝑂 | Blue |
5 | 𝐹 | 𝑇 | Green |
6 | 𝐹 | 𝑂 | Blue |
7 | 𝑆 | 𝑂 | Green |
8 | 𝐹 | 𝑇 | Blue |
9 | 𝐹 | 𝑂 | Blue |
10 | 𝑆 | 𝑂 | Green |
(GATE DS&AI 2024)
Ans – (0.12 to 0.13)
Explanation –
Entropy of Winner
Total Events =10
P(Green) = 4/10
P(Blue) = 6/10
Entropy = -[4/10*log2(4/10) + 6/10*log2(6/10)] = 0.971
Entropy of Pitch
Total Events for Spin = 5
P(Green) = 3/5
P(Blue) = 2/5
Entropy = -[3/5*log2(3/5) + 2/5*log2(2/5)] = 0.971
Total Events for Pace = 5
P(Green) = 1/5
P(Blue) = 4/5
Entropy = -[3/5*log2(3/5) + 2/5*log2(2/5)] = 0.721
Weighted Entropy = Probability of Events of Spin*Entropy of Spin + Probability of Events of Pace*Entropy of Pace
Weighted Entropy = (5/10)*0.971 + (5/10)*0.721 = 0.846
Information Gain = Entropy of winner – weighted entropy = 0.971 – 0.846 = 0.125
Rounded of to two decimal places = 0.12
Q7 – Given the following Bayesian Network consisting of four Bernoulli random variables and the associated conditional probability tables:
The value of 𝑃(𝑈=1, 𝑉=1, 𝑊=1, 𝑍=1) = ______ (rounded off to three decimal places).
(GATE DS&AI 2024)
Ans – (0.125)
Explanation – 4 Bernoulli random variables U → V, U → W, V → Z, W → Z
We have to find P(U=1, V=1, W=1, Z=1)
From the tables
P(U=1) = 0.5
P(V=1∣U=1) = 0.5
P(W=1∣U=1) = 1
P(Z=1∣V=1,W=1) = 0.5
P(U=1,V=1,W=1,Z=1) = 0.5*0.5*1*0.5 = 0.125