Posted on | In

1. Two Sum

Description

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:

1
2
3
4
Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

Idea

hashmap，一次遍历的时候，存之后可能出现的值和此时值的index，比如:[2, 7, 11, 15], t = 9, 遍历2的时候存k : 9 - 2 = 7 , v : 0

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        dic = {}
        for i in range(len(nums)):
            if nums[i] not in dic:
                dic[target - nums[i]] = i
            else:
                return [dic[nums[i]]] + [i]

Posted on | In

Description

Given an array of strings, group anagrams together.

Example:

1
2
3
4
5
6
7
Input: ["eat", "tea", "tan", "ate", "nat", "bat"],
Output:
[
  ["ate","eat","tea"],
  ["nat","tan"],
  ["bat"]
]

Note:

  • All inputs will be in lowercase.
  • The order of your output does not matter.

Idea

You can sort str “ate”,”eat”,”tea” into “aet”, “aet”, “aet”, then they will share the same key, which bring the hashmap into your mind.

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution(object):
    def groupAnagrams(self, strs):
        """
        :type strs: List[str]
        :rtype: List[List[str]]
        """
        dic = {}
        
        for s in strs:
            sorted_key = ''.join(sorted(s))
            if sorted_key not in dic:
                dic[sorted_key] = []
            dic[sorted_key].append(s)
        
        return list(dic.values())

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# sorted examples
# vowels list
pyList = ['e', 'a', 'u', 'o', 'i']
print(sorted(pyList))

# string 
pyString = 'Python'
print(sorted(pyString))

# vowels tuple
pyTuple = ('e', 'a', 'u', 'o', 'i')
print(sorted(pyTuple))

# results
['a', 'e', 'i', 'o', 'u']
['P', 'h', 'n', 'o', 't', 'y']
['a', 'e', 'i', 'o', 'u']

Posted on | In

Description

Given an Android 3x3 key lock screen and two integers m and n, where 1 ≤ m ≤ n ≤ 9, count the total number of unlock patterns of the Android lock screen, which consist of minimum of m keys and maximum n keys.

Rules for a valid pattern:

  1. Each pattern must connect at least m keys and at most n keys.
  2. All the keys must be distinct.
  3. If the line connecting two consecutive keys in the pattern passes through any other keys, the other keys must have previously selected in the pattern. No jumps through non selected key is allowed.
  4. The order of keys used matters.

Example

1
2
3
| 1 | 2 | 3 |
| 4 | 5 | 6 |
| 7 | 8 | 9 |

Invalid move: 4 - 1 - 3 - 6
Line 1 - 3 passes through key 2 which had not been selected in the pattern.

Invalid move: 4 - 1 - 9 - 2
Line 1 - 9 passes through key 5 which had not been selected in the pattern.

Valid move: 2 - 4 - 1 - 3 - 6
Line 1 - 3 is valid because it passes through key 2, which had been selected in the pattern

Valid move: 6 - 5 - 4 - 1 - 9 - 2
Line 1 - 9 is valid because it passes through key 5, which had been selected in the pattern.

Example:
Given m = 1, n = 1, return 9.

Idea

这种棋盘格子之类的问题往往是用dfs来求解的。然后，discussion里面这个哥们给的解挺好的，很清晰：
The basic idea is starting from an arbitrary digit (prev), search all the valid next digit. Use a set/dict (visited) to store all the visited digits. What is the invalid combination? Only two cases.

if prev in {1, 3, 7, 9} and next in {1, 3, 7, 9}, however, (prev + next)/2 not in visited. e.g. 1 -> 7 and 4 not visited.
if prev in {2, 4, 6, 8} and next == 10 - prev, however, 5 is not in visited. e.g. 2->8 and 5 not visited.

Code

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
class Solution(object):
    def numberOfPatterns(self, m, n):
        """
        :type m: int
        :type n: int
        :rtype: int
        """
        visited = {}
        self.res = 0
        self.corner = {1,3,7,9}
        self.mid = {2,4,6,8}
        for i in range(1, 10):
            visited[i] = 1
            self.dfsHelper(visited, 1, m, n, i)
            del visited[i]
        return self.res
        
    # 递归的定义：找出所有合理的next pos
    def dfsHelper(self, visited, keys, m, n, prev):
        # 递归的出口：
        if m <= keys <= n:
            self.res += 1
        if keys == n:
            return

        # 递归的拆解：对1-10遍历，找到valid的next
        for next in range(1, 10):
            if next not in visited:
                if prev in self.corner and next in self.corner and (prev + next)/2 not in visited:
                    continue
                elif prev in self.mid and next == (10 - prev) and 5 not in visited:
                    continue
                visited[next] = 1
                self.dfsHelper(visited, keys + 1, m, n, next)
                del visited[next]
                
#         self.corners = set([1, 3, 7, 9])
#         self.mids = set([2, 4, 6, 8])
#         visited = {}
#         self.res = 0
#         for i in range(1, 10):
#             visited[i] = 1
#             self.dfs(m, n, 1, i, visited)
#             del visited[i]
        
#         return self.res
    
#     # 递归的定义：找出所有合理的next pos
#     def dfs(self, lower, upper, visited_num, prev_n, visited):
#         # 递归的出口：
#         if lower <= visited_num <= upper:
#             self.res += 1
#         if visited_num > upper:
#             return

#         # 递归的拆解：对1-10遍历，找到valid的next
#         for next_n in range(1, 10):
#             if self.isValid(prev_n, next_n, visited):
#                 visited[next_n] = 1
#                 self.dfs(lower, upper, next_n, visited)
#                 del visited[next_n]
    
#     def isValid(self, prev_n, next_n, visited):
#         if prev_n != next_n:
#             if prev_n in self.corners and next_n in self.corners and (prev_n + next_n) / 2 in visited:
#                 return True
#             if prev_n in self.mids and next_n in self.mids and (prev_n + next_n) / 2 in visited:
#                 return True
#         return False

Posted on | In

Description

A matrix is Toeplitz if every diagonal from top-left to bottom-right has the same element. Now given an M x N matrix, return True if and only if the matrix is Toeplitz.

Example

1
2
3
4
5
6
7
8
9
10
11
Input:
matrix = [
  [1,2,3,4],
  [5,1,2,3],
  [9,5,1,2]
]
Output: True
Explanation:
In the above grid, the diagonals are:
"[9]", "[5, 5]", "[1, 1, 1]", "[2, 2, 2]", "[3, 3]", "[4]".
In each diagonal all elements are the same, so the answer is True.
1
2
3
4
5
6
7
8
Input:
matrix = [
  [1,2],
  [2,2]
]
Output: False
Explanation:
The diagonal "[1, 2]" has different elements.

Idea

直接遍历，不过是要check遍历元素和斜对的元素是不是一样

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution(object):
    def isToeplitzMatrix(self, matrix):
        """
        :type matrix: List[List[int]]
        :rtype: bool
        """
        if not matrix or len(matrix) == 0:
            return False
        
        rows = len(matrix)
        cols = len(matrix[0])
        
        for r in range(rows):
            for c in range(cols):
                if (r + 1 <= rows -1 and c + 1 <= cols - 1) and matrix[r][c] != matrix[r + 1][c + 1]:
                    return False
        
        return True

Posted on | In

Description

Given a non-empty binary search tree and a target value, find the value in the BST that is closest to the target.

Example

Given root = {1}, target = 4.428571, return 1.

Idea

思路很简单，就是找到通过检索BST找到upper bound和lower bound，最后在比较谁是离得最近的。upper bound的意思是在整棵树里面，比target小却最大的数，lower bound的意思是在整棵树里面比target大的最小的数。这个大小关系是，进一步递归检索的关键。

Code

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
70
"""
Definition of TreeNode:
class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left, self.right = None, None
"""

class Solution:
    """
    @param root: the given BST
    @param target: the given target
    @return: the value in the BST that is closest to the target
    """
    def closestValue(self, root, target):
        # write your code here
        if root is None:
            return
        
        lower_node = self.lower_bound(root, target)
        upper_node = self.upper_bound(root, target)
        
        if lower_node is None:
            return upper_node.val

        if upper_node is None:
            return lower_node.val    
    
        if lower_node and upper_node:
            if target - lower_node.val > upper_node.val - target:
                return upper_node.val
            else:
                return lower_node.val
            
        return None
        
    
    # find the node with the largest value that smaller than target
    def lower_bound(self, root, target):
        if root is None:
            return None
        
        # the expect val should be smaller than or equal to target
        if root.val > target:
            return self.lower_bound(root.left, target)
        
        # the largest val
        lower_node = self.lower_bound(root.right, target)
        if lower_node:
            return lower_node
        
        # if lower_node is None, the there's no node larger than root, so return root
        return root
    
    
    # find the node with the smallest value that larger than or equal to target
    def upper_bound(self, root, target):
        if root is None:
            return None
        
        # the expect val should be larger than or equal to target
        if root.val < target:
            return self.upper_bound(root.right, target)
        
        # the smallest val
        upper_node = self.upper_bound(root.left, target)
        if upper_node:
            return upper_node
            
        return root

Posted on | In

Description

Given two integers n and k, return all possible combinations of k numbers out of 1 … n.

Example

Given 

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

Code

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
class Solution:
    """
    @param n: Given the range of numbers
    @param k: Given the numbers of combinations
    @return: All the combinations of k numbers out of 1..n
    """
    def combine(self, n, k):
        # write your code here
        self.res = []
        tmp = []
        self.dfs(n, k, 1, 0, tmp)
        return self.res
        
    # 递归的定义：在 [1,2...n] 中找到所有以 tmp 开头的的集合，并放到 res里面
    # cur_start_pos: 表示当前要开始的位置
    # visited_num: 表示已经遍历过的数目
    def dfs(self, n, k, cur_start_pos, visited_num, tmp):
        # 递归的出口:
        if visited_num == k:
            self.res.append(tmp[:])
            return
        # 递归的拆解：
        for i in range(cur_start_pos, n + 1):
            # 将当前的element放在tmp set里面: [1] -> [1, 2]
            tmp.append(i)
            # 进入下一层: n = 4, k = 2, next_start_pos = i + 1 = 3 注意是在tmp最后的一个元素后面开始, visited_num_now = 2, 
            self.dfs(n, k, i + 1, visited_num + 1, tmp)
            # 回溯: [1, 2] -> [1]
            tmp.pop()

Posted on | In

来到CMU，看到了很多高山，常常心生攀爬的欲望，但是每每心生怯懦。就像动漫overload里面的人类强者布莱恩面对吸血鬼始祖夏尔提亚那样，有时候会心生绝望，自己毕生淬炼的一击也只能碰到人家的指甲盖。也许，只是自己太希望自己变得更强了，太希望能和他们一起交流一起在一个平台上共事。我不知道有生之年能不能做到，之前也有过一些机会，但是自己也没有好好把握，同时也走了一些弯路。但是不管怎么样，我还是找寻到了自己的目标，自己的一个方向，来到了这里。人生还有好几十年，自然不能放弃。也许，在overload第二季一样，对于布莱恩来说，他用自己的方式，伤到了夏尔提亚的指甲盖，突破了自己。但，也许更适合自己的想法就是像克莱姆一样，不管自己天赋如何，向强者学习，走好自己的步子，去保护他的公主。总之，我会一直努力，也许能看到你们的背影，也许也能触及到你们的背影。总之，能在这里遇到你们，自己真的是太幸福了。期待未来的自己能和你们再次相遇。



Posted on | In

接下来我开始解读，这篇论文的code

Network Structure and Training

Discriminator

For the discriminator, we use an architecture similar to but utilize all fully-convolutional lay- ers to retain the spatial information.
总是来说就是，5层卷积网络，kernel是4 x 4 stride是2，channel是{64, 128, 256, 512, 1}。
除了最后一层卷积层，其他所有层都是用参数为0.2的leaky ReLU。在最后一层卷积层之后加了一个up-sampling的层，使得最后一层和输入图片的大小是一样的。他们没有使用batch-normalization层，因为他们用小的batch size一起训练判别器和分割网络。(?)

  • batch normalization:

Segmentation Network

他们用DeepLab-v2 和 ResNet-101来作为他们分割的baseline，由于memory的问题，他们没有使用multi-scale。
他们去掉了最后的分类的一层，然后将最后的两层卷积stride从2改成1。这使得输出的feature maps是输入图片大小的1/8。为了使这个更大，他们在conv4和conv5用了stride分别是2，4的dilated conv。这后面又用了Atrous Spatial Pyramid Pooling (ASPP)作为最后的分类器。在ASPP后面，他们也采用了输出的是softmax的up-sampling层，这层输出的大小和输入的图片大小也是一样的。

  • ASPP:

Multi-level Adaptation Model

上面的构成了他们single-level的网络结构。为了构建multi-level的结构，他们将conv4的feature map和一个作为辅助分类器的ASPP模块相结合。和single-level类似，这里面也加了一个同样结构的判别器来进行对抗学习。如图：

Train

作者发现，将segmentation network和discriminitor一起训练效率会比较高。
对源域将图片$I_s$向前传最后得到$P_s$，以及优化$L_{seg}$。对于目标域，我们将得到的$P_t$和$P_s$一起输入到判别器里面，然后优化$L_{d}$。此外，对于$P_t$，我们还需要计算对抗损失$L_{ad}$。

Loss Function

  • whole objective:
    $L(I_s, I_t) = L_{seg}(I_s) + \lambda L_{adv}(I_t)$

    • $L_{seg}(I_s)$
      cross-entropy loss using ground truth annotations in the source domain
    • $L_{adv}$
      对抗损失，用来使得源域的预期的数据分布和目标域相近
    • $\lambda_{abv}$
      这个weight用来平衡这两个loss

  • discriminitor:

    • segmentation softmax output:
      $P = G(I) \in R^{HxWxC}$, 这里C是种类数，这里C是19

    • cross-entropy loss：
      我们将P传到全卷积的判别器D里面：$L_d(P) = - \sum_{h, w}((1 - z)log(D(P)^{(h,w,0)})) + zlog(D(P)^{(h,w,1)})$，这个是binary cross entropy，这里z = 0，表示来自target，z = 1表示来自source

  • segmentation network:

    • segmentation loss:
      在源域的话我们正常训练，还是由cross-entropy loss来定义：$L_{seg}(I_s) = -\sum_{h, w}\sum_{c \in C}Y_s^{h,w,c}log(P_s^{(h,w,c)})$
    • adversarial loss：
      在目标域，我们的对抗损失是：$L_{adv}(I_t) = -\sum_{h,w}log(D(G(I_t)))^{(h,w,1)}$，这个损失是用来欺骗判别器的，使得两者的预期的概率的一致

  • multi-level:

    • multi-level loss
      就是在low-level的feature space里面加上上面的loss，也不是很难理解：
      $L_{I_s, I_t} = \sum_i \lambda_i^{seg}L^i_{seg}(I_s) + \sum_i \lambda^i_{adv}L_{adv}^i(I_t)$，i表示第几层网络。

Network Code

Discriminitor

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
import torch.nn as nn
import torch.nn.functional as F
class FCDiscriminator(nn.Module):
	def __init__(self, num_classes, ndf = 64):
		super(FCDiscriminator, self).__init__()

		self.conv1 = nn.Conv2d(num_classes, ndf, kernel_size=4, stride=2, padding=1)
		self.conv2 = nn.Conv2d(ndf, ndf*2, kernel_size=4, stride=2, padding=1)
		self.conv3 = nn.Conv2d(ndf*2, ndf*4, kernel_size=4, stride=2, padding=1)
		self.conv4 = nn.Conv2d(ndf*4, ndf*8, kernel_size=4, stride=2, padding=1)
		self.classifier = nn.Conv2d(ndf*8, 1, kernel_size=4, stride=2, padding=1)

		self.leaky_relu = nn.LeakyReLU(negative_slope=0.2, inplace=True)
		#self.up_sample = nn.Upsample(scale_factor=32, mode='bilinear')
		#self.sigmoid = nn.Sigmoid()

	def forward(self, x):
		x = self.conv1(x)
		x = self.leaky_relu(x)
		x = self.conv2(x)
		x = self.leaky_relu(x)
		x = self.conv3(x)
		x = self.leaky_relu(x)
		x = self.conv4(x)
		x = self.leaky_relu(x)
		x = self.classifier(x)
		#x = self.up_sample(x)
		#x = self.sigmoid(x) 

		return x

有了上面的描述，判别器的网络还是很清楚的。

Segmentation Network

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class ResNetMulti(nn.Module):
    def __init__(self, block, layers, num_classes):
        self.inplanes = 64
        super(ResNetMulti, self).__init__()
        self.conv1 = nn.Conv2d(3, 64, kernel_size=7, stride=2, padding=3,
                               bias=False)
        self.bn1 = nn.BatchNorm2d(64, affine=affine_par)
        for i in self.bn1.parameters():
            i.requires_grad = False
        self.relu = nn.ReLU(inplace=True)
        self.maxpool = nn.MaxPool2d(kernel_size=3, stride=2, padding=1, ceil_mode=True)  # change
        self.layer1 = self._make_layer(block, 64, layers[0])
        self.layer2 = self._make_layer(block, 128, layers[1], stride=2)
        self.layer3 = self._make_layer(block, 256, layers[2], stride=1, dilation=2)
        self.layer4 = self._make_layer(block, 512, layers[3], stride=1, dilation=4)
        self.layer5 = self._make_pred_layer(Classifier_Module, 1024, [6, 12, 18, 24], [6, 12, 18, 24], num_classes)
        self.layer6 = self._make_pred_layer(Classifier_Module, 2048, [6, 12, 18, 24], [6, 12, 18, 24], num_classes)

前面应该是对resnet的结构的继承吧，后面的layer5，和layer6应该就是前面说的ASPP的classifier了，这两个分别之后参与adaptation module的部分。

Train Code

Train G

类似train 原本的GAN，这里train的G其实就是segmentation network

Train with source

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
_, batch = trainloader_iter.next()
images, labels, _, _ = batch
images = Variable(images).cuda(args.gpu)

pred1, pred2 = model(images)
pred1 = interp(pred1)
pred2 = interp(pred2)

loss_seg1 = loss_calc(pred1, labels, args.gpu)
loss_seg2 = loss_calc(pred2, labels, args.gpu)
loss = loss_seg2 + args.lambda_seg * loss_seg1

# proper normalization
loss = loss / args.iter_size
loss.backward()
loss_seg_value1 += loss_seg1.data.cpu().numpy()[0] / args.iter_size
loss_seg_value2 += loss_seg2.data.cpu().numpy()[0] / args.iter_size

train with source这里的loss就是：$\sum_i \lambda_i^{seg}L^i_{seg}(I_s)$，$L_{seg}(I_s) = -\sum_{h, w}\sum_{c \in C}Y_s^{h,w,c}log(P_s^{(h,w,c)})$

Train with target

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
_, batch = targetloader_iter.next()
images, _, _ = batch
images = Variable(images).cuda(args.gpu)

pred_target1, pred_target2 = model(images)
pred_target1 = interp_target(pred_target1)
pred_target2 = interp_target(pred_target2)

D_out1 = model_D1(F.softmax(pred_target1))
D_out2 = model_D2(F.softmax(pred_target2))

loss_adv_target1 = bce_loss(D_out1,
                            Variable(torch.FloatTensor(D_out1.data.size()).fill_(source_label)).cuda(
                                args.gpu))

loss_adv_target2 = bce_loss(D_out2,
                            Variable(torch.FloatTensor(D_out2.data.size()).fill_(source_label)).cuda(
                                args.gpu))

loss = args.lambda_adv_target1 * loss_adv_target1 + args.lambda_adv_target2 * loss_adv_target2
loss = loss / args.iter_size
loss.backward()
loss_adv_target_value1 += loss_adv_target1.data.cpu().numpy()[0] / args.iter_size
loss_adv_target_value2 += loss_adv_target2.data.cpu().numpy()[0] / args.iter_size

train target对应的就是：$\sum_i \lambda^i_{adv}L_{adv}^i(I_t)$，$L_{adv}(I_t) = -\sum_{h,w}log(D(G(I_t)))^{(h,w,1)}$

Train D

Train with source

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# labels for adversarial training
source_label = 0

pred1 = pred1.detach()
pred2 = pred2.detach()

D_out1 = model_D1(F.softmax(pred1))
D_out2 = model_D2(F.softmax(pred2))

loss_D1 = bce_loss(D_out1,
                    Variable(torch.FloatTensor(D_out1.data.size()).fill_(source_label)).cuda(args.gpu))

loss_D2 = bce_loss(D_out2,
                    Variable(torch.FloatTensor(D_out2.data.size()).fill_(source_label)).cuda(args.gpu))

loss_D1 = loss_D1 / args.iter_size / 2
loss_D2 = loss_D2 / args.iter_size / 2

loss_D1.backward()
loss_D2.backward()

loss_D_value1 += loss_D1.data.cpu().numpy()
loss_D_value2 += loss_D2.data.cpu().numpy()

$L_d(P) = - \sum_{h, w}((1 - z)log(D(P)^{(h,w,0)})) + zlog(D(P)^{(h,w,1)})$，z = 0

Train with target

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# labels for adversarial training
target_label = 1

pred_target1 = pred_target1.detach()
pred_target2 = pred_target2.detach()

D_out1 = model_D1(F.softmax(pred_target1))
D_out2 = model_D2(F.softmax(pred_target2))

loss_D1 = bce_loss(D_out1,
                    Variable(torch.FloatTensor(D_out1.data.size()).fill_(target_label)).cuda(args.gpu))

loss_D2 = bce_loss(D_out2,
                    Variable(torch.FloatTensor(D_out2.data.size()).fill_(target_label)).cuda(args.gpu))

loss_D1 = loss_D1 / args.iter_size / 2
loss_D2 = loss_D2 / args.iter_size / 2

loss_D1.backward()
loss_D2.backward()

loss_D_value1 += loss_D1.data.cpu().numpy()
loss_D_value2 += loss_D2.data.cpu().numpy()

$L_d(P) = - \sum_{h, w}((1 - z)log(D(P)^{(h,w,0)})) + zlog(D(P)^{(h,w,1)})$，z = 1

Posted on | In

leetcode里面考察很多的算法知识：

  1. 基本的数据结构：
    queue, stack, heap, tree, graph，linked-list，trie
  2. 一些基本的算法：
    sort
    binary search
  3. 一些高级点的算法：
    dp，bfs，dfs
  4. 别忘了位运算，和‘2’有关的时候很有用，可以简化问题
    边刷，边整理和总结

Posted on | In

莫烦python也给了pytorch的GAN版本：
然后莫烦的全部代码在这里

hyper parameter

新手画家 (Generator) 在作画的时候需要有一些灵感 (random noise), 我们这些灵感的个数定义为 N_IDEAS. 而一幅画需要有一些规格, 我们将这幅画的画笔数定义一下, N_COMPONENTS 就是一条一元二次曲线(这幅画画)上的点个数. 为了进行批训练, 我们将一整批话的点都规定一下(PAINT_POINTS).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
import torch
import torch.nn as nn
import numpy as np
import matplotlib.pyplot as plt

torch.manual_seed(1) # reproducible
np.random.seed(1)

# hyper parameter
BATCH_SIZE = 64
LR_G = 0.0001 
LR_D = 0.0001
N_IDEAS = 5
ART_COMPONENTS = 15
PAINT_POINTS = np.vstack([np.linspace(-1, 1, ART_COMPONENTS) for _ in range(BATCH_SIZE)])

著名画家的画

我们需要有很多画是来自著名画家的(real data), 将这些著名画家的画, 和新手画家的画都传给新手鉴赏家, 让鉴赏家来区分哪些是著名画家, 哪些是新手画家的画. 如何区分我们在后面呈现. 这里我们生成一些著名画家的画 (batch 条不同的一元二次方程曲线).

1
2
3
4
5
def artist_works(): # real target
    a = np.random.uniform(1, 2, size = BATCH_SIZE)[:, np.newaxis]
    paintings = a * np.power(PAINT_POINTS, 2) + (a - 1)
    paintings = torch.from_numpy(paintings).float()
    return paintings

神经网络

这里会创建两个神经网络, 分别是 Generator (新手画家), Discriminator(新手鉴赏家). G 会拿着自己的一些灵感当做输入, 输出一元二次曲线上的点 (G 的画).

D 会接收一幅画作 (一元二次曲线), 输出这幅画作到底是不是著名画家的画(是著名画家的画的概率).

1
2
3
4
5
6
7
8
9
10
11
12
G = nn.Sequential(                      # Generator
    nn.Linear(N_IDEAS, 128),            # random ideas (could from normal distribution)
    nn.ReLU(),
    nn.Linear(128, ART_COMPONENTS),     # making a painting from these random ideas
)

D = nn.Sequential(                      # Discriminator
    nn.Linear(ART_COMPONENTS, 128),     # receive art work either from the famous artist or a newbie like G
    nn.ReLU(),
    nn.Linear(128, 1),
    nn.Sigmoid(),                       # tell the probability that the art work is made by artist
)

训练

接着我们来同时训练 D 和 G. 训练之前, 我们来看看G作画的原理. G 首先会有些灵感, G_ideas 就会拿到这些随机灵感 (可以是正态分布的随机数), 然后 G 会根据这些灵感画画. 接着我们拿着著名画家的画和 G 的画, 让 D 来判定这两批画作是著名画家画的概率.

1
2
3
4
5
6
7
for step in range(10000):
    artist_paintings = artist_works()           # real painting from artist
    G_ideas = torch.randn(BATCH_SIZE, N_IDEAS)    # random ideas
    G_paintings = G(G_ideas())                  # fake painting from G (random ideas)

    prob_artist0 = D(artist_paintings)          # D try to increase this prob
    prob_artist1 = D(G_paintings)               # D try to reduce this prob

然后计算有多少来之画家的画猜对了, 有多少来自 G 的画猜对了, 我们想最大化这些猜对的次数. 这也就是 log(D(x)) + log(1-D(G(z)) 在论文中的形式. 而因为 torch 中提升参数的形式是最小化误差, 那我们把最大化 score 转换成最小化 loss, 在两个 score 的合的地方加一个符号就好. 而 G 的提升就是要减小 D 猜测 G 生成数据的正确率, 也就是减小 D_score1.

1
2
D_loss = -torch.mean(torch.log(prob_artist0) + torch.log(1. - prob_artist1))
G_loss = torch.mean(torch.log(1. - prob_artist1))

最后我们在根据 loss 提升神经网络就好了.

1
2
3
4
5
6
7
opt_D.zero_grad()
D_loss.backward(retain_graph=True)              # retain_graph 这个参数是为了再次使用计算图纸
opt_D.step()

opt_G.zero_grad()
G_loss.backward()
opt_G.step()

之后就是，开始整理总结最近在看的那篇论文作者代码的解读了。