CS50 Introduction to Artificial Intelligence with Python Lecture 3

第三讲的主题是Uncertainty,这里总结第三讲以及第三次作业。

课程地址:https://cs50.harvard.edu/ai/

备注:图片均来自课程课件。

这节课前面大部分内容是概率论的基本内容,这里略过,从贝叶斯网络开始回顾。

Bayesian Networks

贝叶斯网络是表示随机变量之间依赖性的数据结构,几个特点如下:

  • 有向图
  • 每个节点代表一个随机变量
  • 从$X$到$Y$的箭头表示$X$是$Y$的父节点
  • 每个节点$X$都有概率分布$\mathbf{P}(X | \text { Parents }(X))$

来看一个具体例子:

然后对上图分别指定条件分布即可构成贝叶斯网络。

Inference

  • 查询$\mathrm X$:要为其计算分布的变量
  • 证据变量$\mathrm E$:事件$\mathrm e$的观察变量
  • 隐藏变量$\mathrm Y$:无证据,没有被查询的变量。
  • 目标:计算$\mathbf{P}(\mathrm{X} | \mathbf{e})$

具体方式如下

Approximate Inference: Sampling

之前的方法是计算准确概率,下面介绍近似推断的方法——采样。采样的思路是根据条件概率分布进行采样,然后利用样本均值估计概率。

Hidden Markov Model

在HMM中有隐藏状态$\mathrm X_t$和观测值$\mathrm O_t$,两者有依赖关系,一个常见例子如下:

其中隐藏状态有马尔可夫性,但我们只能观测到观测状态:

HMM中的常见任务如下:

任务 描述
过滤 给定从开始到现在的观测值,计算当前状态的分布
预测 给定从开始到现在的观测值,计算未来状态的分布
平滑 给定从开始到现在的观测值,计算过去状态的分布
最可能的解释 给定从开始到现在的观测值,计算最可能的状态序列

Project

PageRank

此题注意问题介绍中有如下一段话即可

1
If page has no outgoing links, then transition_model should return a probability distribution that chooses randomly among all pages with equal probability. (In other words, if a page has no links, we can pretend it has links to all pages in the corpus, including itself.)

transition_model

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def transition_model(corpus, page, damping_factor):
"""
Return a probability distribution over which page to visit next,
given a current page.

With probability `damping_factor`, choose a link at random
linked to by `page`. With probability `1 - damping_factor`, choose
a link at random chosen from all pages in the corpus.
"""
n = len(corpus)
#计算概率
res = dict()
m = len(corpus[page])
for i in corpus:
if len(corpus[page]) != 0:
if i in corpus[page]:
res[i] = (1 - damping_factor) / n + damping_factor / m
else:
res[i] = (1 - damping_factor) / n
else:
res[i] = 1 / n

return res

sample_pagerank

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
def sample_pagerank(corpus, damping_factor, n):
"""
Return PageRank values for each page by sampling `n` pages
according to transition model, starting with a page at random.

Return a dictionary where keys are page names, and values are
their estimated PageRank value (a value between 0 and 1). All
PageRank values should sum to 1.
"""
#初始化
res = dict()
for i in corpus:
res[i] = 0
page = np.random.choice(list(corpus.keys()))
for i in range(n):
res[page] += 1
prob = transition_model(corpus, page, damping_factor)
key = list(prob.keys())
value = list(prob.values())
page = np.random.choice(key, p=value)

for i in corpus:
res[i] /= n

return res

iterate_pagerank

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
def iterate_pagerank(corpus, damping_factor):
"""
Return PageRank values for each page by iteratively updating
PageRank values until convergence.

Return a dictionary where keys are page names, and values are
their estimated PageRank value (a value between 0 and 1). All
PageRank values should sum to 1.
"""
#计算网页个数
numlinks = dict()
#反向边
corpus_reverse = dict()
for i in corpus:
corpus_reverse[i] = set()
#根据题目的解释
if (len(corpus[i]) == 0):
corpus[i] = set(corpus.keys())

for i in corpus:
for j in corpus[i]:
corpus_reverse[j].add(i)
numlinks[i] = len(corpus[i])

n = len(corpus)
#初始化
page = dict()
for i in corpus:
page[i] = 1 / n
while True:
newpage = dict()
for i in corpus:
newpage[i] = (1 - damping_factor) / n
for j in corpus_reverse[i]:
newpage[i] += damping_factor * page[j] / numlinks[j]
s = 0
flag = True
for i in corpus:
diff = abs(newpage[i] - page[i])
if diff > 0.001:
flag = False
page[i] = newpage[i]
s += page[i]

if flag:
break

return page

Heredity

对于没有复节点的节点,计算概率的方式较为简单,对于其他节点则要复杂一下,这里设计了两个辅助函数:

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
#原本为i个gene,生成j个gene的概率
#i=0,1,2, j=0,1
def get_prob(i, j):
if j != 0 and j != 1:
return 0
p = PROBS["mutation"]
if i == 0:
p1 = 1 - p
if j == 0:
return p1
else:
return 1 - p1
elif i == 1:
p1 = 0.5 * (1 - p) + 0.5 * p
if j == 0:
return p1
else:
return 1 - p1
else:
p1 = p
if j == 0:
return p1
else:
return 1- p1

def get_num(people, one_gene, two_genes, person):
zero_gene = set(people.keys()) - one_gene - two_genes
if person in zero_gene:
return 0
elif person in one_gene:
return 1
else:
return 2

其余部分实现如下

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
def joint_probability(people, one_gene, two_genes, have_trait):
"""
Compute and return a joint probability.

The probability returned should be the probability that
* everyone in set `one_gene` has one copy of the gene, and
* everyone in set `two_genes` has two copies of the gene, and
* everyone not in `one_gene` or `two_gene` does not have the gene, and
* everyone in set `have_trait` has the trait, and
* everyone not in set` have_trait` does not have the trait.
"""
prob = 1

for person in people:
#计算数量
n1 = get_num(people, one_gene, two_genes, person)
#trait
p = PROBS["trait"][n1][True]
if person not in have_trait:
p = 1 - p
prob *= p
#没有父节点
if people[person]['mother'] == None:
prob *= PROBS["gene"][n1]
else:
father = people[person]['father']
mother = people[person]['mother']
n2 = get_num(people, one_gene, two_genes, father)
n3 = get_num(people, one_gene, two_genes, mother)
p1 = 0
#穷举所有情况
for i in range(n1 + 1):
j = n1 - i
p1 += get_prob(n2, i) * get_prob(n3, j)
prob *= p1

return prob


def update(probabilities, one_gene, two_genes, have_trait, p):
"""
Add to `probabilities` a new joint probability `p`.
Each person should have their "gene" and "trait" distributions updated.
Which value for each distribution is updated depends on whether
the person is in `have_gene` and `have_trait`, respectively.
"""
for person in probabilities:
n = get_num(probabilities, one_gene, two_genes, person)
probabilities[person]["gene"][n] += p
probabilities[person]["trait"][person in have_trait] += p


def normalize(probabilities):
"""
Update `probabilities` such that each probability distribution
is normalized (i.e., sums to 1, with relative proportions the same).
"""
for person in probabilities:
s = 0
for i in probabilities[person]["gene"]:
s += probabilities[person]["gene"][i]
for i in probabilities[person]["gene"]:
probabilities[person]["gene"][i] /= s

s = 0
for i in probabilities[person]["trait"]:
s += probabilities[person]["trait"][i]
for i in probabilities[person]["trait"]:
probabilities[person]["trait"][i] /= s

本文标题:CS50 Introduction to Artificial Intelligence with Python Lecture 3

文章作者:Doraemonzzz

发布时间:2020年04月24日 - 08:50:28

最后更新:2020年04月30日 - 14:34:03

原始链接:http://doraemonzzz.com/2020/04/24/CS50 Introduction to Artificial Intelligence with Python Lecture 3/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。