24/11/14 算法笔记＜强化学习＞马尔可夫

一. MDP

马尔可夫决策过程（Markov Decision Process, MDP）：
- 马尔可夫决策过程是马尔可夫链的扩展，它引入了决策的概念。在MDP中，每个状态都对应一个或多个动作，而动作会影响下一个状态的转移概率和获得的奖励。
- MDP由四个主要元素组成：状态空间、动作空间、转移概率和奖励函数。状态空间定义了所有可能的状态，动作空间定义了在每个状态下可执行的动作，转移概率描述了执行某个动作后转移到另一个状态的概率，奖励函数则定义了在特定状态下执行特定动作后获得的即时奖励。
- 在机器学习中，MDP常用于解决强化学习问题，即智能体（agent）通过与环境的交互来学习最优策略，以最大化长期累积奖励。

MDP由以下几个基本元素组成：

状态（S）：智能体可以处于的状态集合。
动作（A）：智能体在每个状态下可以执行的动作集合。
转移概率（P）：描述了在给定状态下执行某个动作后转移到另一个状态的概率。
回报函数（R）：智能体在执行动作后从环境中获得的即时回报。
折扣因子（γ）：用于计算累积回报的折扣因子，它决定了未来回报相对于即时回报的重要性。

MDP的目标是找到一个策略（π），该策略可以最大化智能体的期望累积回报。策略可以是确定性的，也可以是随机性的。在确定性策略中，每个状态都映射到一个确定的动作；而在随机性策略中，每个状态都指定了在该状态下选择每个动作的概率。

MDP的求解方法主要分为两大类：

值函数算法：这类算法通过迭代地改进状态值函数或动作值函数来寻找最优策略。主要的方法包括动态规划（包括策略迭代和值迭代）和时序差分学习（TD学习）。动态规划方法要求环境模型是已知的，即状态转移概率和回报函数是已知的。而TD学习则不需要环境模型，可以通过与环境的交互来学习。
策略搜索算法：这类算法直接在策略空间中搜索最优策略。常见的策略搜索算法包括REINFORCE算法和演员-评论员算法（Actor-Critic Algorithm）。REINFORCE算法通过随机梯度上升来优化策略函数的参数，而演员-评论员算法结合了策略搜索和TD学习，其中“演员”负责执行策略，“评论员”负责评估策略。

这是一个使用Python实现的MDP示例，包括计算状态价值的函数。

import numpy as np

np.random.seed(0)
P = [
    [0.9, 0.1, 0.0, 0.0, 0.0, 0.0],
    [0.5, 0.0, 0.5, 0.0, 0.0, 0.0],
    [0.0, 0.0, 0.0, 0.6, 0.0, 0.4],
    [0.0, 0.0, 0.0, 0.0, 0.3, 0.7],
    [0.0, 0.2, 0.3, 0.5, 0.0, 0.0],
    [0.0, 0.0, 0.0, 0.0, 0.0, 1.0]
]
P = np.array(P)
rewards = [-1, -2, -2, 10, 1, 0]
gamma = 0.5

def compute_return(start, chain, gamma):
    G = 0
    for i in reversed(range(start, len(chain))):
        G = gamma * G + rewards[chain[i] - 1]
    return G

def compute(P, rewards, gamma, states_num):
    rewards = np.array(rewards).reshape((-1, 1))  # 将 rewards 改写为列向量
    value = np.dot(np.linalg.inv(np.eye(states_num, states_num) - gamma * P), rewards)
    return value

def compute_return_sample():
    chain = [1, 2, 3, 6]
    start = 0
    G = compute_return(start, chain, gamma)
    print('计算回报为：%s' % G)

def compute_value_sample():
    V = compute(P, rewards, gamma, 6)
    print("马尔可夫奖励过程中每个状态的价值分别为：\n", V)

compute_value_sample()

让我们分析每段代码

1.随机数种子和状态转移概率矩阵

np.random.seed(0)
P = [
    [0.9, 0.1, 0.0, 0.0, 0.0, 0.0],
    [0.5, 0.0, 0.5, 0.0, 0.0, 0.0],
    [0.0, 0.0, 0.0, 0.6, 0.0, 0.4],
    [0.0, 0.0, 0.0, 0.0, 0.3, 0.7],
    [0.0, 0.2, 0.3, 0.5, 0.0, 0.0],
    [0.0, 0.0, 0.0, 0.0, 0.0, 1.0]
]
P = np.array(P)

设置随机数种子np.random.seed(0)以确保结果的可重复性。
定义一个状态转移概率矩阵P，其中P[i][j]表示从状态i转移到状态j的概率。
将P转换为NumPy数组以便于后续计算。

2.奖励列表和折扣因子

rewards = [-1, -2, -2, 10, 1, 0]
gamma = 0.5

定义一个奖励列表rewards，其中rewards[i]表示在状态i+1的奖励。
定义折扣因子gamma，它用于计算未来奖励的现值。

3.计算回报的函数

def compute_return(start, chain, gamma):
    G = 0
    for i in reversed(range(start, len(chain))): #遍历一个从 start 到 len(chain) - 1 的整数序列，并且这个序列是反向的。
        G = gamma * G + rewards[chain[i] - 1]
    return G

定义一个函数compute_return，用于计算从特定状态开始的回报序列。
通过遍历状态链chain，从后向前计算回报G，使用公式G = gamma * G + reward。

4.计算状态价值的函数

def compute(P, rewards, gamma, states_num):
    rewards = np.array(rewards).reshape((-1, 1))  # 将 rewards 改写为列向量
    value = np.dot(np.linalg.inv(np.eye(states_num, states_num) - gamma * P), rewards)
    return value

定义一个函数compute，用于计算马尔可夫奖励过程中每个状态的价值。
将rewards转换为列向量。
使用公式value = (I - gamma * P)^-1 * rewards计算状态价值，其中I是单位矩阵，gamma * P是折扣后的状态转移概率矩阵。

5.计算回报的示例

def compute_return_sample():
    chain = [1, 2, 3, 6]  #状态转移序列
    start = 0
    G = compute_return(start, chain, gamma)
    print('计算回报为：%s' % G)

6.计算状态价值的示例

def compute_value_sample():
    V = compute(P, rewards, gamma, 6)
    print("马尔可夫奖励过程中每个状态的价值分别为：\n", V)

定义一个函数compute_value_sample，用于演示如何计算马尔可夫奖励过程中每个状态的价值。
使用compute函数计算状态价值，并打印结果。

这段代码展示了如何使用状态转移概率矩阵、奖励列表和折扣因子来计算马尔可夫奖励过程中的状态价值。通过compute_return和compute函数，我们可以分别计算特定状态链的回报和所有状态的价值。

二：HMM

隐马尔可夫模型（HMM）：是马尔可夫链的扩展，用于描述一个含有隐含未知参数的马尔可夫过程。在HMM中，我们观察到的是一系列可以观测的状态，但这些状态是由一系列隐藏的状态生成的。HMM在语音识别、自然语言处理等领域有广泛应用

这是一个使用Python实现的简单HMM示例，包括前向算法、维特比算法和Baum-Welch算法的实现

import numpy as np

# 初始化参数
states = ['Healthy', 'Fever']
observations = ['Dizzy', 'Cold', 'Normal']
start_prob = np.array([0.6, 0.4])
trans_prob = np.array([[0.7, 0.3],
                       [0.4, 0.6]])
emission_prob = np.array([[0.1, 0.4, 0.5],
                          [0.6, 0.3, 0.1]])

# 前向算法
def forward(obs_seq, start_prob, trans_prob, emission_prob): 

#states 和 observations 分别定义了状态集合和观测集合。
start_prob 是初始状态概率分布。
trans_prob 是状态转移概率矩阵。
emission_prob 是观测概率矩阵，表示在给定状态下观测到特定观测值的概率。

    N = len(states)
    T = len(obs_seq)
    alpha = np.zeros((T, N)) #用于存储在每个时间点 t 处于每个状态 i 的概率
    alpha[0, :] = start_prob * emission_prob[:, obs_seq[0]]
    for t in range(1, T):
        for j in range(N):
        #算在时间 t 时处于状态 j 的概率。这个概率是之前所有状态转移到状态 j 的概率之和，乘以在状态 j 下观测到当前观测值的概率。
            alpha[t, j] = np.sum(alpha[t-1, :] * trans_prob[:, j]) * emission_prob[j, obs_seq[t]]
    return np.sum(alpha[-1, :])


# 维特比算法
def viterbi(obs_seq, start_prob, trans_prob, emission_prob):
    N = len(states)
    T = len(obs_seq)
    delta = np.zeros((T, N)) #一个二维数组，用于存储在每个时间点 t 处于每个状态 j 的最大概率。
    psi = np.zeros((T, N), dtype=int) #一个二维数组，用于记录在每个时间点 t 达到状态 j 的最大概率的前一个状态。
#初始化第一个时间点的概率
    delta[0, :] = start_prob * emission_prob[:, obs_seq[0]]

#递归计算最优路径：
    for t in range(1, T):
        for j in range(N):
            delta[t, j] = np.max(delta[t-1, :] * trans_prob[:, j]) * emission_prob[j, obs_seq[t]]
            psi[t, j] = np.argmax(delta[t-1, :] * trans_prob[:, j]) #记录达到这个最大概率的前一个状态。

    #回溯找到最优路径：
path = np.zeros(T, dtype=int)
    path[-1] = np.argmax(delta[-1, :])
    for t in range(T-2, -1, -1):
        path[t] = psi[t+1, path[t+1]]
    return path


# Baum-Welch算法
def baum_welch(obs_seq, N, M, max_iter=100):
    T = len(obs_seq)
    a = np.random.rand(N, N)
    a = a / a.sum(axis=1, keepdims=True)
    b = np.random.rand(N, M)
    b = b / b.sum(axis=1, keepdims=True)
    pi = np.random.rand(N)
    pi = pi / pi.sum()
    for _ in range(max_iter):
        alpha = np.zeros((T, N))
        alpha[0, :] = pi * b[:, obs_seq[0]]
        for t in range(1, T):
            for j in range(N):
                alpha[t, j] = np.sum(alpha[t-1, :] * a[:, j]) * b[j, obs_seq[t]]
        beta = np.zeros((T, N))
        beta[-1, :] = 1
        for t in range(T-2, -1, -1):
            for i in range(N):
            #计算在时间 t 时处于状态 i 的后向概率。
                beta[t, i] = np.sum(beta[t+1, :] * a[i, :] * b[:, obs_seq[t+1]])
        xi = np.zeros((T-1, N, N))
        for t in range(T-1):
            denom = np.sum(alpha[t, :] * np.sum(a * b[:, obs_seq[t+1]].T * beta[t+1, :], axis=1))
            for i in range(N):
                numer = alpha[t, i] * a[i, :] * b[:, obs_seq[t+1]].T * beta[t+1, :]
                xi[t, i, :] = numer / denom

1. 前向算法（Forward Algorithm）

前向算法用于计算给定观测序列出现的概率。

这个概率是在模型参数（状态转移概率和观测概率）已知的情况下，观测序列发生的可能性。

2.维特比算法（Viterbi Algorithm）

维特比算法用于找到最可能产生观测序列的状态序列。

这个算法的核心思想是，通过递归地寻找最优路径，来确定在每个时间点最有可能的状态。

3.Baum-Welch算法（Baum-Welch Algorithm）

Baum-Welch算法是HMM的期望最大化（EM）算法，用于在给定观测序列的情况下，估计模型参数（状态转移概率和观测概率）。

通过迭代计算前向概率、后向概率和状态转移期望概率，来更新和优化隐马尔可夫模型的参数，直到收敛或达到最大迭代次数。

三：MC

马尔科夫链（MC)

马尔可夫链（Markov Chain）是一种随机过程，它的特点是无记忆性，即未来的状态只依赖于当前状态，而与之前的历史状态无关。这种性质也被称为马尔可夫性质。马尔可夫链在数学、物理、经济学、计算机科学、信息论以及生物学等多个领域都有广泛的应用。

基本组成部分

状态空间（State Space）：所有可能状态的集合。例如，天气可以是“晴天”、“多云”、“雨天”，这些就是状态空间中的元素。
状态（State）：系统在某一特定时间点的情况。在上述天气的例子中，某一天的天气就是一个状态。
转移概率（Transition Probabilities）：从一个状态转移到另一个状态的概率。这些概率通常用转移概率矩阵来表示。

转移概率矩阵

转移概率矩阵是一个方阵，其中第 i 行第 j 列的元素表示从状态 i 转移到状态 j 的概率。这个矩阵的行和为1，因为系统在下一个时间点必须转移到某个状态。

马尔可夫链的性质

无记忆性（Memorylessness）：未来的状态只依赖于当前状态，而与之前的状态无关。
遍历性（Ergodicity）：如果一个马尔可夫链是遍历的，那么无论从哪个状态开始，最终都能达到任何其他状态，并且长期行为不依赖于初始状态。
稳态分布（Stationary Distribution）：如果一个马尔可夫链有一个稳态分布，那么无论初始状态如何，经过足够多的转移后，系统状态的分布将趋于这个稳态分布。

这是一个使用Python实现的简单马尔科夫链示例，包括状态转移矩阵和初始分布的定义。

import numpy as np
#定义了一个 3x3 的转移概率矩阵。这个矩阵的每一行的和应该等于 1，表示从任一状态出发，转移到其他状态的概率之和为 1。
matrix = np.matrix([[0.6, 0.2, 0.2],
                    [0.5, 0.2, 0.3],
                    [0.2, 0.4, 0.4]])
#定义了一个初始状态分布向量，表示系统开始时处于三个状态的概率分布。这个向量的行和应该等于 1。
vector1 = np.matrix([[0.3, 0.4, 0.3]])
for i in range(50):
    vector1 = vector1 * matrix
    print('第{}轮'.format(i+1))
    print(vector1)