Doraemonzzz

课程主页： https://www.davidsilver.uk/teaching/ 这里回顾David silver 强化学习 Lecture2 的课程内容，这一讲简单介绍了马尔可夫决策过程。 马尔可夫过程马尔可夫性定义 状态$S_t$有马尔可夫性当且仅当 \mathbb{P}\left[S_{t+1} | S_{t}\right]=\mathbb{P}\left[S_{t+1} | S_{1}, \ldots, S_{t}\right] 状态从历史中捕获所有相关信息 一旦知道状态后，历史可以被丢弃 状态是未来的充分统计量 状态转移矩阵对于马尔可夫状态$s$和后继状态$s’$，状态转移概率被定义为 \mathcal{P}_{s s^{\prime}}=\mathbb{P}\left[S_{t+1}=s^{\prime} | S_{t}=s\right]状态转移矩阵$\mathcal P$定义了从所有状态$s$到后继状态$s’$的概率， \mathcal{P}=\left[\begin{array}{ccc}{\mathcal{P}_{11}} & {\cdots} & {\ ...

课程主页： https://www.davidsilver.uk/teaching/ 这里回顾David silver 强化学习 Lecture 1的课程内容，这一讲简单介绍了强化学习。 强化学习的特点强化学习是机器学习的一个分支，它和监督学习以及非监督学习的关系如下： 强化学习两个重要元素为智能体和环境，它和机器学习的其他分支最明显的区别为： 没有监督，只有奖励信号 反馈是延迟的，不是即时的 时间很重要（即数据为序列，非独立同分布的） 智能体的动作影响其收到的后续数据 强化学习问题奖励 奖励$R_t$是标量反馈信号 表示智能体在步骤$t$的表现 智能体的工作是使累积奖励最大化 强化学习基于奖励假设，下面给出正式定义： 定义（奖励假设） 所有目标都可以通过累积奖励的期望最大化来描述。 序列决策 目标：选择可最大化未来总回报的行动 行动可能会带来长期结果 奖励可能会延迟 牺牲即时奖励以获得更多长期奖励可能更好 环境环境是强化学习的一个重要概念，其和智能体的交互关系可以用下图表示： 在每个步骤$t$，智能体： 执行动作$A_t$ 接受观测值$O_t$ 收到标量奖励$R_t$ ...

课程主页： http://web.stanford.edu/class/cs234/index.html 由于实习的原因，需要补充RL方面的知识，目前找了两份资料，一个David Silver的课程，另一个是CS234，这部分是对CS234的整理，第一讲的主题是Introduction to RL。 序列决策过程考虑序列决策过程，其模式如下 在每个时间戳$t$： 智能体采取行动$a_t$ 环境根据$a_t$进行更新，给出观测值$o_t$和奖励$r_t$ 智能体得到观测值$o_t$和奖励$r_t$ 由此不难得到历史$h_{t}=\left(a_{1}, o_{1}, r_{1}, \ldots, a_{t}, o_{t}, r_{t}\right)$ 智能体根据历史选择行动 状态是决定下一步会发生什么的信息：$s_t= f(h_t)$ 马尔可夫假设状态$s_t$具有马尔可夫性当且仅当： p\left(s_{t+1} | s_{t}, a_{t}\right)=p\left(s_{t+1} | h_{t}, a_{t}\right)即状态信息是历史的充分统计量。 实际中 ...

这次回顾第四周的内容。 课程主页：https://www.coursera.org/learn/analysis-of-algorithms Exercise4.9If $\alpha<\beta,$ show that $\alpha^{N}$ is exponentially small relative to $\beta^{N}$. For $\beta=1.2$ and $\alpha=1.1,$ find the absolute and relative errors when $\alpha^{N}+\beta^{N}$ is approximated by $\beta^{N},$ for $N=10$ and $N=100 .$ 解：因为当$N$充分大时，对于任意$M$，下式成立 \left(\frac{\alpha}{ \beta} \right)^N

这次回顾第三周的内容。 课程主页：https://www.coursera.org/learn/analysis-of-algorithms Exercise3.20Solve the recurrence $a_{n}=3 a_{n-1}-3 a_{n-2}+a_{n-3} \text { for } n>2$ with $a_0=a_1=0$ and $a_2=1$. 首先对原式进行改写： a_{n}=3 a_{n-1}-3 a_{n-2}+a_{n-3} +\delta_{n2}那么 \begin{aligned} a_nz^n &= 3 a_{n-1}z^n -3 a_{n-2}z^n +a_{n-3} z^n +\delta_{n2}z^n \\ A(z)&= 3zA(z)-3z^2 A(z) +z^3A(z) +z^2\\ A(z) &=\frac{z^2}{ 1-3z+3z^2 -z^3} =\frac{z^2}{(1-z)^3}\\ a_n &=\binom n2 =\frac{n(n-1)}{2} \end{aligned}3.28Find an ex ...

这次回顾第二周的内容。 课程主页：https://www.coursera.org/learn/analysis-of-algorithms Exercise2.17Solve the recurrence $A_{N}=A_{N-1}-\frac{2 A_{N-1}}{N}+2\left(1-\frac{2 A_{N-1}}{N}\right) \quad \text { for } N>0 \text { with } A_{0}=0$. This recurrence describes the following random process: A set of $N$ elements collect into “2-nodes” and “3-nodes.” At each step each 2-node is likely to turn into a 3-node with probability $2/N$ and each 3-node is likely to turn into two 2-nodes with probability $3/N$ Wh ...

这次回顾Course2 week3的算法。 课程地址：https://www.coursera.org/specializations/algorithms Heapclass Heap(): def __init__(self, Type): ''' type定义堆类型，x=1表示最小堆, x=0表示最大堆 ''' #堆的索引从1开始，堆守存放一个无用的元素 self.heap = [-1] self.len = 0 #type定义堆类型，x=1表示最小堆, x=0表示最大堆 self.type = Type def insert(self, x): ''' 插入 ''' #进入数组 self.heap.append(x) #更新长度 self.len += 1 #索引 i = self. ...

课程主页：https://see.stanford.edu/Course/EE364A 这次回顾凸优化Homework 3。 3.42考虑下水平集 S_0=\{ x |W(x) \le T_0 \}即 \forall x \in S_0, \left|x_{1} f_{1}(t)+\cdots+x_{n} f_{n}(t)-f_{0}(t)\right| \le \epsilon现在$\forall x, y\in S_0, 0\le \alpha \le 1$，考虑 z =\alpha x +(1-\alpha) y那么 \begin{aligned} \left|z_{1} f_{1}(t)+\cdots+z_{n} f_{n}(t)-f_{0}(t)\right| &= \left|\left(\alpha x +(1-\alpha) y\right)_{1} f_{1}(t)+\cdots+ \left(\alpha x +(1-\alpha) y\right)_{n} f_{n}(t)-f_{0}(t)\right|\\ &\le \alpha \left|x_{1 ...

这次回顾Course2 week2的算法。 课程地址：https://www.coursera.org/specializations/algorithms Dijkstra#include <iostream> #include <cstdio> #include <algorithm> #include <vector> #include <cstring> #include <sstream> using namespace std; const int N = 1e6; const int INFTY = 1e9; //定义图 vector <int> G[N]; //定义边长 vector <int> G1[N]; //节点数量 int n = 1; //判断是否访问过 int flag[N]; //距离数组 int dist[N]; int Find_min(){ int index = -1; int min_dist = INFTY; for (int i = 1; i <= ...

这次回顾Course2 week1的算法。 课程地址：https://www.coursera.org/specializations/algorithms BFS#include <cstdio> #include <queue> #include <vector> #include <cstring> using namespace std; const int N = 1e6; //定义图 vector <int> G[N]; //节点数量 int n = 1; //判断是否访问过 int flag[N]; //存储结果 vector <int> res; void BFS(vector <int> Graph[], int i){ //初始化栈 queue <int> Q; Q.push(i); flag[i] = 1; while (!Q.empty()){ int u = Q.front(); res.push_back(u); ...

这一部分将带来Course1理论习题的实现。 思考题1现在有$n$个元素且大小不相同的无序数组，$n$为$2$的幂，给出一个最多用$n+\log_2n-2$次比较的算法来找出第二大的元素。 算法伪代码：传送门 import numpy as np def Find_second_largest(array): n = len(array) #构造Hash，值为和键比较过且小于键的元素 mp = dict() for i in range(n): mp[i] = [] #索引集合 index = range(n) #比较次数 Cnt = 0 while (len(index) != 1): new_index, cnt = Compare(array, index, mp) index = new_index[:] Cnt += cnt #和最大值比较过的元素 index1 = mp[index[0]] ...

这次回顾第四周的算法。 课程地址：https://www.coursera.org/specializations/algorithms Randomized Selectionimport numpy as np def Exchange(A, i, j): #交换元素的值 p = A[i] A[i] = A[j] A[j] = p def Partion(A, l, r): #随机选择 index = np.random.randint(l, r + 1) Exchange(A, index, l) #选择主元 p = A[l] i = l + 1 for j in range(l + 1, r + 1): if (A[j] < p): Exchange(A, i, j) i += 1 Exchange(A, l, i - 1) return i - 1 def Randomized_ ...