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
此题注意问题介绍中有如下一段话即可
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
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 ressample_pagerank
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 resiterate_pagerank
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 pageHeredity
对于没有复节点的节点，计算概率的方式较为简单，对于其他节点则要复杂一下，这里设计了两个辅助函数：
#原本为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其余部分实现如下
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本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Doraemonzzz！
相关推荐
评论
ValineLivere