-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathaima_solutions.html
1515 lines (1502 loc) · 74.3 KB
/
aima_solutions.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
<html><head><title>niplav</title>
<link href="./favicon.png" rel="shortcut icon" type="image/png"/>
<link href="main.css" rel="stylesheet" type="text/css"/>
<meta content="text/html; charset=utf-8" http-equiv="Content-Type"/>
<!DOCTYPE HTML>
<style type="text/css">
code.has-jax {font: inherit; font-size: 100%; background: inherit; border: inherit;}
</style>
<script async="" src="./mathjax/latest.js?config=TeX-MML-AM_CHTML" type="text/javascript">
</script>
<script type="text/x-mathjax-config">
MathJax.Hub.Config({
extensions: ["tex2jax.js"],
jax: ["input/TeX", "output/HTML-CSS"],
tex2jax: {
inlineMath: [ ['$','$'], ["\\(","\\)"] ],
displayMath: [ ['$$','$$'], ["\\[","\\]"] ],
processEscapes: true,
skipTags: ['script', 'noscript', 'style', 'textarea', 'pre']
},
"HTML-CSS": { availableFonts: ["TeX"] }
});
</script>
<script>
document.addEventListener('DOMContentLoaded', function () {
// Change the title to the h1 header
var title = document.querySelector('h1')
if(title) {
var title_elem = document.querySelector('title')
title_elem.textContent=title.textContent + " – niplav"
}
});
</script>
</head><body><h2 id="home"><a href="./index.html">home</a></h2>
<p><em>author: niplav, created: 2021-01-21, modified: 2021-03-31, language: english, status: in progress, importance: 2, confidence: likely</em></p>
<blockquote>
<p><strong>In which I solve exercsise from <a href="https://en.wikipedia.org/wiki/Artificial_Intelligence:_A_Modern_Approach">“Artificial Intelligence: A Modern
Approach”</a>,
written by <a href="https://en.wikipedia.org/wiki/Stuart_J._Russell">Stuart
Russell</a> and <a href="https://en.wikipedia.org/wiki/Peter_Norvig">Peter
Norvig</a>. I use the 3rd edition
from 2010, because the exercises for the 4th edition were moved online.</strong></p>
</blockquote><div class="toc"><div class="toc-title">Contents</div><ul><li><a href="#Chapter_1">Chapter 1</a><ul><li><a href="#11">1.1</a><ul><li><a href="#Intelligence">Intelligence</a><ul></ul></li><li><a href="#Artificial_Intelligence">Artificial Intelligence</a><ul></ul></li><li><a href="#Agent">Agent</a><ul></ul></li><li><a href="#Rationality">Rationality</a><ul></ul></li><li><a href="#Logical_Reasoning">Logical Reasoning</a><ul></ul></li></ul></li><li><a href="#13">1.3</a><ul></ul></li><li><a href="#14">1.4</a><ul></ul></li><li><a href="#15">1.5</a><ul></ul></li></ul></li><li><a href="#Chapter_2">Chapter 2</a><ul><li><a href="#21">2.1</a><ul></ul></li><li><a href="#23">2.3</a><ul></ul></li><li><a href="#24">2.4</a><ul></ul></li></ul></li><li><a href="#Chapter_3">Chapter 3</a><ul><li><a href="#31">3.1</a><ul></ul></li><li><a href="#32">3.2</a><ul></ul></li></ul></li><li><a href="#Chapter_6">Chapter 6</a><ul><li><a href="#61">6.1</a><ul></ul></li><li><a href="#65">6.5</a><ul></ul></li></ul></li><li><a href="#Chapter_7">Chapter 7</a><ul><li><a href="#710">7.10</a><ul></ul></li><li><a href="#714">7.14</a><ul></ul></li></ul></li><li><a href="#Chapter_9">Chapter 9</a><ul><li><a href="#99">9.9</a><ul></ul></li></ul></li><li><a href="#Chapter_13">Chapter 13</a><ul><li><a href="#131">13.1</a><ul></ul></li><li><a href="#132">13.2</a><ul></ul></li><li><a href="#133">13.3</a><ul></ul></li><li><a href="#135">13.5</a><ul></ul></li><li><a href="#136">13.6</a><ul></ul></li></ul></li><li><a href="#Chapter_14">Chapter 14</a><ul><li><a href="#141">14.1</a><ul></ul></li></ul></li><li><a href="#Chapter_15">Chapter 15</a><ul><li><a href="#1513">15.13</a><ul></ul></li><li><a href="#1514">15.14</a><ul></ul></li></ul></li><li><a href="#Chapter_16">Chapter 16</a><ul><li><a href="#161">16.1</a><ul><li><a href="#Ranking_My_Answers">Ranking My Answers</a><ul></ul></li></ul></li><li><a href="#Ranking_My_Answers_1">Ranking My Answers</a><ul></ul></li><li><a href="#163">16.3</a><ul></ul></li><li><a href="#1615">16.15</a><ul></ul></li><li><a href="#1617">16.17</a><ul></ul></li></ul></li><li><a href="#Chapter_17">Chapter 17</a><ul><li><a href="#173">17.3</a><ul></ul></li></ul></li></ul></div>
<h1 id="Solutions_to_Artificial_Intelligence_A_Modern_Approach"><a class="hanchor" href="#Solutions_to_Artificial_Intelligence_A_Modern_Approach">Solutions to “Artificial Intelligence: A Modern Approach”</a></h1>
<h2 id="Chapter_1"><a class="hanchor" href="#Chapter_1">Chapter 1</a></h2>
<h3 id="11"><a class="hanchor" href="#11">1.1</a></h3>
<blockquote>
<p>Define in your own words: (a) intelligence, (b) artificial intelligence,
(c) agent, (d) rationality, (e) logical reasoning</p>
</blockquote>
<h4 id="Intelligence"><a class="hanchor" href="#Intelligence">Intelligence</a></h4>
<p>The word “intelligence” is mostly used to describe a property of
systems. Roughly, it refers to the ability of a system to make decisions
that result in consequences are graded high according to some metric,
as opposed to decisions that result in consequences that are graded low
according to that metric.</p>
<h4 id="Artificial_Intelligence"><a class="hanchor" href="#Artificial_Intelligence">Artificial Intelligence</a></h4>
<p>“Artificial intelligence” refers to systems designed and implemented
by humans with the aim of these systems displaying intelligent behavior.</p>
<h4 id="Agent"><a class="hanchor" href="#Agent">Agent</a></h4>
<p>An “agent” is a part of the universe that carries out goal-directed
actions.</p>
<h4 id="Rationality"><a class="hanchor" href="#Rationality">Rationality</a></h4>
<p>The usage of the word “rationality” is difficult to untangle from
the usage of the word “intelligence”. For humans, “rationality”
usually refers to the ability to detect and correct cognitive errors
that hinder coming to correct conclusions about the state of the world
(epistemic rationality), as well as the ability to act on those beliefs
according to ones values (instrumental rationality). However, these
seem very related to “intelligence”, maybe only being separated by a
potentiality–intelligence being the potential, and rationality being
the ability to fulfill that potential. One could attempt to apply the
same definition to artificial intelligences, but it seems unclear how
a lawful process could be more intelligent, but is not.</p>
<h4 id="Logical_Reasoning"><a class="hanchor" href="#Logical_Reasoning">Logical Reasoning</a></h4>
<p>“Logical reasoning” refers to the act of deriving statements from
other statements according to pre-defined rules.</p>
<h3 id="13"><a class="hanchor" href="#13">1.3</a></h3>
<p>A reflex action is not intelligent, as it is not the result of a
deliberate reasoning process. According to my personal definition above
(and also the definition given in the text), it is also not rational
(since the action is not guided by a belief).</p>
<p>Common usage of the term “rational” indicates that
people would describe this reflex as a rational action. I
believe this is fine, and words are just pointers to <a href="https://www.lesswrong.com/posts/jMTbQj9XB5ah2maup/similarity-clusters">clusters in
thing-space</a>
anyway.</p>
<h3 id="14"><a class="hanchor" href="#14">1.4</a></h3>
<blockquote>
<p>Suppose we extend Evans’s ANALOGY program so that it can score 200
on a standard IQ test. Would we then have a program more intelligent
than a human? Explain.</p>
</blockquote>
<p>No. (At least not for any useful definition of intelligence). IQ
tests as they currently exist measure a proxy for the actual ability
to perform complex tasks in the real world. For humans, geometry
puzzles correlate (and predict) well with such tests (<a href="./doc/psychology/iq/the_predictive_value_of_iq_sternberg_2001.pdf" title="The Predictive Value of IQ">Sternberg et al.
2001</a>).</p>
<p>However, this proxy breaks down once we start optimising for it (as
in the case on extending ANALOGY). We can now not predict real-world
performance on arbitrary goals given the result of the IQ test performed
on ANALOGY anymore.</p>
<h3 id="15"><a class="hanchor" href="#15">1.5</a></h3>
<blockquote>
<p>The neural structure of the sea slug Aplysia has been widely studied
(first by Nobel Laureate Eric Kandel) because it has only about 20,000
neurons, most of them large and easily manipulated. Assuming that the
cycle time for an Aplysia neuron is roughly the same as for a human
neuron, how does the computational power, in terms of memory updates
per second, compare with the high-end computer described in Figure 1.3?</p>
</blockquote>
<!--TODO: un-fuck the dimensional analysis here-->
<p>Given the cycle time of <code>$10^{-3}$</code> seconds, we can expect</p>
<div>
$$\frac{2*10^{4} \hbox{ neurons}}{10^{-3}\frac{\hbox{s}}{\hbox{update}}}=2*10^{7} \frac{\hbox{neuron updates}}{s}$$
</div>
<p>which is seven orders of magnitude lower than a supercomputer. Aplysia
won't be proving any important theorems soon.</p>
<!--
If Aplysia has 20k neurons, then it can be expected to have
`$2*10^{4}\hbox{ neurons }*\frac{10 \hbox{ to } 10^{5} \hbox{ synapses }}{\hbox{neuron}}=2*10^{5}\hbox{ to } 2*10^{9} \hbox{ neurons}$`
-->
<h2 id="Chapter_2"><a class="hanchor" href="#Chapter_2">Chapter 2</a></h2>
<h3 id="21"><a class="hanchor" href="#21">2.1</a></h3>
<blockquote>
<p>Suppose that the performance measure is concerned with just the first
T time steps of the environment and ignores everything thereafter. Show
that a rational agent’s action may depend not just on the state of
the environment but also on the time step it has reached.</p>
</blockquote>
<p>Example: Let's say that we are in an environment with a button,
and pressing the button causes a light to go on in the next timestep.
The agent cares that the light is on (obtaining 1 util per timestep the
light is on for the first T timesteps).</p>
<p>However, pressing the button incurs a cost of ½ on the agent.</p>
<p>Then, at timestep T, the agent will not press the button, since it does
not care about the light being on at timestep T+1, and wants to avoid
the cost ½. At timesteps <code>$<T$</code> it will press the button, with the light
currently being on, at timestep T it will not press the button, under
the same environmental conditions.</p>
<h3 id="23"><a class="hanchor" href="#23">2.3</a></h3>
<blockquote>
<p>For each of the following assertions, say whether it is true or
false and support your answer with examples or counterexamples where
appropriate.</p>
<p>a. An agent that senses only partial information about the state cannot
be perfectly rational.</p>
</blockquote>
<p>False. An agent that senses only partial information about the state could
infer missing information by making deductions (logical or statistical)
about the state of the environment, coming to full knowledge of the
environment, and making perfectly rational choices using that information.</p>
<p>For example, a chess-playing agent that can't see exactly one square
could infer the piece standing on that square by observing which piece
is missing from the rest of the board.</p>
<blockquote>
<p>b. There exist task environments in which no pure reflex agent can
behave rationally.</p>
</blockquote>
<p>True. In an environment in which the next reward depends on the current
state and the previous state, a simple reflex agent will get outperformed
by agents with an internal world-model.</p>
<p>An example for this is a stock-trading agent: The future prices of stocks
doesn't just depend on the current prices, but on the history of prices.</p>
<blockquote>
<p>c. There exists a task environment in which every agent is rational.</p>
</blockquote>
<p>True. It is the environment where the agent has no options to act.</p>
<blockquote>
<p>d. The input to an agent program is the same as the input to the
agent function.</p>
</blockquote>
<p>Not sure. Both the agent function and the agent program receive percepts,
but sometimes the agent program also needs information that is not a
percept (e.g. priors for bayesian agents). Is that counted as input,
or simply as program-specific data?</p>
<blockquote>
<p>e. Every agent function is implementable by some program/machine
combination.</p>
</blockquote>
<p>False. An agent function could be uncomputable
(e. g. <a href="https://en.wikipedia.org/wiki/AIXI">AIXI</a>), and therefore not
be implementable on a real-world machine.</p>
<blockquote>
<p>f. Suppose an agent selects its action uniformly at random from the
set of possible actions. There exists a deterministic task environment
in which this agent is rational.</p>
</blockquote>
<p>True, that would be the environment in which every action scores equally
well on the performance measure.</p>
<blockquote>
<p>g. It is possible for a given agent to be perfectly rational in two
distinct task environments.</p>
</blockquote>
<p>True. Given two agents <code>$A_X$</code> and <code>$A_Y$</code>, and two task environments
<code>$X$</code> (giving percepts from the set <code>$\{x_1, \dots, x_n\}$</code>) and <code>$Y$</code>
(giving percepts from the set <code>$\{y_1, \dots, y_n\}$</code>), with <code>$A_X$</code> being
perfectly rational in <code>$X$</code> and <code>$A_Y$</code> being perfectly rational in <code>$Y$</code>
an agent that is perfectly rational in two distinct task environments
could be implemented using the code:</p>
<pre><code>p=percept()
if p∈X
A_X(p)
while p=percept()
A_X(p)
if p∈Y
A_Y(p)
while p=percept()
A_Y(p)
</code></pre>
<blockquote>
<p>h. Every agent is rational in an unobservable environment.</p>
</blockquote>
<p>False. Given an unobservable environment in which moving results in
the performance measure going up (e.g. by knocking over ugly vases),
agents that move a lot are more rational than agents that do not move.</p>
<blockquote>
<p>i. A perfectly rational poker-playing agent never loses.</p>
</blockquote>
<p>False. Given incomplete knowledge, a rational poker-playing agent can
only win in expectation.</p>
<h3 id="24"><a class="hanchor" href="#24">2.4</a></h3>
<blockquote>
<p>For each of the following activities, give a PEAS description of the
task environment and characterize it in terms of the properties listed
in Section 2.3.2</p>
<ul>
<li>Playing soccer.</li>
</ul>
</blockquote>
<p>Performance measure: <code>$goals_{own}-goals_{enemy}$</code>; environment: soccer
field; actuators: legs & feet, arms & hands (for goalkeeper), torso,
head; sensors: vision, hearing, tactile</p>
<p>Multi-agent, continuous, partially observable, fully known (both rules
of soccer and classical mechanics underlying the ball & other players,
although fluid dynamics of air-player interaction is probably tricky),
sequential, dynamic, stochastic (in theory deterministic, but practically
stochastic, very small unobservable effects can have large consequences)</p>
<blockquote>
<ul>
<li>Exploring the subsurface oceans of Titan.</li>
</ul>
</blockquote>
<p>Performance measure: surface explored; environment: subsurface
environments of Titan; actuators: motor with propeller, arms to grab
things, perhaps wheels; sensors: radar, vision (if the agent has inbuilt
light generation)</p>
<p>Single-agent, continuous, partially observable, partially known (in case
there's actually life there, we don't know how it behaves), sequential,
dynamic (maybe not very dynamic, but there might be currents/geothermal
vents/life), stochastic.</p>
<blockquote>
<ul>
<li>Shopping for used AI books on the internet.</li>
</ul>
</blockquote>
<p>Performance measure: <code>$\frac{n_{books}}{\sum_{b \in books} p(b)}$</code> (price
per book); environment: web browser; actuators: keyboard, mouse; sensors:
vision of the screen, location of mouse, state of keys on keyboard pressed</p>
<p>Multi-agent (if bidding against others), discrete, partially observable,
fully known (unless bidding against others, since that would need model
of human psychology), sequential (money in bank account is not reset),
static (again, unless bidding against others), deterministic</p>
<blockquote>
<ul>
<li>Playing a tennis match.</li>
</ul>
</blockquote>
<p>Performance measure: <code>$points_{own}-points_{enemy}$</code> (I think tennis
uses rounds? Maybe <code>$winrounds_{own}-winrounds_{enemy}$</code>); environment:
tennis court; actuators: arms, tennis racket, wheels/legs to move around;
sensors: vision, hearing</p>
<p>Multi-agent, continous, fully observable, fully known (though caveats
similar to soccer apply), episodic (after each round there's a reset,
right?), dynamic, stochastic (similar caveats as in soccer example)</p>
<blockquote>
<ul>
<li>Practicing tennis against a wall.</li>
</ul>
</blockquote>
<p>Performance measure: number of balls hit; environment: place with wall;
actuators: arms, tennis racket, wheels/legs to move around; sensors:
vision, hearing</p>
<p>Single-agent, continous, fully observable, fully known (though caveats
similar to soccer apply), episodic, dynamic, stochastic (similar caveats
as in soccer example)</p>
<blockquote>
<ul>
<li>Performing a high jump.</li>
</ul>
</blockquote>
<p>Performance measure: height of the jump; environment: a place with a
high/nonexistent ceiling; actuators: legs; sensors: tactile sensors in
feet, height sensor</p>
<p>Single-agent, continuous, fully observable (unless wind), fully known
(although, again, caveats as in soccer), episodic (unless falling over
and not being able to get up again), static, deterministic (unless wind)</p>
<blockquote>
<ul>
<li>Knitting a sweater.</li>
</ul>
</blockquote>
<p>Performance measure: beauty, robustness and comfortableness of the
sweater; environment: a cozy sofa in the living room; actuators: needles
for knitting; sensors: tactile sensors for the needles, visual sensors
for observing the sweater</p>
<p>Single-agent, continuous, fully observable, fully known (again using
classical mechanics), sequential (unless unraveling completely & starting
again is an option), static, deterministic</p>
<blockquote>
<ul>
<li>Bidding on an item at an auction.</li>
</ul>
</blockquote>
<p>Performance measure: <code>$\frac{nitems}{\sum_{i \in items} price(item)}$</code>;
environment: bidding platform/auction house; actuators: text entering for
online/audio output for bidding; sensors: vision of the screen/auditory
in the case of the auction house, visual to observe the items presented</p>
<p>Multi-agent, discrete (money is usually discrete), fully observable,
partially known (other bidders might be human and too complex to fully
model), sequential (account balance persistent throughout auction),
dynamic, deterministic</p>
<h2 id="Chapter_3"><a class="hanchor" href="#Chapter_3">Chapter 3</a></h2>
<h3 id="31"><a class="hanchor" href="#31">3.1</a></h3>
<blockquote>
<p>Explain why problem formulation must follow goal formulation.</p>
</blockquote>
<p>The goal formulation applies first & foremost to the real world. The
problem formulation, however, then translates this real-world goal into
a format that computers can deal with. Formulating the problem before
the goal has no “anchor” as to what to formalize, the goal gives
information on what to concentrate on.</p>
<h3 id="32"><a class="hanchor" href="#32">3.2</a></h3>
<blockquote>
<p>Your goal is to navigate a robot out of a maze. The robot starts in the
center of the maze facing north. You can turn the robot to face north,
east, south, or west. You can direct the robot to move forward a certain
distance, although it will stop before hitting a wall.</p>
<p>a. Formulate this problem. How large is the state space?</p>
</blockquote>
<p>Assumption: The maze has size <code>$n*m$</code>. Size of the state space: <code>$4*n*m$</code>.</p>
<blockquote>
<p>b. In navigating a maze, the only place we need to turn is at the
intersection of two or more corridors. Reformulate this problem using
this observation. How large is the state space now?</p>
</blockquote>
<p>Let i be the number of intersections. Then there are <code>$2*((n*m)-i)+i*4$</code>
different states (2 for each non-intersection state (walking forward
or backward, and 4 for each intersection state, for each direction the
agent can go).</p>
<p>However, this does not consider dead ends or intersections where there
are only 3 valid directions. If there are <code>$i_d$</code> dead ends, <code>$i_3$</code>
intersections with 3 possible directions, and <code>$i_4$</code> intersections
with 4 possible directions, the number of possible states is instead
<code>$i_d+3*i_3+4*i_4+2*((n*m)-(i_d+i_3+i_4))$</code>.</p>
<blockquote>
<p>c. From each point in the maze, we can move in any of the four
directions until we reach a turning point, and this is the only action
we need to do. Reformulate the problem using these actions. Do we need
to keep track of the robot’s orientation now?</p>
</blockquote>
<p>Since we don't have to turn before moving, we're equivalent to an
unchanging directionless dot (only the position changes). We don't
need to keep track of the orientation anymore, since we don't have to
a specific direction before moving.</p>
<blockquote>
<p>d. In our initial description of the problem we already abstracted
from the real world, restricting actions and removing details. List
three such simplifications we made.</p>
</blockquote>
<p>Only 4 different directions allowed, not being able to run into walls,
the robot will move the given distance (and not experience battery
failure/fall into a hole etc.).</p>
<h2 id="Chapter_6"><a class="hanchor" href="#Chapter_6">Chapter 6</a></h2>
<h3 id="61"><a class="hanchor" href="#61">6.1</a></h3>
<blockquote>
<p>How many solutions are there for the map-coloring problem in Figure
6.1? How many solutions if four colors are allowed? Two colors?</p>
</blockquote>
<ul>
<li>2 colors: 0 possible solutions</li>
<li>3 colors: <code>$3*3*2=18$</code> possible solutions (TA and SA are free, and then the WA-NT-Q-NSW-V chain can only be colored with 2 different colors, which have to be alternating)</li>
<li>4 colors: <code>$4*4*(3*2*2*2*2)=768$</code> possible solutions (again, TA and SA are free, and then WA-NT-Q-NSW-V have 3 colors left, but no same color twice, which means 3 colors for the first option, and two for each successor)</li>
</ul>
<h3 id="65"><a class="hanchor" href="#65">6.5</a></h3>
<blockquote>
<p>Solve the cryptarithmetic problem in Figure 6.2 by hand, using
the strategy of backtracking with forward checking and the MRV and
least-constraining-value heuristics.</p>
</blockquote>
<p><img alt="Figure 6.2" src="./img/aima_solutions/figure_6_2.png" title="Figure 6.2 (a) A cryptarithmetic problem. Each letter stands for a distinct digit; the aim is to find a substitution of digits for letters such that the resulting sum is arithmetically correct, with the added restriction that no leading zeroes are allowed. (b) The constraint hypergraph for the cryptarithmetic problem, showing the Alldiff constraint (square box at the top) as well as the column addition constraints (four square boxes in the middle). The variables C1, C2, and C3 represent the carry digits for the three columns."/></p>
<p>Variables: <code>$X=\{F, T, U, W, R, O, C_1, C_2, C_3\}$</code><br/>
Constraints:
</p><div>
$$C={\langle O, R \rangle: O+O \mod 10=R, \
\langle W, U, C<em>1 \rangle: W+W+C</em>1 \mod 10=U, \
\langle T, O, C<em>2 \rangle: T+T+C</em>2 \mod 10=O, \
\langle C<em>1, O \rangle: C</em>1=1 \hbox{ if } O+O>9 \hbox { else } 0, \
\langle C<em>2, W, C</em>1 \rangle: C<em>2=1 \hbox{ if } W+W+C</em>1>9 \hbox { else } 0, \
\langle C<em>3, T, C</em>2 \rangle: C<em>3=1 \hbox{ if } T+T+C</em>2>9 \hbox { else } 0, \
\langle F, C<em>3 \rangle: F=C</em>3\
\langle F, T, U, W, R, O \rangle: Alldiff(F, T, U, W, R, O)}$$
</div>
<p>Domains: <code>$\{0..9\}$</code> for <code>$\{F, T, U, W, R, O\}$</code>, and <code>$\{0, 1\}$</code> for <code>$\{C_1, C_2, C_3\}$</code>.</p>
<p>Replacing the Alldiff constraint with binary constraints:</p>
<div>
$$C := (C \backslash \{\langle F, T, U, W, R, O \rangle: Alldiff(F, T, U, W, R, O)\}) \cup \\{ \langle x_1, x_2 \rangle: x_1 \not = x_2 | x_1, x_2 \in \{ F, T, U, W, R, O \} }$$
</div>
<p>Replacing the other trinary constraints with binary ones:</p>
<p>New variables <code>$X_1, X_2 \in [10] \times \{0, 1\}$</code>.</p>
<p>We remove the constraints</p>
<div>
$$\{\langle W, U, C_1 \rangle: W+W+C_1 \mod 10=U, \\
\langle T, O, C_2 \rangle: T+T+C_2 \mod 10=O, \\
\langle C_2, W, C_1 \rangle: C_2=1 \hbox{ if } W+W+C_1>9 \hbox { else } 0, \\
\langle C_3, T, C_2 \rangle: C_3=1 \hbox{ if } T+T+C_2>9 \hbox { else } 0 \} $$
</div>
<p>and add some constraints to replace the trinary with binary constraints on
<code>$X_{1 \hbox{ to } 4}$</code>. The result looks like this:</p>
<div>
$$ C := \{ \langle X_1, U \rangle: U=fst(X_1)+fst(X_1)+snd(X_1) \mod 10, \\
\langle X_2, O \rangle: O=fst(X_2)+fst(X_2)+snd(X_2) \mod 10, \\
\langle X_1, C_2 \rangle: C_2=1 \hbox{ if } fst(X_1)+fst(X_1)+snd(X_1)>9 \hbox { else } 0, \\
\langle X_2, C_3 \rangle: C_3=1 \hbox{ if } fst(X_2)+fst(X_2)+snd(X_2)>9 \hbox { else } 0, \\
\langle X_1, W \rangle: W=fst(X_1), \\
\langle X_1, C_1 \rangle: C_1=snd(X_1), \\
\langle X_2, T \rangle: T=fst(X_2), \\
\langle X_2, C_2 \rangle: C_2=snd(X_2), \\
\langle O, R \rangle: O+O \mod 10=R, \\
\langle C_1, O \rangle: C_1=1 \hbox{ if } O+O>9 \hbox { else } 0, \\
\langle F, C_3 \rangle: F=C_3 \} \\ \cup
\{ \langle x_1, x_2 \rangle: x_1 \not = x_2 | x_1, x_2 \in \{ F, T, U, W, R, O \} $$
</div>
<p>Variables sorted by domain size: <code>$X_1: 20, X_2: 20, F: 10, T: 10, U: 10, W: 10, R: 10, O: 10, C_1: 2, C_2: 2, C_3: 2$</code></p>
<p>Variables sorted by degree: <code>$O: 8, W: 6, T: 6, R: 6, U: 6, F: 6, X_1: 4, X_2: 4, C_1: 2, C_2: 2, C_3: 2$</code></p>
<p>Now, one can do the actual searching and inference:</p>
<ul>
<li>Assign (tie between <code>$C_1, C_2, C_3$</code> in remaining values, choosing <code>$C_1$</code> randomly): <code>$C_1=1$</code>
<ul>
<li>Infer: <code>$X_1 \in [10] \times \{1\}$</code></li>
<li>Infer: <code>$O \in \{5,6,7,8,9\}$</code></li>
<li>Infer: <code>$X_2 \in \{2,3,4,7,8,9\} \times \{0, 1\}$</code></li>
<li>Infer: <code>$R \in \{0,2,4,6,8\}$</code></li>
<li>Infer: <code>$T \in \{2,3,4,7,8,9\}$</code></li>
<li>Assign: (tie between <code>$C_2, C_3$</code> in remaining values, choosing <code>$C_2$</code> next): <code>$C_2=1$</code>
<ul>
<li>Infer from <code>$C_2$</code>: <code>$X_1 \in \{5,6,7,8,9\} \times \{1\}$</code></li>
<li>Infer from <code>$C_2$</code>: <code>$X_2 \in \{2,3,4,7,8,9\} \times \{1\}$</code></li>
<li>Infer from <code>$X_1$</code>: <code>$U \in \{1, 3, 5, 7, 9\}$</code></li>
<li>Infer from <code>$X_1$</code>: <code>$W \in \{5,6,7,8,9\}$</code></li>
<li>Infer from <code>$X_2$</code>: <code>$O \in \{5,7,9\}$</code></li>
<li>Infer from <code>$X_2$</code>: <code>$T \in \{2,3,4,7,8,9\}$</code></li>
<li>Infer from <code>$O$</code>: <code>$R \in \{0, 4, 8\}$</code></li>
<li>Assign: <code>$C_3=1$</code>
<ul>
<li>Infer from <code>$C_3$</code>: <code>$X_2 \in \{7,8,9\} \times \{1\}$</code></li>
<li>Infer from <code>$C_3$</code>: <code>$F=1$</code></li>
<li>Infer from <code>$F$</code>: <code>$U \in \{3,5,7,9\}$</code></li>
<li>Infer from <code>$U$</code>: <code>$X_1 \in \{6,7,8,9\} \times \{1\}$</code></li>
<li>Infer from <code>$X_1$</code>: <code>$W \in \{6,7,8,9\}$</code></li>
<li>Assign: <code>$R=0$</code>
<ul>
<li>Infer from <code>$R$</code>: <code>$O \in \emptyset$</code></li>
</ul></li>
<li>Backtrack, assign: <code>$R=4$</code>
<ul>
<li>Infer from <code>$R$</code>: <code>$O=7$</code></li>
<li>Infer from <code>$R$</code>: <code>$T \in \{2,3,7,8,9\}$</code></li>
<li>Infer from <code>$O$</code>: <code>$X_2=(8,1)$</code></li>
<li>Infer from <code>$O$</code>: <code>$T \in \{2,3,8,9\}$</code></li>
<li>Infer from <code>$O$</code>: <code>$W \in \{6,8,9\}$</code></li>
<li>Infer from <code>$X_2$</code>: <code>$T=8$</code></li>
<li>Infer from <code>$W$</code>: <code>$X_1 \in \{6,8,9\} \times \{1\}$</code></li>
<li>Infer from <code>$T$</code>: <code>$W \in \{6,9\}$</code></li>
<li>Infer from <code>$W$</code>: <code>$X_1 \in \{6,9\} \times \{1\}$</code></li>
<li>Infer from <code>$X_1$</code>: <code>$U \in \{3,9\}$</code></li>
<li>Assign: <code>$W=6$</code>
<ul>
<li>Infer from <code>$W$</code>: <code>$X_1=(6,1)$</code></li>
<li>Infer from <code>$X_1$</code>: <code>$U=3$</code></li>
</ul></li>
</ul></li>
</ul></li>
</ul></li>
</ul></li>
</ul>
<p>The assignments are
<code>$C_1=1, C_2=1, C_3=1, F=1, T=8, U=3, W=6, R=4, O=7, X_1=(6,4), X_2=(8,1).$</code>
Or, in the puzzle:</p>
<div>
$$
\matrix {
& 8 & 6 & 7 \cr
+ & 8 & 6 & 7 \cr
\hline{}
1 & 7 & 3 & 4 \cr
}
$$
</div>
<h2 id="Chapter_7"><a class="hanchor" href="#Chapter_7">Chapter 7</a></h2>
<h3 id="710"><a class="hanchor" href="#710">7.10</a></h3>
<blockquote>
<p>Decide whether each of the following sentences is valid, unsatisfiable,
or neither. Verify your decisions using truth tables or the equivalence
rules of Figure 7.11 (page 249).</p>
<p>a. <code>$Smoke \Rightarrow Smoke$</code></p>
</blockquote>
<div>
$$Smoke \Rightarrow Smoke \equiv \\
\lnot Smoke \lor Smoke \equiv \\
True$$
</div>
<p>The sentence is valid since True is valid.</p>
<blockquote>
<p>b. <code>$Smoke \Rightarrow Fire$</code></p>
</blockquote>
<p><code>$Smoke \Rightarrow Fire \equiv \lnot Smoke \lor Fire$</code></p>
<p>Neither: If Smoke=True and Fire=False, then the sentence is false,
if Smoke=False and Fire=False, the sentence is true.</p>
<blockquote>
<p>c. <code>$(Smoke \Rightarrow Fire) \Rightarrow (\lnot Smoke \Rightarrow \lnot Fire)$</code></p>
</blockquote>
<div>
$$(Smoke \Rightarrow Fire) \Rightarrow (\lnot Smoke \Rightarrow \lnot Fire) \equiv \\
\lnot (\lnot Smoke \lor Fire) \lor (Smoke \lor \lnot Fire) \equiv \\
(Smoke \land \lnot Fire) \lor Smoke \lor \lnot Fire$$
</div>
<p>Neither: For Smoke=False and Fire=True, the sentence is false, but for
Smoke=True, the sentence is true.</p>
<blockquote>
<p>d. <code>$Smoke \lor Fire \lor \lnot Fire$</code></p>
</blockquote>
<p><code>$Smoke \lor Fire \lor \lnot Fire \equiv Smoke \lor True = True$</code></p>
<p>This sentence is valid, since it is equivalent to True.</p>
<blockquote>
<p>e. <code>$((Smoke \land Heat) \Rightarrow Fire) \Leftrightarrow ((Smoke \Rightarrow Fire) \lor (Heat \Rightarrow Fire))$</code></p>
</blockquote>
<div>
$$((Smoke \land Heat) \Rightarrow Fire) \Leftrightarrow ((Smoke \Rightarrow Fire) \lor (Heat \Rightarrow Fire)) \equiv \\
((\lnot Smoke \lor \lnot Heat \lor Fire) \Leftrightarrow (\lnot Smoke \lor Fire \lor \lnot Heat)) \equiv \\
True$$
</div>
<p>This sentence is valid since <code>$a \Leftrightarrow a \equiv True$</code>.</p>
<blockquote>
<p>f. <code>$(Smoke \Rightarrow Fire) \Rightarrow ((Smoke \land Heat) \Rightarrow Fire)$</code></p>
</blockquote>
<div>
$$(Smoke \Rightarrow Fire) \Rightarrow ((Smoke \land Heat) \Rightarrow Fire) \equiv \\
\lnot (\lnot Smoke \lor Fire) \lor (\lnot (Smoke \land Heat) \lor Fire) \equiv \\
(Smoke \land \lnot Fire) \lor \not Smoke \lor \lnot Heat \lor Fire \equiv $$
</div>
<p>This sentence is valid. If Smoke=True, Heat=True and Fire=False, then
<code>$Smoke \land \lnot Fire$</code> is true, and makes the whole sentence true.
Otherwise, any of the other disjunctions make the sentence true.</p>
<blockquote>
<p>g. <code>$Big \lor Dumb \lor (Big \Rightarrow Dumb)$</code></p>
</blockquote>
<p><code>$Big \lor Dumb \lor (Big \Rightarrow Dumb) \equiv Big \lor Dumb \lor \lnot Big \lor Dumb \equiv True$</code>.</p>
<p>Therefore, this sentence is valid as heck.</p>
<h3 id="714"><a class="hanchor" href="#714">7.14</a></h3>
<blockquote>
<p>According to some political pundits, a person who is radical (R) is
electable (E) if he/she is conservative (C), but otherwise not electable.</p>
<p>a. Which of the following are correct representations of this assertion?<br/>
(i) <code>$R \land E \Leftrightarrow C$</code><br/>
(ii) <code>$R \Rightarrow (E \Leftrightarrow C)$</code><br/>
(iii) <code>$R \Rightarrow ((C \Rightarrow E) \lor \lnot E)$</code></p>
</blockquote>
<p>(i) Would mean that a conservative is only electable if they are radical
and electable, which must not be true. (ii) is a good representation:
If someone is radical, they have to be either both conservative and
electable or not conservative and not electable.</p>
<p>For (iii), if R=True, C=True and E=False, then the sentence is true,
but this goes against the earlier formulation: There are no unelectable
radical conservatives (in this hypothetical scenario).</p>
<blockquote>
<p>b. Which of the sentences in (a) can be expressed in Horn form?</p>
</blockquote>
<p>(i)</p>
<div>
$$(R \land E) \Leftrightarrow C \equiv \\
C \Rightarrow (R \land E) \land (R \land E) \Rightarrow C \equiv \\
\lnot C \lor (R \land E) \land \lnot (R \land E) \lor C \equiv \\
(\lnot C \lor R) \land (\lnot C \lor E) \land (\lnot R \lor \lnot E \lor C)$$
</div>
<p>This sentence can't be represented in Horn form, since it can't be
reduced down to only disjunctions of literals.</p>
<p>(ii)</p>
<div>
$$ R \Rightarrow (E \Leftrightarrow C) \equiv \\
\lnot R \lor (E \Rightarrow C \land C \Rightarrow E) \equiv \\
\lnot R \lor (\lnot E \lor C \land \lnot C \lor E) \equiv \\
(\lnot R \lor \lnot E \lor C) \land (\lnot R \lor \lnot C \lor E) \equiv \\
\lnot R \land (\lnot E \lor C) \land (\lnot C \lor E) $$
</div>
<p>Neither can this sentence.</p>
<p>(iii)</p>
<div>
$$ R \Rightarrow ((C \Rightarrow E) \lor \lnot E) \equiv \\
\lnot R \lor ((\lnot C \lor E) \lor \lnot E \equiv) \\
\lnot R \lor \lnot C \lor E \lor \lnot E \equiv \\
(R \land C \land E) \Rightarrow E \equiv \\
True$$
</div>
<p>This sentence can be represented in Horn form, and is also a tautology.</p>
<h2 id="Chapter_9"><a class="hanchor" href="#Chapter_9">Chapter 9</a></h2>
<h3 id="99"><a class="hanchor" href="#99">9.9</a></h3>
<blockquote>
<p>Suppose you are given the following axioms:</p>
<ol>
<li><code>$0 \le 3$</code>.</li>
<li><code>$ 7 \le 9$</code>.</li>
<li><code>$\forall x: x \le x$</code>.</li>
<li><code>$\forall x: x \le x+0$</code>.</li>
<li><code>$\forall x: x+0 \le x$</code>.</li>
<li><code>$\forall x, y: x+y \le y+x$</code>.</li>
<li><code>$\forall w, x, y, z: w \le y \land x \le z \Rightarrow w+x \le y+z$</code>.</li>
<li><code>$\forall x, y, z: x \le y \land y \le z \Rightarrow x \le z$</code>.</li>
</ol>
<p>a. Give a backward-chaining proof of the sentence <code>$7 \le 3 + 9$</code>. (Be
sure, of course, to use only the axioms given here, not anything else
you may know about arithmetic.) Show only the steps that leads [sic]
to success, not the irrelevant steps.</p>
</blockquote>
<ul>
<li>Proof: <code>$7 \le 3+9$</code>
<ul>
<li>Rule 8: <code>$\{7/x, 3+9/z\}$</code></li>
<li>Proof: <code>$7 \le y \land y \le 3+9$</code>
<ul>
<li>Substitute <code>$\{0+7/y\}$</code></li>
<li>Proof: <code>$7 \le 0+7$</code>
<ul>
<li>Rule 8: <code>$7 \le y \land y \le 0+7$</code></li>
<li>Substitute: <code>$\{y/7+0\}$</code></li>
<li>Proof: <code>$7+0 \le 0+7$</code>
<ul>
<li>Rule 6: <code>$7+0 \le 0+7$</code></li>
</ul></li>
<li>Proof: <code>$7 \le 7+0$</code>
<ul>
<li>Rule 4: <code>$7 \le 7+0$</code></li>
</ul></li>
</ul></li>
<li>Proof: <code>$0+7 \le 3+9$</code></li>
<li>Rule 7: <code>$\{0/w, 7/x, 3/y, 9/z\}$</code></li>
<li>Proof: <code>$0 \le 3 \land 7 \le 9$</code>:
<ul>
<li>Rule 1: <code>$0 \le 3$</code></li>
<li>Rule 2: <code>$7 \le 9$</code></li>
</ul></li>
</ul></li>
</ul></li>
</ul>
<blockquote>
<p>b. Give a forward-chaining proof of the sentence <code>$7 \le 3+9$</code>. Again,
show only the steps that lead to success.</p>
</blockquote>
<ul>
<li>Known: <code>$0 \le 3, 7 \le 9$</code></li>
<li>Rule 7: <code>$\{0/w, 7/x, 3/y, 9/z\}$</code></li>
<li>Known: <code>$0+7 \le 3+9$</code></li>
<li>Rule 7: <code>$\{x/7\}$</code></li>
<li>Known: <code>$7 \le 7+0$</code></li>
<li>Rule 6: <code>$\{7/x, 0/y\}$</code></li>
<li>Known: <code>$7+0 \le 0+7$</code></li>
<li>Rule 8: <code>$\{7/x, 7+0/y, 0+7/z\}$</code></li>
<li>Known: <code>$7 \le 0+7$</code></li>
<li>Rule 8: <code>$\{7/0, 0+7/y, 3+9/z$</code></li>
<li>Known: <code>$7 \le 3+9$</code></li>
</ul>
<!--
TODO
### 9.10
> A popular children's riddle is “Brothers and sisters have I none,
but that man's father is my father's son.” Use the rules of the family
domain (Section 8.3.2 on page 301) to show who that man is. You may
apply any of the inference methods described in this chapter. Why do
you think that this riddle is difficult?
Constants: `$I$`, referring to the speaker, `$T$` referring to "that man".
Variables: `$x, y, z$`.
Known facts: `$\lnot Sibling(x, I), Father(T)=Son(Father(I))$`
We don't know whether the speaker is male.
Let's say we have a hunch that it is the case that `$Father(T)=I$`
-->
<h2 id="Chapter_13"><a class="hanchor" href="#Chapter_13">Chapter 13</a></h2>
<h3 id="131"><a class="hanchor" href="#131">13.1</a></h3>
<blockquote>
<p>Show from first principile that <code>$P(a|b \land a) = 1$</code>.</p>
</blockquote>
<p>I'm not sure whether this counts as "from first principles", but</p>
<p><code>$P(a|b \land a)=\frac{P(a \land a \land b)}{P(a \land b)}=\frac{P(a \land b)}{P(a \land b)}=1$</code></p>
<p>is my solution.</p>
<h3 id="132"><a class="hanchor" href="#132">13.2</a></h3>
<blockquote>
<p>Using the axioms of probability, prove that any probability distribution
on a discrete random variable must sum to 1.</p>
</blockquote>
<p>We know that <code>$\sum_{\omega \in \Omega} P(\omega)=1$</code>.</p>
<p>Given a discrete random variable X (X is discrete (and therefore also
countable?)), and a probability distribution <code>$P: X \rightarrow [0;1]$</code>.</p>
<p>Then, setting <code>$\Omega=X$</code>, one can see that <code>$\sum_{x \in X} P(x)=1$</code>.</p>
<!--Possible problem: What about other variables & their distributions?
Conditional on those in joint, the result is still 1, but would be
worthwhile to write down.-->
<h3 id="133"><a class="hanchor" href="#133">13.3</a></h3>
<blockquote>
<p>For each of the following statements, either prove it is true or give
a counterexample.</p>
<p>a. If <code>$P(a|b,c)=P(b|a,c)$</code>, then <code>$P(a|c)=P(b|c)$</code></p>
</blockquote>
<div>
$$P(a|b,c)=P(b|a,c) \Leftrightarrow \\
\frac{P(a,b,c)}{P(b,c)}=\frac{P(a,b,c)}{P(a,c)} \Leftrightarrow \\
P(a,c)=P(b,c) \Leftrightarrow \\
\frac{P(a,c)}{P(c)}=\frac{P(b,c)}{P(c)} \Leftrightarrow \\
P(a|c)=P(b|c)$$
</div>
<p>True.</p>
<blockquote>
<p>b. If <code>$P(a|b,c)=P(a)$</code>, then <code>$P(b|c)=P(b)$</code></p>
</blockquote>
<p>False: If
<code>$P(a)=P(a|b,c)=P(a|\lnot b,c)=P(a|b, \lnot c)=P(a|\lnot b,\lnot c)=0.1$</code>
(<code>$P(\lnot a)$</code> elided for brevity), then still can b be dependent on c,
for example <code>$P(b|c)=0.2$</code>, <code>$P(\lnot b|c)=0.8$</code>, <code>$P(b|\lnot c)=0.3$</code>,
<code>$P(\lnot b|\lnot c)=0.7$</code>, and <code>$P(c)=P(\lnot c)=0.5$</code> (which would
make <code>$P(b)=\sum_{c \in C} P(b|c)*P(c)=0.5*0.2+0.5*0.3=0.25$</code> and
<code>$P(\lnot b)=\sum_{c \in C} P(\lnot b|c)*P(c)=0.5*0.8+0.5*0.7=0.75$</code>).</p>
<blockquote>
<p>c. If <code>$P(a|b)=P(a)$</code>, then <code>$P(a|b,c)=P(a|c)$</code></p>
</blockquote>
<p><code>$a$</code> and <code>$b$</code> are independent. However, this does not imply conditional
independence given <code>$c$</code>. E.g.:</p>
<p><code>$P(a)=0.5, P(b)=0.5, P(c|a, b)=1, P(c|\lnot a, \lnot b)=0, P(c|\lnot a, b)=1, P(c|a, \lnot b)=1$</code></p>
<p>So this is false.</p>
<!--
### 13.4
> Would it be rational for an agent to hold the three beliefs `$P(A)=0.4, P(B)=0.3$`,
and `$P(A \lor B)=0.5$`? If so, what range of probabilities
would be rational for the agent to hold for `$A \land B$`? Make up
a table like the one in Figure 13.2, and show how it supports your
argument about rationality. Then draw another version of the table where
`$P(A \lor B)=0.7$`. Explain why it is rational to have this probability,
even though the table shows one case that is a loss and three that just
break even. (*Hint*: what is Agent 1 commited to about the probability
of each of the four cases, especially the case that is a loss?)
It is rational for an agent to believe `$P(A)=0.4, P(B)=0.3$` and
`$P(A \lor B)=0.5$`, if
`$P(A \land B)=P(A)+P(B)-P(A \lor B)=0.4+0.3-0.5=0.2$`.
<table>
<thead>
<tr>
<td>Proposition</td>
<td>Belief</td>
</tr>
</thead>
<tbody>
<tr>
</tr>
</tbody>
</table>
-->
<h3 id="135"><a class="hanchor" href="#135">13.5</a></h3>
<blockquote>
<p>This question deals with the properties of possible worlds, defined
on page 488 as assignments to all random variables. We will work with
propositions that correspond to exactly one possible world because they
pin down the assignments of all the variables. In probability theory,
such propositions are called <strong>atomic events</strong>. For example, with Boolean
variables <code>$X_1, X_2, X_3$</code>, the proposition <code>$x_1 \land \lnot x_2 \land \lnot x_3$</code>
fixes the assignment of the variables,; in the language of
propositional logic, we would say it has exactly one model.</p>
<p>a. Prove, for the case of <code>$n$</code> Boolean variables, that any two distinct
atomic events are mutually exclusive; that is, their conjunction is
equivalent to <em>false</em>.</p>
</blockquote>
<p>Let <code>$s_1, s_2$</code> be two distinct atomic events. That means there exists at
least one <code>$x_i$</code> so that <code>$x_i$</code> is part of the conjunction in <code>$s_1$</code>
and <code>$\lnot x_i$</code> is part of the conjunction in <code>$s_2$</code>.</p>
<p>Then:</p>
<div>
$$s_1 \land s_2 = \\
s_1(1) \land \dots \land s_1(i-1) \land x_i \land s_1(i+1) \land \dots \land s_1(n) \land s_2(1) \land \dots \land s_2(i-1) \land \lnot x_i \land s_2(i+1) \land \dots \land s_2(n)=\\
s_1(1) \land \dots \land s_1(i-1) \land s_1(i+1) \land \dots \land s_1(n) \land s_2(1) \land \dots \land s_2(i-1) \land s_2(i+1) \land \dots \land s_2(n) \land x_i \land \lnot x_i=\\
s_1(1) \land \dots \land s_1(i-1) \land s_1(i+1) \land \dots \land s_1(n) \land s_2(1) \land \dots \land s_2(i-1) \land s_2(i+1) \land \dots \land s_2(n) \land false=\\
false$$
</div>
<blockquote>
<p>b. Prove that the disjunction of all possible atomic events is logically
equivalent to <em>true</em>.</p>
</blockquote>
<p>For every atomic event <code>$s$</code>, there is an atomic event
<code>$s'=\lnot s=\lnot s(1) \land \dots \lnot s(n)$</code>. Then the
disjunction of all atomic events contains <code>$s \lor s' \lor \dots=True$</code>.</p>
<blockquote>
<p>c. Prove that any proposition is logically equivalent to the disjunction
of the atomic events that entail its truth.</p>
</blockquote>
<p>Let <code>$\mathcal{A}$</code> be the set of <code>$n$</code> assignments that make the proposition
true. Then each assignment <code>$A_i \in \mathcal{A}$</code> corresponds to exactly
one atomic event <code>$a_i$</code> (e.g. assigning true to <code>$x_1$</code>, false to <code>$x_2$</code> and
false to <code>$x_3$</code> corresponds to <code>$x_1 \land \lnot x_2 \land \lnot x_2$</code>).
The set of these atomic events exactly entails the proposition.</p>
<p>One can then simply create the conjunction of sentences
<code>$\bigwedge_{i=1}^{n} a_i$</code> that is true only if we use an assignment
that makes the proposition true.</p>
<h3 id="136"><a class="hanchor" href="#136">13.6</a></h3>
<blockquote>
<p>Prove Equation (13.4) from Equations (13.1) and (13.2).</p>
</blockquote>
<p>More explicit: Prove <code>$P(a \lor b)= P(a)+P(b)-P(a \land b)$</code> from
<code>$0 \le P(ω) \le 1, \sum_{ω \in Ω} P(ω)=1$</code>.</p>
<p>Since <code>$a \lor b \Leftrightarrow ω \in a \cup b$</code> and <code>$\sum_{ω \in a \backslash b} P(ω) + \sum_{ω \in a \cap b} P(ω)=\sum_{ω \in a} P(ω)$</code>:</p>
<div>
$$P(a \lor b)=\\
\sum_{ω \in a \cup b} P(ω)=\\
\sum_{ω \in a \backslash b} P(ω) + \sum_{ω \in b \backslash a} P(ω) + \sum_{ω \in a \cap b} P(ω)=\\
\sum_{ω \in a \backslash b} P(ω) + \sum_{ω \in b \backslash a} P(ω) + \sum_{ω \in a \cap b} P(ω) + \sum_{ω \in a \cap b} P(ω) - \sum_{ω \in a \cap b} P(ω)=\\
\sum_{ω \in a} P(ω) + \sum_{ω \in b} P(ω) - \sum_{ω \in a \cap b} P(ω)=\\
P(a)+P(b)-P(a \land b)$$
</div>
<h2 id="Chapter_14"><a class="hanchor" href="#Chapter_14">Chapter 14</a></h2>
<h3 id="141"><a class="hanchor" href="#141">14.1</a></h3>
<blockquote>
<p>We have a bag of three biased coins a, b, and c with probabilities of
coming up heads of 20%, 60%, and 80%, respectively. One coin is drawn
randomly from the bag (with equal likelihood of drawing each of the
three coins), and then the coin is flipped three times to generate the
outcomes <code>$X_1$</code>, <code>$X_2$</code>, and <code>$X_3$</code>.</p>
<p>a. Draw the Bayesian network corresponding to this setup and define
the necessary CPTs.</p>
</blockquote>
<p><img alt="A Bayesian network for drawing the coin & throwing it thrice" src="./img/aima_solutions/14_1_bayesnet.png" title="A Bayesian network for drawing the coin & throwing it thrice. The first parent node contains the coin, the three independent children are the three throws."/></p>
<table>
<thead>
<tr>
<td>$Coin$</td>
<td>$P(Coin)$</td>
</tr>
</thead>
<tbody>
<tr>
<td>a</td>
<td>1/3</td>
</tr>
<tr>
<td>b</td>
<td>1/3</td>
</tr>
<tr>
<td>c</td>
<td>1/3</td>
</tr>
</tbody>
</table>
<p>The three conditional tables for <code>$X_1, X_2, X_3$</code> are very the same.</p>
<table>
<thead>
<tr>
<td>$Coin$</td>
<td>$P(\{X_1, X_2, X_3\}=Head)$</td>
</tr>
</thead>
<tbody>
<tr>
<td>a</td>
<td>0.2</td>
</tr>
<tr>
<td>b</td>
<td>0.6</td>
</tr>
<tr>
<td>c</td>
<td>0.8</td>
</tr>
</tbody>
</table>
<p>Furthermore, <code>$X_1, X_2, X_3$</code> are mutually conditionally independent
given <code>$Coin$</code>.</p>
<blockquote>
<p>b. Calculate which coin was most likely to have been drawn from the
bag if the observed flips come out heads twice and tails once.</p>
</blockquote>
<p><code>$C=\underset{coin \in \{a,b,c\}}{\hbox{argmax}} P(coin|H_1, H_2, T_3)$</code></p>
<div>
$$P(coin|H_1, H_2, T_3)=\\
\frac{P(H_1, H_2, T_3|coin)*P(coin)}{P(H_1, H_2, H_3)}=\\
\frac{P(H_1, H_2, T_3|coin)*P(coin)}{P(H_1|Coin)*P(H_2|Coin)*P(T_3|Coin)}=\\
\frac{P(H_1, H_2, T_3|coin)*P(coin)}{\sum_{v \in \{a,b,c\}}(P(H_1|v)*P(v))*\sum_{v \in \{a,b,c\}}(P(H_2|v)*P(v))*\sum_{v \in \{a,b,c\}}(P(T_3|v)*P(v))}=\\
\frac{P(H_1|coin)*P(H_2|coin)*P(T_3|coin)*P(coin)}{\sum_{v \in \{a,b,c\}}(P(H_1|v)*P(v))^2*\sum_{v \in \{a,b,c\}}(P(T_3|v)*P(v))}=\\
\frac{P(H_1|coin)*P(H_2|coin)*P(T_3|coin)*P(coin)}{(0.2*1/3+0.6*1/3+0.8*1/3)^2*(0.8*1/3+0.4*1/3+0.2*1/3)}=\\
\frac{P(H_1|coin)*P(H_2|coin)*P(T_3|coin)*P(coin)}{0.1327407}$$
</div>
<p>Now we plug in the values for <code>$coin$</code>:</p>
<div>
$$P(a|H_1, H_2, T_3)=\frac{P(H_1|a)*P(H_2|a)*P(T_3|a)*P(a)}{0.1327407}=\frac{0.2*0.2*0.8*1/3}{0.1327407}=0.0803571\\
P(b|H_1, H_2, T_3)=\frac{P(H_1|b)*P(H_2|b)*P(T_3|b)*P(b)}{0.1327407}=\frac{0.6*0.6*0.4*1/3}{0.1327407}=0.36160725384\\
P(c|H_1, H_2, T_3)=\frac{P(H_1|c)*P(H_2|c)*P(T_3|c)*P(c)}{0.1327407}=\frac{0.8*0.8*0.2*1/3}{0.1327407}=0.32142867$$
</div>
<p>Thus, I conclude that it is most likely that coin b was pulled out of
the bag.</p>
<p><em>Note</em>: the probabilities for <code>$P(coin|H_1, H_2, T_3)$</code> don't sum to
1. I'm not sure what's up with that, but it's a good indicator that I
have done something horribly wrong. Don't copy this solution.</p>
<h2 id="Chapter_15"><a class="hanchor" href="#Chapter_15">Chapter 15</a></h2>
<h3 id="1513"><a class="hanchor" href="#1513">15.13</a></h3>
<blockquote>
<p>A professor wants to know if students are getting enough sleep. Each
day, the professor observes whether the students sleep in class, and
whether they have red eyes. The professor has the following domain theory:</p>
<ul>
<li>The prior probability of getting enough sleep, with no observations, is 0.7.</li>
<li> The probability of getting enough sleep on night t is 0.8 given
that the student got enough sleep the previous night, and 0.3
if not.</li>
<li>The probability of having red eyes is 0.2 if the student got enough sleep, and 0.7 if not.</li>
<li>The probability of sleeping in class is 0.1 if the student got enough sleep, and 0.3 if not.</li>
</ul>
<p>Formulate this information as a dynamic Bayesian network that
the professor could use to filter or predict from a sequence of
observations. Then reformulate it as a hidden Markov model that has only
a single observation variable. Give the complete probability tables for
the model.</p>
</blockquote>
<p>There are three variables: <code>$E_t$</code> for getting enough sleep in night t,
<code>$S_t$</code> for sleeping in class on day t, and <code>$R_t$</code> for having red eyes
on day t.</p>
<p><img alt="Image of the resulting dynamic Bayesian network" src="./img/aima_solutions/15_3_bayesnet.png" title="The resulting dynamic Bayesian network, with E nodes in sequence, each parent of one R and one S node."/></p>
<p>The conditional probabilities tables for the dynamic Bayesian network are:</p>
<p><code>$P(E_{t+1}|E_t)$</code>:</p>
<table>
<thead>
<tr>
<td>$E_t$</td>
<td>$e_{t+1}$</td>
<td>$\lnot e_{t+1}$</td>
</tr>
</thead>
<tbody>
<tr>
<td>1</td>
<td>0.8</td>
<td>0.2</td>
</tr>
<tr>
<td>0</td>
<td>0.3</td>
<td>0.7</td>
</tr>
</tbody>
</table>
<p><code>$P(S_t|E_t)$</code>:</p>
<table>
<thead>
<tr>
<td>$E_t$</td>
<td>$s_t$</td>
<td>$\lnot s_t$</td>
</tr>
</thead>
<tbody>
<tr>
<td>1</td>
<td>0.1</td>
<td>0.9</td>
</tr>
<tr>
<td>0</td>
<td>0.3</td>
<td>0.7</td>
</tr>
</tbody>
</table>
<p><code>$P(R_t|E_t)$</code>:</p>
<table>
<thead>
<tr>
<td>$E_t$</td>
<td>$r_t$</td>
<td>$\lnot r_t$</td>
</tr>
</thead>
<tbody>
<tr>
<td>1</td>