写在前面

• 支持向量：两类别距离决策边界最近且相等的点。
• SVM目的：使得两个类别的SV间的距离最小。即最大化Margin间的距离。
• SVM考虑当前样本同时，又考虑到未来可能出现的样本，即使找到的决策边界尽量有强的泛化能力。
• 经过数学推到，可以将问题转化为最优化问题。如同其他参数学习算法。
• 其他机器学习算法一般是全局最优化问题，而SVM是有条件的最优化问题。
• 有条件的最优化问题使用拉格朗日算子求解。
• KKT条件
• Hard Margin要严格满足两个Margin见没有没有任何样本点。这由该最优化问题的条件决定。
• Soft Margin允许两个Margin之间存在样本点，即有容错的能力。相应的模型条件与目标都会体现该容错能力。
• L1正则；L2正则
• Hinge损失函数，Exponential Loss，Logistic Loss，是常用的损失函数，由好的数学性质。
• 惩罚项表达了容错空间，不能太大。
• 目标表达式中的C，目的是平衡前后两部分的比例。
• 此处C（正则化惩罚系数）与其他ML算法C含义不同，但是可以相同地解读。且C越大，越接近Hard Margin。
• SVM中涉及距离，所以要对数据进行标准化处理。否则当不同维数的特征尺度不同时，影响模型性能。

1. 数据

有二分类样本：

1
2
3
4
5
6
7
8

iris = datasets.load_iris()

x = iris.data    # 150 x 4
y = iris.target  # 150

# 二分类模型
x = x[y < 2, :2]  # 100 x 2
y = y[y < 2]     # 100

2. 首先标准化处理：

1
2
3
4
5

from sklearn.preprocessing import StandardScaler

stand = StandardScaler()
stand.fit(x)
x_standard = stand.transform(x)

得到标准化后的x_standard。

为了说明问题，使用所有数据fit，使用原来数据predict。

3. 当C取很大值时，如C=1e9：

1
2
3

svc = LinearSVC(C=1e9)
svc.fit(x_standard, y)
y_predict = svc.predict(x_standard)

查看模型所学，w和b：

1
2

print(svc.coef_)       # w [[ 4.03242779 -2.49296705]] 
print(svc.intercept_)  # b [ 0.95365901]

绘出决策边界， 及两个Margin：

1
2
3
4

plot_svc_decision_boundary(svc, axis=[-3, 3, -3, 3])
plt.scatter(x_standard[y_predict==0,0], x_standard[y_predict==0,1])
plt.scatter(x_standard[y_predict==1,0], x_standard[y_predict==1,1])
plt.show()

如图：

4. 当C取很小值时，如C=0.05：

1
2
3

svc2 = LinearSVC(C=0.005)
svc2.fit(x_standard, y)
y_y_predict = svc2.predict(x_standard)

查看模型所学，w&b：

1
2

print(svc2.coef_)       # w [[ 0.33360588 -0.30904355]]
print(svc2.intercept_)  # b [  3.81794231e-08]

绘出决策边界，及两个Margin：

1
2
3
4

plot_svc_decision_boundary(svc2, axis=[-3, 3, -3, 3])
plt.scatter(x_standard[y_predict==0,0], x_standard[y_predict==0,1])
plt.scatter(x_standard[y_predict==1,0], x_standard[y_predict==1,1])
plt.show()

如图：

当C太小时，容错空间太大，以至于大量明显分错的点也被模型认为是允许的。

这是当只指明C后，模型的参数：

1
2
3
4

LinearSVC(C=1000000000.0, class_weight=None, dual=True, f   it_intercept=True,
     intercept_scaling=1, loss='squared_hinge', max_iter=1000,
     multi_class='ovr', penalty='l2', random_state=None, tol=0.0001,
     verbose=0)

可以看出，使用的是hinge损失函数，L2正则化，ovr…等其他设置。

附件

绘出决策边界，及两个Margin的函数：

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

# show margins and boundary:
def plot_svc_decision_boundary(model, axis):
    x0, x1 = np.meshgrid(
        np.linspace(axis[0], axis[1], int((axis[1] - axis[0]) * 100)).reshape(-1, 1),
        np.linspace(axis[2], axis[3], int((axis[3] - axis[2]) * 100)).reshape(-1, 1),
    )
    X_new = np.c_[x0.ravel(), x1.ravel()]

    y_predict = model.predict(X_new)
    zz = y_predict.reshape(x0.shape)

    from matplotlib.colors import ListedColormap
    custom_cmap = ListedColormap(['#EF9A9A', '#FFF59D', '#90CAF9'])

    plt.contourf(x0, x1, zz, linewidth=5, cmap=custom_cmap)

    # margin lines:
    w = model.coef_[0]
    b = model.intercept_[0]

    # w0*x0 + w1*x1 + b = 0
    # => x1 = -w0/w1 * x0 - b/w1
    plot_x = np.linspace(axis[0], axis[1], 200)
    # # w0*x0 + w1*x1 + b = 1
    above_y = -w[0] / w[1] * plot_x - b / w[1] + (1 / w[1])
    # # w0*x0 + w1*x1 + b = -1
    below_y = -w[0] / w[1] * plot_x - b / w[1] - (1 / w[1])

    # two boolean vectors: set the length of lines
    above_index = (above_y >= axis[2]) & (above_y <= axis[3])
    below_index = (below_y >= axis[2]) & (below_y <= axis[3])
    plt.plot(plot_x[above_index], above_y[above_index], color='black')
    plt.plot(plot_x[below_index], below_y[below_index], color='black')

226,112,589

写在前面：

• 别忘了递归终止条件。
• 明确递归函数的定义，并确保实现中函数保持定义不变。
• 理解问题。分析出递归结构。
• 大脑不适应递归，像盗梦空间，你需要跳进跳出。一层一层跳入，到底，再一层一层跳出。令人恍惚的是每一层的变量都长一样！
• 用彩色笔画递归树，不同颜色表示不同层，你就不懵了。
• 除了多见类似的问题，训练大脑。目前找不出其他方法让大脑适应递归。
• 深度优先遍历，回朔，都是递归。
• 递归函数占用额外空间，调用递归函数需要额外开销。
• 由于二叉树天然具有递归性，解决问题时可以从树中拿出一个合适大小的子树，来构建出初步代码。
• 大多问题与二叉树的4种常见的遍历方法有关。
• 一个模式：移动控制+结点操作

#226 Invert Binary Tree

• 描述：

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

  Input: 4 / \ 2 7 / \ / \ 1 3 6 9 Output: 4 / \ 7 2 / \ / \ 9 6 3 1

• 思路

  递归树：

  

  要想实现问题描述的Invert，就需要从下往上Swap。具体说：
  先执行灰三角A，swap(空，空)；执行灰三角B，swap(空，空)；执行绿三角，swap(9子树, 6子树)；
  先执行灰三角C，swap(空，空)；执行灰三角D，swap(空，空)；执行红三角，swap(3子树, 1子树)；
  最后执行黄三角，swap(2子树, 7子树)
  结束。

• 代码实现：

  1 2 3 4 5 6 7 8 9 10 11

  // 定义：交换以root为跟的左右子树，返回交换后的root。 TreeNode* invertTree(TreeNode* root){ if (!root) return NULL; invertTree(root->left); invertTree(root->right); swap(root->left, root->right); return root; }

  这个过程其实是Binary Tree的后续遍历：

  1 2 3 4 5 6 7 8 9 10 11

  // 定义：打印输出root的值。 void postOrder(TreeNode* root){ if (!root) return NULL; postOrder(root->left); postOrder(root->right); cout<<root->val<<endl; return; }

  除了返回值，唯一的不同是前者执行交换root的左右子树，后者执行打印root->val。本质一样：后续遍历。

相似问题：#337 #508

#112 Path Sum

描述：

1
2
3
4
5
6
7
8
9
Given the below binary tree and sum = 26,

   5
  / \
 4   8
/   / \
11  13  4
return true,
as there exist a root-to-leaf path 5->8->13 which sum is 26.

• 思路

  两种思路，先序遍历，保存所有root-to-leaf的路径值，后搜索。见这里，效率低。

  另一种思路，递归树：

  

  执行过程，即是先序遍历，每“跳进”一个新的子树，就更新sum值。最终可以找到sum:13==13，

• 实现：

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

  // 定义： 以root为根的树中是否含有和为sum的路径 bool hasPathSum(TreeNode* root, int sum) { // if root is NULL if (!root) return false; // if this root is a leaf if (root->left == nullptr && root->right == nullptr) return root->val == sum; // if root has the left child if (hasPathSum(root->left, sum-root->val)) return true; // if root has the right child if (hasPathSum(root->right, sum-root->val)) return true; return false; }

  本质上还是先序遍历。敲黑板sum值在“跳进”后，变小，“跳出”后，又变回原来值。“跳进”表示，递归调用自己，“跳出”表示，这次递归调用执行到return语句。就本问题而言，但遍历到结点13时，满足sum 13==13，所以在此返回true。遍历不再执行，所以右下角结点4从未被遍历到。

#589 N-ary Tree Preorder Traversal

• 描述

  1	Given an n-ary tree, return the preorder traversal of its nodes' values.

• 逻辑

  多叉树的先序遍历，思路很直接：先遍历root，后对于这个root的所有子节点，以子节点为新的root做同样的操作。
  这里的操作具体说是将节点值放入vector。

• 实现

  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

  void travel(Node* root, vector<int>& res){ if (!root) return; res.push_back(root->val); // root for (Node* chld : root->children) // all children of root travel(chld, res); } vector<int> preorder(Node* root){ vector<int> res; travel(root, res); return res; } // The definition of Node class Node { public: int val; vector<Node*> children; Node() {} Node(int _val, vector<Node*> _children) { val = _val; children = _children; } };

敲黑板这里有个模式：对于几乎所有树的问题，本质上都是树的遍历。遍历本质上是结点的移动控制。而对于当前节点来说，它的value是可得到的，对这个value的操作称之为结点操作。

总结一下与DP相关的问题。

64, 300(LIS), LCS, 120, 62, 303, 198,

DP特点：

• 把重复计算的结果保存下来，避免重复计算（记忆机制）。
• DP自下而上执行，通过可计算的最小子结构逐步向上求值，直到得到最终值。
• 通常问题是要求最优值。

实现DP方法：

• 画递归树，自顶向下思考，自下而上实现
• 找到合适的状态及状态转移方程
  • 状态：递归树的结点啥定义，即每一步记忆的内容是啥memo[i]，即函数是啥。
  • 状态转移方程：结点怎样实现，即怎样得到memo[i]，即函数怎么做。

#64 Minimum Sum Path

问题描述：

1
2
3
4
5
6
7
8
9
10
11
12

Given a m x n grid filled with non-negative numbers, find a path from **top left** to **bottom right** which minimizes the sum of all numbers along its path.
Note: You can only move either *down* or *right* at any point in time.

Input:
[
  [1,3,1],
  [1,5,1],
  [4,2,1]
]

Output: 7
the path 1→3→1→1→1 minimizes the sum, which is 7.

• 思路

  记忆的逐步实现：

  • 初始化：memo所有元素初始化为0，且第一行第一列特殊处理。

  • 状态定义：memo[i][j]表示从左上角到Input[i][j]的最短路径。

  • 状态转移方程：memo[i][j] = Input[i][j] + min(memo[i][j-1], memo[i-1][j])。

  • 返回值：memo[i-1][j-1]

    图示：

    

    最终返回memo右下角值：7。

• 看图说话

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

  int minPathSum(vector<vector<int>>& grid) { int m = grid.size(); int n = grid[0].size(); for (int i=1; i<m; i++) grid[i][0] += grid[i-1][0]; for (int i=1; i<n; i++) grid[0][i] += grid[0][i-1]; for (int i=1; i<m; i++){ for (int j=1; j<n; j++) grid[i][j] += min(grid[i][j-1], grid[i-1][j]); } return grid[m-1][n-1]; }

#300 Longest Increasing Subsequence

• 描述

1
2
3
4
5

Input: [10,9,2,5,3,7,101,18]
Output: 4 
Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4. 

返回最长公共子序列的长度。

• 逻辑

  • 初始化：mem数组为全1。
  • 状态的定义：定义mem[i]为以nums[i] 为结尾的最长上升子序列的长度。
  • 状态转移方程：当前元素nums[i]与其前元素逐个比较，如果当前元素大于其前某个元素nums[j]，更新mem[i]=max(mem[i], 1+mem[j]).
  • 最终：找到mem数组中最大的值即可。DONE

• 实现

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

  int lengthOfLIS(vector<int>& nums) { if (nums.size() == 0) return 0; // calculate memo vector<int> memo(nums.size(), 1); for (int i=1; i<nums.size(); i++){ for (int j=0; j<i; j++){ if (nums[i]>nums[j]) memo[i] = max(memo[i], 1+memo[j]); } } // get max length int res = memo[0]; for (int i=0; i<memo.size(); i++) res = max(res, memo[i]); return res; }

关键：由最小已知求未知，接着根据当前的已知求进一步的未知， 状态的定义，找到状态转移方程，

#LCS Longest Common Subsequence

• 描述

1

给定两个字符数组，求其公共的子序列。公共子序列的元素在原序列中可以不连续。

• 逻辑

• 实现

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

string getLCS(const string& s1, const string& s2){
		int m = s1.size();
		int n = s2.size();
		
		vector<vector<int>> memo(m ,vector<int>(n, 0));
		// initilize memo
		for (int i=0; i<m; i++){
			if (s1[i]==s2[0]){
				for (int k=i; k<m; k++)
					memo[k][0] = 1;
				break;
			}	
		}

		for (int j=0; j<n; j++){
			if (s2[j]==s1[0]){
				for (int k=j; k<n; k++)
					memo[0][k]=1;
				break;
			}	
		}

		// DP progress for the rest
		for (int i=1; i<m; i++){
			for (int j=1; j<n; j++){
				if (s1[i]==s2[j])
					memo[i][j] = 1 + memo[i-1][j-1];
				else
					memo[i][j] = max(memo[i-1][j], memo[i][j-1]);
			}	
		}

		cout<<"The lenght of the LCS: "<<memo[m-1][n-1]<<endl;
		// get the longest common sequence
		string res = "";
		while (m>=0 && n>=0){
			if (s1[m] == s2[n]){
				res = s1[m] + res;
				m--;
				n--;
			}
			else if (m==0) n--;
			else if (n==0) m--;
			else{
				if (memo[m-1][n]>memo[m][n-1]) m--;
				else n--;
			}
		}
		return res;
	}

#120 Triangle

• 描述

1
2
3
4
5
6
7
8
9
10
11
12
13

Given a triangle, find the minimum path sum from top to bottom. 
Each step you may move to adjacent numbers on the row below.

For example, given the following triangle

[
     [2],
    [3,4],
   [6,5,7],
  [4,1,8,3]
]

The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).

• 逻辑

  bottom-up DP或者Top-down DP。使用Top-down：

  • 状态定义：triangle[i][j] 表示从顶端到第i行第j个位置的最小路径

  • 状态转移方程：见下图

    Top-down DP过程如下图表示：其中椭圆结点构成的triangle为源triangle，矩形结点构成的triangle就是DP的mem，即状态。

    

• 看图说话

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

  int minimumTotal(vector<vector<int>>& triangle) { int n = triangle.size(); // height of this triangle triangle[0][0] = triangle[0][0]; for (int i = 1; i<n; i++){ // // 这一行第一个值 triangle[i][0] += triangle[i-1][0]; // 这一行最后一个值 triangle[i][i] += triangle[i-1][i-1]; // 这一行其他值 for (int j=1;j<i;j++) triangle[i][j] += min(triangle[i-1][j-1], triangle[i-1][j]); } // 源triangle被修改了，所以最终结果在这个triangle的最后一层找最小值即可 return *min_element(triangle[n-1].begin(), triangle[n-1].end()); }

关键：当处理最值相关问题，考虑DP

#62 Unique Path

• 描述

1

从grid的左上角位置到右下角位置有几种走法？只能向下走或向右走。

• 逻辑

  Top-down DP或者Bottom-up DP，使用Bottom-up：

  • 状态定义：从(i,j)出发到终点(m-1,n-1)由多少条路径。
  • 状态转移方程：同Fibonacci()，numPath(i,j) = numPath(i,j+1) + numPath(i+1,j);
  • 初始化最右边和最下边值为1. 过程从这里开始up。

• 实现

  • Bottom-up

    1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

    int uniquePaths(int m, int n) { vector<vector<int>> memo(m, vector<int>(n, -1)); // 初始化最下行 for (int i=0;i<m; i++) memo[i][n-1] = 1; // 初始化最右行 for (int j=0; j<n; j++) memo[m-1][j] = 1; // Bottom up for(int i = m-2; i>=0; i-- ) for(int j = n-2; j>=0; j-- ) memo[i][j] = memo[i][j+1] + memo[i+1][j]; return memo[0][0]; }

  • Top-down

    1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

    int uniquePaths(int m, int n) { vector<vector<int>> memo(m, vector<int>(n, -1)); // 初始化第一行 for (int i=0;i<m; i++) memo[i][0] = 1; // 初始化最左行 for (int j=0; j<n; j++) memo[0][j] = 1; // top-down for (int i=1;i<m; i++) for (int j=1; j<n; j++) memo[i][j] = memo[i-1][j] + memo[i][j-1]; return memo[m-1][n-1]; }

#303 Range Sum Query - Immutable

• 描述

1
2
3
4
5
6
7
8

Given an integer array nums, find the sum of the elements between indices i and j (i ≤ j), inclusive.

Example:
Given nums = [-2, 0, 3, -5, 2, -1]

sumRange(0, 2) -> 1
sumRange(2, 5) -> -1
sumRange(0, 5) -> -3

• 逻辑

  从nums[i] 到nums[j] 元素累加就可以了。这种方法对于一条query，没问题。但是query一般频繁的。最好可以把结果提前计算出来，之后的query操作秩序做一次减法，便可以得到结果。所以使用DP。

  • 状态定义：mem[0]=0，mem[i]表示从第一个数到第i个数的和。
  • 状态转移方程：memo[i+1] = memo[i] + nums[i];
  • 初始化mem为全零。

• 实现

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

  class NumArray2{ private: vector<int> memo; public: NumArray2(vector<int>& nums){ // n+1个元素。 memo = vector<int>(nums.size()+1, 0); for (int i=0; i<nums.size(); i++) memo[i+1] = memo[i] + nums[i]; } // 频繁操作只需求一次减法。效率高 int sumRange(int i, int j){ return memo[j+1] - memo[i]; } };

#198 House Robber

• 描述

1
2
3
4
5
6

一条街上有若干房子，现在要抢劫房子，从街头到街尾，所抢的房子不能直接相邻，求可能的最大收益。

Input: [2,7,9,3,1]
Output: 12
Explanation: Rob house 1 (money = 2), rob house 3 (money = 9) and rob house 5 (money = 1).
             Total amount you can rob = 2 + 9 + 1 = 12.

• 逻辑

  • 状态定义：mem[i]表示抢[0~i]可获得的最大收益。

  • 状态转移方程：memo[i] = max(memo[i-1], nums[i]+tmp;

    下图为抢house=[5,2,3,1,1,5]的DP过程：

    

• 实现

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

  int rob(vector<int>& nums) { vector<int> memo(nums.size(), 0); // 切入口：前两个值特殊处理 memo[0] = nums[0]; memo[1] = max(nums[0], nums[1]); // 开始切~~ for (int i=2; i<nums.size(); i++){ // 求tmp：当前位置之前可抢劫最大收益（不包括与当前位置紧邻的房子） int tmp=0; for (int j=0; j<=i-2; j++) if (memo[j]>tmp) tmp = memo[j]; memo[i] = max(memo[i-1], nums[i]+tmp); } return memo[nums.size()-1]; }

  关键：mem[],以初始化的值为切入点，一个一个计算。，

这篇笔记为概述，记录使用模拟退火算法(Simulated Anneling)解决，迁移学习(Transfer Learning)应用在增强学习(Reinforcemet Learning)任务间整体效率的问题。实现过程看这里。

增强学习

增强学习是一个agent在与它所处的环境相互作用中学习的过程。比如把一只老鼠放在一个迷宫中，让它自己试错找到出口。agent与环境的相互作用由三个变量体现：状态，动作，奖励。状态指agent当前的位置，动作指agent在当前位置有哪些行动的选择。比如老鼠在迷宫中的当前位置可以向前，后，左，右移动。奖励指agent在每次行动后得到的奖励。比如迷宫中的老鼠每找到一粒花生得+10奖励，若它掉进陷阱里得到-10的奖励，且本次学习结束。为了让老鼠尽快学习，一般设置，如果每次执行一个动作，没有正负效果的话，获得-1奖励。这激励agent用较少的步数达到目标，对于老鼠说，吃到花生。

增强学习的可视化环境使用开源BURLAP可视化RL环境。其中agent是个像素小人儿，小人儿的目标是执行不同的动作来找到出口。使用Q-learning学习算法后，可以得到关于本阶段相关数据。一个阶段可能要执行多次学习，比如100次学习。这个项目使用3列数据：Episode Index，#Actions，Reward。这些数据在学习过程中生成，并且保存在外部文件中。

经过一个阶段的学习后，可视化这个阶段学习：Reward-EpisodesIndex图像。E-R图像表示每一个episode对应的reward。可以观察到小人儿确实学习了的。因为钱若干次的R值较小且波动，但是呈上升趋势，直到上升到一个稳定值。此时可以认为小人儿停止学习了，或者说，小人儿找到了最优路径。开始稳定横坐标暂且称为“完全学习Episode”。

为了减少噪声对R-E图像的影响，可以尝试让小人儿学习多阶段，比如10阶段，每阶段学习相同次数，后对R&A分别求均值。为了使图像便于观察，对平均操作后的图像加上平滑操作。平滑后的图像。

迁移学习

迁移学习对于相似但又不同的任务(一个成为源任务，另一个成为目标任务)，可以把在源任务中学习到的内容应用于目标任务的学习中，进而可以加速目标学习的速度。这已被实验证实。

目标

进一步实验发现，其实即使只在源任务学习少于“完全学习Episode”的Episode，在目标任务中的学习也可以提前拟合，相较于从零开始学习目标任务。目标任务提前拟合。那么小人儿在源中学习具体学习多少次，可以使迁移后的整体步数更少来达到拟合。

此处对于图像有个改动，横轴不再是Episode Index，而换成每一个Episode对应的Accumulated Actions。即从此往下使用AA-R图像。为什么要如此做，这么做，横轴不单单是Episode，更增加了到达这一Episode为止一共执行了多少Actions。换句话说，之前这个“系统”中的信息只有Episode Index和对应的Reward，两个有用信息。现在这个“系统”中的有用信息包括，Episode Index，当前Episode的Actions数和从开始到现在一共的Actions数。根据信息论观点，增加有用信息，可以减少系统不确定性。

回到问题，具体在源任务中学习多少次。先探索一下。我的做法是，1）分别在源任务中学习1E，2E，3E，… ，nE后迁移到目标任务中，如此得到n个迁移学习过程。对应n个AA-R条曲线，并合并到一幅图中。2）设定一个具体Reward值为R。观察哪条曲线先穿过R。现在我的目标转化为，在不需要执行完n个迁移学习过程的前提下，如何确定哪条曲线先穿过R。

记录第二步中每条曲线穿过R时的对应Episode值，如此便可以得到在源任务中学习次数与其对应的穿过R时的AA值。绘出这条曲线。E-AA图像。此时的目标转化为：在这条曲线中搜索最小值。多次实验发现这条曲线是非凸的，即有局部最小值，且很多。所以在线搜索只能找到第一个局部最优值，不可取。那遍历一遍就可以搜索到最小值。错，如果那样做，整个过程将毫无意义。为了搜索最值，而把所有值求出来。记住求出曲线中一个值，其代价是要完整地执行RL(Surce task)->TL->RL(Target task) 阶段数×每阶段的Episode数。比如10阶段，每阶段执行100Episode。得到一个值要执行1000次完整的上述过程。成本太高。

这个问题类似TSP(Traveling Salesman Problem)问题。同样是求最值，TSP提前得到所有方案是不可能的，就现在的计算机。借鉴TSP的解法，遗传算法或模拟退火，分别点击见实现。因为此问题的输入不是序列，所以遗传算法不适用，实验模拟退火，成功。

模拟退火与遗传算法都属于带有随机性的算法。遗传算法中的交叉，变异操作，模拟退火中的以一定概率接受一个比之前差的结果，都是引入随机性。而随机性给了算法跳出当前局部最有值的能力。

敲黑板

1. 这个项目中达到目标进行了至少两次的问题转化。
2. 借鉴相同性质问题的成熟解法。
3. 积累不同问题的解法。

ROC曲线是由TPR和FPR为横纵轴，

• TPR表示：所有实际为正，我的模型有多少也预测为正；
• FPR表示：所有实际为反，我的模型由多少预测为正。

二者实现如下，其中你已经知道TP，FN，FP，TN的含义：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

def TPR(y_true, y_predict):
    tp = TP(y_true, y_predict)
    fn = FN(y_true, y_predict)
    try:
        return tp / (tp + fn)
    except:
        return 0.


def FPR(y_true, y_predict):
    fp = FP(y_true, y_predict)
    tn = TN(y_true, y_predict)
    try:
        return fp / (fp + tn)
    except:
        return 0.

TPR和FPR是和P&R相似的概念，计算所用到的值都在Confusion Matrix中。所以绘制ROC图过程同PR曲线：

1
2
3
4
5
6
7

fprs = []
tprs = []
thresholds = np.arange(np.min(decision_scores), np.max(decision_scores), 0.1)
for threshold in thresholds:
    y_predict = np.array(decision_scores >= threshold, dtype='int')
    fprs.append(FPR(y_test, y_predict))
    tprs.append(TPR(y_test, y_predict))

得到不同的threshold值，每一个值对应一个模型，计算每一个模型的TPR和FPR，分别放入空列表中。就可以绘图了：

1
2
3
4
5

plt.plot(fprs, tprs, label='ROC')
plt.legend(loc='lower right', prop={'size': 10})
plt.xlabel('FPR')
plt.ylabel('TPR')
plt.show()

结果：

使用sklearn中自带实现：

1
2
3
4
5
6
7
8
9

from sklearn.metrics import roc_curve

fprs, tprs, thresholds = roc_curve(y_test, decision_scores)

plt.plot(fprs, tprs, label='ROC')
plt.legend(loc='lower right', prop={'size': 10})
plt.xlabel('FPR')
plt.ylabel('TPR')
plt.show()

如图：

ROC的作用是为了计算AUC(Area Under Curve)。而比较模型的相对性能，只要得到两个模型各自的ROC，分别计算各自的AUC，谁大，谁的相对性能好。

sklearn提供AUC的计算：

1
2
3

from sklearn.metrics import roc_auc_score

print(roc_auc_score(y_test, decision_scores))     #  0.98304526749

传入y_test和decision_scores即可得到。

敲黑板ROC的两个指标，与PR指标相似又不同，是另一个角度的对模型性能的量化。引入相似但不同的信息有助于减少系统的不确定性，这里是模型选择的不确定性。衡量一个模型的性能，通常要尽可能把所有指标都找到，综合衡量。
给出liuyubobobo老师的话：
我们的目的不是“找到”单一的“最好”的指标；而是了解所有的指标背后在反映什么，在看到这个指标出现问题的时候，能够判断问题可能出现在哪里，进而改进我们的模型。虽然我们的改进方向可能是单一的。

具体到PR曲线和ROC曲线，他们的核心区别在TN。可以看出来，PR曲线其实不反应TN。所以，如果你的应用场景中，如果TN并不重要，那么PR曲线是一个很好的指标（事实上，Precision和Recall就是通过抹去TN，来去除极度的偏斜数据带来的影响，进而放大FP, FN和TP三者的关系的）。

而ROC曲线则综合了TN, FP, FN和TP。虽然它对TN极度多的情况下，FP，FN和TP的变化不敏感。所以在TN没有那么多（数据没有那么偏斜），或者TN是一种很重要的需要考虑的情况下，ROC能反映出PR不能反映的问题。

Precision和Recall是两个矛盾的度量，一个变大时，另一个就变小。怎样格式化P-R的关系呢。P-R曲线。

绘制P-R曲线

根据每一个样本得到不同的分类平面，即许多个不同的模型。对每一个模型计算P&R值，最后以P，R为横纵轴绘图。

1. 如何得到不同模型

图示

假设已经使用训练样本训练出一个Logistic Regression模型log_reg，测试集x_test，y_test。调用训练好模型的decision_function()，返回所有分类平面。其实Logistic Regression的默认分类平面是y=0，即threshold=0。

decision_scores记录所有分类平面：

1
2
3
4

decision_scores = log_reg.decision_function(x_test)  
print(len(decision_scores))         #  450
print(np.min(decision_scores))      #  -85.6861241675
print(np.max(decision_scores))      #  19.8896068857

当threshold = 0时，即默认分类平面对应的模型各指标：

1
2
3
4
5

y_predict = log_reg.predict(x_test)            
print(confusion_matrix(y_test, y_predict))    #  [[403   2]
                                              #   [  9  36]]
print(precision_score(y_test, y_predict))     #  0.947368421053
print(recall_score(y_test, y_predict))        #  0.8

当使用threshold = -5为分类平面时，三指标：

1
2
3
4
5
6

# 移动threshold到-5得到不同的模型：
y_predict_m5 = np.asarray(decision_scores >= -5, dtype='int')
print(confusion_matrix(y_test, y_predict_m5))   #  [[390  15]
                                                #   [  5  40]]
print(precision_score(y_test, y_predict_m5))    #  0.727272727273
print(recall_score(y_test, y_predict_m5))       #  0.888888888889

相较threshold = 0的模型，P下降，R上升。

当使用threshold = 5为分类平面时，三指标：

1
2
3
4
5
6

# 移动threshold到5得到不同的模型：
y_predict_5 = np.asarray(decision_scores >= 5, dtype='int')
print(confusion_matrix(y_test, y_predict_5))    #  [[404   1]
                                                #   [ 21  24]]
print(precision_score(y_test, y_predict_5))     #  0.96
print(recall_score(y_test, y_predict_5))        #  0.533333333333

相较threshold = 0的模型，P上升，R下降。

2. 绘制曲线

得到每一个threshold对应的P，R值，绘制P-R曲线。

有了对某一个threshold的理解，现在相隔0.1取一个threshold，获得所有P，所有R：

1
2
3
4
5
6
7
8
9
10
11

import matplotlib.pyplot as plt
precisions = []                           # 记录所有P
recalls = []                              # 记录所有R
# 相隔0.1取一个threshold值保存：
thresholds = np.arange(np.min(decision_scores), np.max(decision_scores), 0.1)

# 记录每一个threshold对应模型的P&R:
for threshold in thresholds:
    y_predict = np.array(decision_scores >= threshold, dtype='int')
    precisions.append(precision_score(y_test, y_predict))
    recalls.append(recall_score(y_test, y_predict))

绘图thresholds vs precisions和thresholds vs recalls：

1
2
3
4
5
6

plt.plot(thresholds, precisions, label='P')
plt.plot(thresholds, recalls, label='R', )
plt.legend(loc='center left', prop={'size': 10})
plt.xlabel('threshold')
plt.ylabel('P/R')
plt.show()

结果：

绘制precision vs recall：

1
2
3
4
5

plt.plot(precisions, recalls, label='P-R')
plt.legend(loc='lower left', prop={'size': 10})
plt.xlabel('P')
plt.ylabel('R')
plt.show()

结果：

敲黑板经过实验得出：

1. 最优threshold基本都在0附近，因此可以说，若没有对某一指标有具体的定量要求，只用判别threshold=0时的指标就可以对整个模型的性能进行评估了。
2. 第二点，一个二分类模型尝试移动分类平面，可以得到对于P&R不同重视程度的模型。

对于P-R曲线的几点补充：

• 实际中，对P-R曲线进行平滑操作
• 如果由若干个模型的P-R曲线在同一个图中，如何判断哪个最优。
  1. 看哪一个曲线把其他的“包住”
  2. 比较每条曲线与坐标轴围成的面积

附件

sklearn package中的绘制P-R曲线的方法：

1
2
3
4
5
6
7
8
9
10

from sklearn.metrics import precision_recall_curve

pres, recs, thrs = precision_recall_curve(y_test, decision_scores)

plt.plot(thrs, pres[:-1], label='thr-P')
plt.plot(thrs, recs[:-1], label='thr-R', )
plt.legend(loc='center left', prop={'size': 10})
plt.xlabel('threshold')
plt.ylabel('P/R')
plt.show()

不同threshold的P/R值:

与上述实现不同在于，上述实现的threashold值从decision_scores的最小值到最大值，而package中函数把threshold值小于-18的值忽略未记，因为图一中这部分对于用户是没有决策贡献的。抓住要矛盾。

1
2
3
4
5

plt.plot(pres, recs, label='P-R')
plt.legend(loc='lower left', prop={'size': 10})
plt.xlabel('P')
plt.ylabel('R')
plt.show()

P/R曲线

F1

F1度量是基于Precision和recall的调和平均定义的：

定义

1
2
3
4
5

def f1_score(precision, recall):
    try:
        return 2 * precision * recall/(precision+recall)
    except:
        return 0.0

对于一个训练好的模型，用于测试样本上得到测试样本的预测值，和真实值一起，计算出P&R。代入F1定义，得这个模型的F1值：

代入不同的P&R组合，看看对应F1：

1
2
3
4

print(f1_score(0.9, 0.8))    # 0.8470588235294118
print(f1_score(0.9, 0.1))    # 0.18000000000000002
print(f1_score(0.5, 0.5))    # 0.5
print(f1_score(0.1, 0.1))    # 0.10000000000000002

根据这些结果可以看出调和平均值的特点：当P&R值都较大时，对应F1也较大。当P&R一大一小差别很大时，对应F1接近较小值。当P&R值很平均时，F1接近两者的平均值。

F1是综合考虑了P值和R值，一般地，F1值越大表示模型性能越好。但是，如上一篇笔记所述，不同的实际应用场景对于P和R的重视程度是不同的。如，在推荐系统中，为了尽可能精准推荐，P就相对重要；逃犯系统中，为了不漏掉任何一个罪犯，哪怕一个很可疑但无辜的嫌疑人，先认为他是罪犯，抓起来再说。此时R相对重要。对于冤枉的，进一步审问就好了；而对于实际是罪犯，但被模型漏掉了，此情况代价是很高的。
所以对于具体问题，使用F-beta度量。

F-beta

F-beta是F1的更一般形式，它表达出对P&R的不同偏好：

定义

把训练好的样本用于测试集y_test后，得到的预测值y_predict，代入F-beta定义：

1
2
3
4
5
6
7

from sklearn.metrics import fbeta_score

print(f1_score(y_test, y_predict))          # 0.867469879518
print(fbeta_score(y_test, y_predict, 1))    # 0.867469879518   when beta=1,
print(fbeta_score(y_test, y_predict, 0.2))  # 0.940703517588   when beta=0.2,
print(fbeta_score(y_test, y_predict, 0.8))  # 0.883832335329   when beta=0.8,
print(fbeta_score(y_test, y_predict, 1.8))  # 0.830467899891   when beta=1.8,

beta>0为前提条件。beta为1时，退化为F1。beta<1，P影响大，beta>1，R影响大。
不同的beta值代表不同的应用场景，一个训练好的模型有它实用的场景。

这篇笔记记录Confusion Matrix。

当训练好了模型，需要评价它的性能。错误率和准确率是常用的，一般为了测试一个模型的正确性，用这个指标，尤其对于极度均衡的数据。但是对于极度偏斜的数据，用准确率评价模型很可能得到的结果表示，这个模型还不如随机猜测的准确率高。此时准确率不足以衡量模型性能。所以必要使用其他性能指标。

由混淆矩阵得到的Precision， Recall 和 F1度量，F-beta度量。

其定义不赘述，看下图。

图中，P，R的含义在清楚不过了。

使用真实数据集算一下。

引入数据，把它变为极度偏斜的二分类问题：

1
2
3
4
5
6
7
8
9
10
11
12

import numpy as np
from sklearn import datasets

digits = datasets.load_digits()
x = digits.data
y = digits.target.copy()

y[digits.target == 9] = 1
y[digits.target != 9] = 0

# 分训练样本和测试样本
x_train, x_test, y_train, y_test = train_test_split(x, y, random_state=666)

这里使用Logistic Regression对其学习：

1
2
3
4
5
6

from sklearn.linear_model import LogisticRegression
log_reg = LogisticRegression()
log_reg.fit(x_train, y_train)
acc = log_reg.score(x_test, y_test)
y_log_predict = log_reg.predict(x_test)
print(acc)

得结果：0.975555555556。注意数据集是很不平衡的，所以这个值不可靠。

根据混淆矩阵的定义，可得：

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

def TN(y_true, y_predict):
    assert len(y_true) == len(y_predict)
    return np.sum((y_true == 0) & (y_predict == 0))


def TP(y_true, y_predict):
    assert len(y_true) == len(y_predict)
    return np.sum((y_true == 1) & (y_predict == 1))


def FN(y_true, y_predict):
    assert len(y_true) == len(y_predict)
    return np.sum((y_true == 1) & (y_predict == 0))


def FP(y_true, y_predict):
    assert len(y_true) == len(y_predict)
    return np.sum((y_true == 0) & (y_predict == 1))


def confusion_matrix(y_true, y_predict):
    return np.array([[TN(y_true, y_predict), FP(y_true, y_predict)],
                     [FN(y_true, y_predict), TP(y_true, y_predict)]])

# 打印出混淆矩阵：
print(confusion_matrix(y_test, y_log_predict))

结果：

1
2

[[403   2]
 [  9  36]]

一般来说，最优情况是，其对角线的值最大，斜对角线值为0。详见多分类问题的混淆矩阵。

Precision=0.947368421053， Recall=0.8。标准是，此而值同时越大模型性能约优。可以说这个模型的性能还不错。

敲黑板啥是R，“所有实际为正的样本，我的模型有多少也认为为正”。啥是P，“所有我的模型认为为正的样本，有多少确实为正”。可以体会到，P&R 是不同角度的两个指标。根据信息论观点，引入相似但不相同的信息有助于减少系统的不确定性。两个指标同时考虑比单单考虑一个指标更能确定模型的性能。实际上，可能的情况下，对于一个训练好的模型，所有可能的指标都应该看看。
另一方面，P&R两者的关注点不同，所以对于不同的实际任务，P&R值的相对大小可以有所不同。举例，对于病例数据，尽可能希望所有实际有病的样本，模型也认为有病。即实际有病的样本模型都可以判断出来，即使没病的模型认为有病，没关系，复查就好了。这就是R值越大模型性能越好。反而P值相对不重要。

在上一篇笔记文本分类(三)-构建模型I-built-in-LSTM 中tensorflow中的LSTM相关函数实现了LSTM层。这篇笔记记录把LSTM单元拆解，一步一步实现，即 from scratch

理解这一篇笔记的细节，要结合上一篇笔记，尤其是其最后一段，结合这里的细节，体会。

LSTM结点如下图：

一般RNN存在信息过载而不能长久传播的问题，LSTM单元结构存在三重门机制尝试解决这个问题。

假如一个词的编号为12，将它对应的embedding向量输入LSTM 结点中有一下过程发生：

• 得到这个词的embedding，大小为[batch_size, 1, embedd_size]：

1

embedd_input = embedded_inputs[:, 12, :]

• 变形为：[batch_size, embedd_size]

1

embedd_input = tf.reshape(embedd_input, [batch_size, hps.num_embedding_size])

三重门过程，公式及实现：

遗忘门：

1
2

forget_gate = tf.sigmoid( 
                        tf.matmul(embedd_input, fx_w) + tf.matmul(h, fh_w) + fb)

输入门：

1
2
3
4

input_gate = tf.sigmoid(
                        tf.matmul(embedd_input, ix_w) + tf.matmul(h, ih_w) + ib)
mid_state = tf.tanh(
                        tf.matmul(embedd_input, cx_w) + tf.matmul(h, ch_w) + cb)

结点隐含状态输出：

1

state_C = mid_state * input_gate + state_C * forget_gate

输出门及结点LSTM的输出：

1
2
3

output_gate = tf.sigmoid(
                        tf.matmul(embedd_input, ox_w) + tf.matmul(h, oh_w) + ob)
h = output_gate * tf.tanh(state)

以上是对于样本中一个词的操作，对于该样本中所有词的操作如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

for i in range(encoded_length):
    embedd_input = embedded_inputs[:, i, :]   
    embedd_input = tf.reshape(embedd_input, [batch_size, hps.num_embedding_size])
    forget_gate = tf.sigmoid(
                            tf.matmul(embedd_input, fx_w) + tf.matmul(h, fh_w) + fb)
    input_gate = tf.sigmoid(
                            tf.matmul(embedd_input, ix_w) + tf.matmul(h, ih_w) + ib)
    mid_state = tf.tanh(
                            tf.matmul(embedd_input, cx_w) + tf.matmul(h, ch_w) + cb)

    state_C = mid_state * input_gate + state_C * forget_gate 

    output_gate = tf.sigmoid(
                            tf.matmul(embedd_input, ox_w) + tf.matmul(h, oh_w) + ob)
    h = output_gate * tf.tanh(state)
last = h

其中encode_lenght表示每一个样本(一条评论)的长度，即评论词的个数，此处是50个。
这个序列操作中有那两个值在不断更新

• state_C
• h

这两个值的不断更新使得对每个词操作的每个LSTM结点在逻辑上是连在一起的，如下图：

敲黑板将等号左边按时间次序展开就是右边。实现中一个LSTM结点可以代表一个神经元，只不过这一个神经元内部有5个非线性变换。对于复杂问题一个这样的神经元不足以表达输入数据，所以会有多个这样的神经元。
这里的实现源码看这里。源码中对网络的设置为：

1
2
3

num_lstm_nodes=[32, 32],    
num_lstm_layers=2,
encoded_length=50,

表示这个模型有2层LSTM，每一层的神经原结点有32个，而每一层中的每一个神经元所处理的输入序列长50！

务必理解

完成

LSTM结点实现。

本笔记所有图片来源与colah’s blog

这篇笔记记录使用tensorflow的built-in LSTM创建一个文本分类模型，数据来自文本预处理(二)词编码。

超参数

首先定义模型使用的超参数，使用tf.contrib.training.HParams()来管理,如下：

1
2
3
4
5
6
7
8
9
10
11

def huper_param():
    return tf.contrib.training.HParams(
            num_embedding_size=16,  #  每一个词所作embedding的向量长度
            encoded_length=50,      #  每一条编码后的样本切取或补充后的长度，
            num_word_threshold=20,  #  词频数<=该值，不考虑
            num_lstm_nodes=[32, 32],  # 每一层LSTM的节点个数 
            num_lstm_layers=2,       #  LSTM层数
            num_fc_nodes=32,         #  全连接层节点数
            batch_size=100,          #  每一次输入样本书
            learning_rate=0.001,    # 学习率
            clip_lstm_grads=1.0, )   #  设置LSTM梯度大小，防止梯度爆炸

默认每一个参数含初始值，各个参数的含义见注释。其中具体解释两个：

• num_embedding_size： 每一个词会用一个向量来表示，该值指明这个向量的大小。而且这个向量是被学习的。
• clip_lstm_grads： 这是LSTM梯度值的上限，当一个梯度值大于这个上限时，把这个值设置为上限值，来防止梯度爆炸。

调用该函数生成一个对象，可以用对象名.参数名来使用相应的参数：

1
2

hp = huper_param()
encoded_length = hp.encoded_length

定义计算图

先定义输入：

1
2

inputs = tf.placeholder(tf.int32, (batch_size, encoded_length))
outputs = tf.placeholder(tf.int32, (batch_size, ))

定义DropOut比率：

1

keep_prob = tf.placeholder(tf.float32, name='keep_prob')

保存当前训练到了那一步：

1

global_step = tf.Variable(tf.zeros([], tf.int64), name='global_step', trainable=False)

1. Embedding层

使用均匀分布来初始化：

1

embedding_init = tf.random_uniform_initializer(-1.0, 1.)

定义embedding：

1
2
3
4
5

embedding = tf.get_variable(
            'embedding',
            [vocab_size, hps.embedding_size],   # size of embedding matrix
            tf.float32
)

说明：

• 使用get_varable()，当这个变量存在，就重用它，不存在，则创建它。
• embedding矩阵：[vocab_size, hps.embedding_size]：一共有多少个词，每个词用多大的向量表示。

下一步，将每一条输入中每一个词对应的向量在embedding matrix中查找，比如，当前词id为12，就从embedding matrix中把第12行的向量取出来，对一条记录中每个词作此操作：

1
2
3
4

[2, 34, 5, 67]->[[234,565,1,45,57,73],
                 [12,76,23,54,123,48],
                 [43,87,239,57,13,14],
                 [98,64,421,13,63,36]]

用长度为6的向量表示一个词的id。可以看作是对每一条记录的进一步编码。而且这个编码是要被学习的。

给出完整embedding层：

1
2
3
4
5
6
7
8
9

embedding_init = tf.random_uniform_initializer(-1.0, 1.)
    with tf.variable_scope('embedding', initializer=embedding_init):
        embedding = tf.get_variable(
            'embedding',
            [vocab_size, hps.embedding_size],   # size of embedding matrix
            tf.float32
        )
        #
        embedded_inputs = tf.nn.embedding_lookup(embedding, inputs)

2. LSTM 层

定义initializer：

1
2

scale = 1.0/math.sqrt(hps.num_embedding_size + hps.nums_lstm_nodes[-1])/3.0
lstm_init = tf.random_uniform_initializer(-scale, scale)

即使用xavior初始化。

定义两层LSTM：

1
2
3
4
5
6
7
8
9
10
11

cells = []
for i in range(2):
    cell = tf.contrib.rnn.BasicLSTMCell(
        hps.nums_lstm_nodes[i],
        state_is_tuple=True
    )
    cell = tf.contrib.rnn.DropoutWrapper(
        cell,
        output_keep_prob=keep_prob
    )
    cells.append(cell)

cells接收每一层，使用BasicLSTMCell创建一LSTM层。紧接着使用DropoutWrapper执行DropOut操作。此时cells中含有两层LSTM。

然后使用MultiRNNCell合并两LSTM层，第一个cell的输出为第二个cell的输入：

1

cell = tf.contrib.rnn.MultiRNNCell(cells)

此时就可以把两层的LSTM当作模型中的一层来操作。

紧接着初始化LSTM单元中的state：

1

initialize_state = cell.zero_state(batch_size, tf.float32)

此时便可以使用dynamic_rnn把序列式的输入传入LSTM层，后得到一系列中间状态和输出值：

1

rnn_outputs, _ = tf.nn.dynamic_rnn(cell, embedded_inputs, initial_state=initialize_state)

其中_表示中间隐含状态，不需要。rnn_outputs中包含了所有中间输出。对于多对一的问题，我们只需要最后一个值：

1

last = rnn_outputs[:, -1, :]

给出完整的LSTM层：

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

scale = 1.0/math.sqrt(hps.num_embedding_size + hps.nums_lstm_nodes[-1])/3.0
lstm_init = tf.random_uniform_initializer(-scale, scale)
with tf.variable_scope('lstm', initializer=lstm_init):
    # store two LSTM layers
    cells = []
    for i in range(hps.num_lstm_layer):
        cell = tf.contrib.rnn.BasicLSTMCell(
            hps.nums_lstm_nodes[i],
            state_is_tuple=True
        )
        cell = tf.contrib.rnn.DropoutWrapper(
            cell,
            output_keep_prob=keep_prob
        )
        cells.append(cell)
    # combine two LSTM layers: 第一个cell的输出为第二个cell的输入
    cell = tf.contrib.rnn.MultiRNNCell(cells)
    # init state
    initialize_state = cell.zero_state(batch_size, tf.float32)
    # input a sentence to cell, 此时就可以把句子输入到cell中

    # rnn_outputs: [batch_size, encoded_length, lstm_output[-1]]
    rnn_outputs, _ = tf.nn.dynamic_rnn(
        cell, embedded_inputs, initial_state=initialize_state)
    last = rnn_outputs[:, -1, :]

3. 全连接层

使用dence()构建全连接层，指定ReLU为激活函数：

1

fc1 = tf.layers.dense(last, hps.num_fc_nodes, activation=tf.nn.relu, name='fc1')

紧接着进行dropOut操作：

1

fc1_dropout = tf.contrib.layers.dropout(fc1, keep_prob)

最后再接一个全连接层：

1

logits = tf.layers.dense(fc1_dropout, classes_size, name='fc2')

给出完整的全连接层：

1
2
3
4
5

fc_init = tf.uniform_unit_scaling_initializer(factor=1.0)
with tf.variable_scope('fc', initializer=fc_init):
    fc1 = tf.layers.dense(last, hps.num_fc_nodes, activation=tf.nn.relu, name='fc1')
    fc1_dropout = tf.contrib.layers.dropout(fc1, keep_prob)
    logits = tf.layers.dense(fc1_dropout, classes_size, name='fc2')

4. 模型输出

首先：

1

softmax_loss = tf.nn.sparse_softmax_cross_entropy_with_logits(logits=logits, labels=outputs)

tf.nn.sparse_softmax_cross_entropy_with_logits()做了三件事：

• 填坑
• 填坑
• 填坑

其次，传入代价函数，并且算出模型输出：

1
2

loss = tf.reduce_mean(softmax_loss)
y_pred = tf.argmax(tf.nn.softmax(logits), 1, output_type=tf.int32)

最后，用最简单的正确率衡量模型性能：

1
2

correct_pred = tf.equal(outputs, y_pred)
accuracy = tf.reduce_mean(tf.cast(correct_pred, tf.float32))

说明下面二者的不同：

• tf.variable_scope：需要初始化
• tf.name_scope：无需初始化

此部分完整实现：

1
2
3
4
5
6
7
8

with tf.name_scope('metrics'):
    softmax_loss = tf.nn.sparse_softmax_cross_entropy_with_logits(
        logits=logits, labels=outputs
    )
    loss = tf.reduce_mean(softmax_loss)
    y_pred = tf.argmax(tf.nn.softmax(logits), 1, output_type=tf.int32)
    correct_pred = tf.equal(outputs, y_pred)
    accuracy = tf.reduce_mean(tf.cast(correct_pred, tf.float32))

5. 得到train_op

因为之前对梯度值设定了一个上界，所以要把截断后的梯度值得到，作用于所有可训练变量。所以第一步得到所有可训练变量：

1

trainable_vars = tf.trainable_variables()

可以查看所有的可训练变量：

1
2

for var in trainable_vars:
    print('variable name: %s' % (var.name))

对所有可训练变量求导数，得到实际梯度后对其执行剪切操作：

1

grads, _ = tf.clip_by_global_norm(tf.gradients(loss, trainable_vars), hps.clip_lstm_grads)

指定优化算法，应用剪切后的梯度于所有可训练变量。最后训练：

1
2

optimizer = tf.train.AdamOptimizer(hps.learning_rate)
train_op = optimizer.apply_gradients(zip(grads, trainable_vars), global_step=global_step)

完整实现：

1
2
3
4
5
6
7
8
9
10
11

with tf.name_scope('train_op'):
    trainable_vars = tf.trainable_variables()
    for var in trainable_vars:
        print('variable name: %s' % (var.name))
    grads, _ = tf.clip_by_global_norm(
        tf.gradients(loss, trainable_vars), hps.clip_lstm_grads
    )
    optimizer = tf.train.AdamOptimizer(hps.learning_rate)
    train_op = optimizer.apply_gradients(
        zip(grads, trainable_vars), global_step=global_step
    )

6. 返回值

最后指定函数返回值：

1
2
3

return ((inputs, outputs, keep_prob),  #  all placeholders
        (loss, accuracy),              # loss & accuracy
        (train_op, global_step))      # tain_op

到此位置计算图设计完成。

假设上述定义计算图可以封装到函数：create_model()。测试一下：

1
2
3
4
5
6

from dataPreProcess import encodeWords
vocab_instance = encodeWords.VocabDict(vocab_file, hps.num_word_threshold)
catego_instance = encodeWords.CategoryDict(category_file)
placeholders, metrics, others = create_model(hps,
                                             vocab_instance.size(),
                                             catego_instance.size())

encodedWords中是在文本预处理(二)词编码篇实现的两个类VocabDict和CategoryDict。分别调用其.size()方法，可返回词数量和类别数量。

打印所有可训练变量，控制台结果：

1
2
3
4
5
6
7
8
9

variable name: <tf.Variable 'embedding/embedding:0' shape=(50513, 16) dtype=float32_ref>
variable name: <tf.Variable 'lstm/rnn/multi_rnn_cell/cell_0/basic_lstm_cell/kernel:0' shape=(48, 128) dtype=float32_ref>
variable name: <tf.Variable 'lstm/rnn/multi_rnn_cell/cell_0/basic_lstm_cell/bias:0' shape=(128,) dtype=float32_ref>
variable name: <tf.Variable 'lstm/rnn/multi_rnn_cell/cell_1/basic_lstm_cell/kernel:0' shape=(64, 128) dtype=float32_ref>
variable name: <tf.Variable 'lstm/rnn/multi_rnn_cell/cell_1/basic_lstm_cell/bias:0' shape=(128,) dtype=float32_ref>
variable name: <tf.Variable 'fc/fc1/kernel:0' shape=(32, 32) dtype=float32_ref>
variable name: <tf.Variable 'fc/fc1/bias:0' shape=(32,) dtype=float32_ref>
variable name: <tf.Variable 'fc/fc2/kernel:0' shape=(32, 10) dtype=float32_ref>
variable name: <tf.Variable 'fc/fc2/bias:0' shape=(10,) dtype=float32_ref>

注意，训练并没有执行计算，只是打印了计算图中的可训练变量。结果显示有三部分：

• embedding层
• 两层LSTM的权值阈值
• 两层全连接层的权值和阈值

并且每部分参数的形状也可知。

执行计算流程

先执行create_model()：

1
2
3
4
5
6

placeholders, metrics, others = create_model(hps,
                                             vocab_instance.size(),
                                             catego_instance.size())
inputs, outputs, keep_prob = placeholders
loss, accuracy = metrics
train_op, global_step = others

然后初始化整个网络，给训练过程的keep_prob赋值，并指明训练步数：

1
2
3

init_op = tf.global_variables_initializer()
train_keep_prob = 0.8
num_train_steps = 1000

最后创建执行图的tf.session，并执行：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

with tf.Session() as sess:
    # init whole network
    sess.run(init_op)
    for i in range(num_train_steps):
        batch_inputs, batch_label = train_dataset.next_batch(hps.batch_size)
        # training: global_step+1 when sess.run() is called
        outputs_val = sess.run([loss, accuracy, train_op, global_step],
                               feed_dict={
                                   inputs: batch_inputs,
                                   outputs: batch_label,
                                   keep_prob: train_keep_prob
                               })
        # get three values from output_val
        loss_val, accuracy_val, _, global_step_val = outputs_val

        # print for every 100 times
        if global_step_val % 20 == 0:
            print("step: %5d, loss: %3.3f, accuracy: %3.5f" %
                  (global_step_val, loss_val, accuracy_val)
                  )

其中用到了一个重要方法：给placeholders赋值。所以在运行之前使用训练集创建EncodedDataset对象，就可以调用train_dataset.next_batch(hps.batch_size)了：

1
2

train_dataset = createEncodedDataset.EncodedDataset(
        seg_train_file, vocab_instance, catego_instance, hps.encoded_length)

如下时执行1000次的结果：

1
2
3
4
5

step:   200, loss: 1.732, accuracy: 0.25000
step:   400, loss: 1.720, accuracy: 0.32000
step:   600, loss: 1.537, accuracy: 0.39000
step:   800, loss: 1.279, accuracy: 0.53000
step:  1000, loss: 0.994, accuracy: 0.67000

至少证明模型是正确的。完整实现看这里。
这是第一步，之后便可以进一步优化。本笔记只记录使用tf内置LSTM模块构建基本LSTM文本分类模型，对于优化，调参以后讨论。

最后一点*

在参数列表中有一项num_lstm_nodes，什么意思？！在构建LSTM时的核心函数是：

1

cell = tf.contrib.rnn.BasicLSTMCell( hps.nums_lstm_nodes[i], state_is_tuple=True)

敲黑板

查看官方文档：首个参数num_units：它表示LSTM单元内部的神经元数量，即输出神经元数。LSTM结点结构图中有5个主要非线性变换，他们中的每一个都相当于普通神经网络的的一个神经原，相对于解决异或问题只需要3个神经元(逻辑门)，解决复杂问题的网络神经元数量都远远不止一个。

相同道理，包含5个非线性变换的一个LSTM结点在解决复杂问题时一定也远不只需要一个。图中只是示意图，表示一个结点，实际上会有很多。从LSTM层使用xavior初始化的角度看，sqrt(hps.num_embedding_size + hps.nums_lstm_nodes[-1])定义代表sqrt(输入大小 + 输出大小)，hps.nums_lstm_nodes[-1]正对应这一层的输出大小。

诶，在图中也有多个LSTM节点呀！？，这些结点是逻辑上按时间序列展开的节点，空间上只有一个。这里讨论的是另一个维度的LSTM结点。并不矛盾。可以从下一节笔记的代码实现中体会。

理解这个很重要！