历史

• java 1.0 中没有HashMap，有HashTable
• java 1.2 引入HashMap
• java 7 基于哈希表的实现
• java 8 采用的

hash

数据结构

1
2

transient Node<K,V>[] table;
transient Set<Map.Entry<K,V>> entrySet;

hash过程

流程

1. 对key计算hashcode
2. 将hashcode映射到有限bucket空间
3. 在相应的bucket内，存储或查询相应的key

计算hashcode

java7

1
2
3
4
5
6
7
8
9

final int hash(Object k) {
    int h = hashSeed;
    if (0 != h && k instanceof String) {
        return sun.misc.Hashing.stringHash32((String) k); // 麻蛋
    }
    h ^= k.hashCode();  // 按位异或
    h ^= (h >>> 20) ^ (h >>> 12);  // “扰动函数”。Java 8中这步已经简化了，只做一次16位右位移异或混合，而不是四次，但原理是不变的。
    return h ^ (h >>> 7) ^ (h >>> 4); // >>> 无符号右移运算符
}

基础知识:

1. hashSeed 随机数的种子，详见..
2. ^ 按位异或。作用:
3. >>> 无符号右移运算符
   左移的规则：丢弃高位，0补低位
   右移的规则：丢弃低位，高位的空位补符号位，即正数补零，负数补1

右移的偏移量20，12，7，4是怎么来的呢？因为Java中对象的哈希值都是32位的，所以这几个数应该
就是把高位与低位做异或运算，

再看一下String类中hashcode的计算

1
2
3
4
5
6
7
8
9
10
11

public int hashCode() {
    int h = hash;
    if (h == 0 && value.length > 0) {
        char val[] = value;
        for (int i = 0; i < value.length; i++) {
            h = 31 * h + val[i];  // 为什么取素数？为什么取31？
        }
        hash = h;
    }
    return h;
}

在存储数据计算hash地址的时候，我们希望尽量减少有同样的hash地址，所谓“冲突”。如果使用相同hash地址的数据过多，那么这些数据所组成的 hash链就更长，从而降低了查询效率！所以在选择系数的时候要选择尽量长的系数并且让乘法尽量不要溢出的系数，因为如果计算出来的hash地址越大，所 谓的“冲突”就越少，查找起来效率也会提高。

使用31的原因可能是为了更好的分配hash地址，并且31只占用5bits！

在java乘法中如果数字相乘过大会导致溢出的问题，从而导致数据的丢失.
而31则是素数（质数）而且不是很长的数字，最终它被选择为相乘的系数的原因不过与此！

分配hashcode到bucket

hashcode的取值空间太大，不能作为直接存储地址。因此要把hashcode分配到一定数量的bucket中，取值[0, capacity‐1]。

为了使每个key都能在冲突最小的情况下映射到[0,capacity)，通常有两种做法：

1. capacity为素数，index = hashCode(key) mod capacity
2. capacity为2的倍数，index = hashCode(key) & (capacity‐1)

java7中

1
2

int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 16
index = hashCode(key) & (capacity‐1); // 映射到0,capacity-1之间(类似mod)

普通的哈希算法（也称硬哈希）采用简单取模的方式，将机器进行散列，这在cache环境不变的情况下能取得让人满意的结果，但是当cache环境动态变化时，这种静态取模的方式显然就不满足单调性的要求（当增加或减少一台机子时，几乎所有的存储内容都要被重新散列到别的缓冲区中）。

存储或查询 (get put)

java7的get

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

final Entry<K,V> getEntry(Object key) {
    if (size == 0) {
        return null;
    }
    int hash = (key == null) ? 0 : hash(key);
    for (Entry<K,V> e = table[indexFor(hash, table.length)];
         e != null;
         e = e.next) {
        Object k;
        if (e.hash == hash &&
            ((k = e.key) == key || (key != null && key.equals(k))))
            return e;
    }
    return null;
}

java7的put

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

public V put(K key, V value) {
    if (table == EMPTY_TABLE) {
        inflateTable(threshold);
    }
    if (key == null)
        return putForNullKey(value);
    int hash = hash(key);
    int i = indexFor(hash, table.length);
    for (Entry<K,V> e = table[i]; e != null; e = e.next) {
        Object k;
        if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
            V oldValue = e.value;
            e.value = value;
            e.recordAccess(this);
            return oldValue;
        }
    }
    modCount++;
    addEntry(hash, key, value, i);
    return null;
}

rehash

java7的rehash

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

void resize(int newCapacity) {
    Entry[] newTable = new Entry[newCapacity]; // 创建新的entry array
    transfer(newTable, initHashSeedAsNeeded(newCapacity));
    table = newTable;
    threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}

// Transfers all entries from current table to newTable.
void transfer(Entry[] newTable, boolean rehash) {
    int newCapacity = newTable.length;
    for (Entry<K,V> e : table) {
        while(null != e) {
            Entry<K,V> next = e.next;
            if (rehash) {
                e.hash = null == e.key ? 0 : hash(e.key);
            }
            int i = indexFor(e.hash, newCapacity);
            e.next = newTable[i];
            newTable[i] = e;
            e = next;
        }
    }
}

复杂度？

一致性？

其他

1
2
3
4

 //  默认的平衡因子为0.75。过高的因子会降低存储空间但是查找的时间就会增加。
int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
int MAXIMUM_CAPACITY = 1 << 30;   // 哈希表容量（也就是buckets或slots大小）
float DEFAULT_LOAD_FACTOR = 0.75f;

NUll keys always map to hash 0, thus index 0

横向对比

• Hashtable
• LinkedHashMap
• TreeMap
• EnumMap

VS Hashtable

HashMap 不是线程安全的

HashMap 是 HashTable 的轻量级实现，他们都完成了Map 接口，主要区别在于 HashMap 允许 null key 和 null value，由于非线程安全，效率上可能高于 Hashtable。

VS

revisit

设计

参考

• HashMap.java | java7
• HashMap.java | java8

思考题

• hashcode的计算？
• Null key的处理？为什么
• 常量
  • modCount的作用？
  • loadFactor的作用？
  • 为什么容量必须为2的指数倍（默认为16）？
  • 超容后，reshash的复杂度是多少？怎样降低复杂度？怎样保证一致性？
  • 容量超过Integer.MAX_VALUE怎么办？
  • hashSeed的影响？
• 并发的影响？见
• 如何做到key的排序？见
• 为什么放到util呢？ Map类的操作对象是其他类，所以也属于工具类。当然也可以理解为普通类(封装类、组合类)

答案在文中寻找

简介

 结构风险（structural risk）：描述模型与训练样本的拟合程度，以及模型的复杂程度。

正则化的由来
　　有几种角度来看待正则化(Regularization)，它符合奥卡姆剃刀(Occam’s razor)原理：在所有可能选择的模型中，能够很好地解释已知数据并且十分简单的才是最好的模型。从贝叶斯估计的角度来看，正则化项对应于模型的先验概率。还有个说法就是，正则化是结构风险最小化策略的实现，是在经验风险上加一个正则化项(regularization term)或惩罚项(penalty term)或权重衰减项(weight decay term)。

　　高维统计分析模型通常都是稀疏模型，即真正有效的变量只占一小部分，绝大多数变量都是噪声数据。因此当模型的参数过多时，不仅无法提高模型的解释力，反而会降低模型的解释力。
　　在这个背景下，统计学家提出了各种各样的变量选择方法来筛选模型中重要的解释变量，从而防止过拟合问题。其中正则化是最常用的一种方法，而正则化方法中最常见的就是L0, L1 和L2范数。

　　正则化方法的思想：处理最优化函数问题时，在目标函数中加入对参数的约束惩罚项，从而达到简化模型的目的。

常见的结构风险

L0范数：就是指矩阵中非零元素的个数，很显然，在损失函数后面加上L0正则项就能够得到稀疏解，但是L0范数很难求解，是一个NP问题，因此转为求解相对容易的L1范数（l1能够实现稀疏性是因为l1是L0范数的最优凸近似）

L1

L1正则化使得模型更加稀疏，

L1范数：矩阵中所有元素的绝对值的和。损失函数后面加上L1正则项就成了著名的Lasso问题（Least Absolute Shrinkage and Selection Operator），L1范数可以约束方程的稀疏性，该稀疏性可应用于特征选择：
比如，有一个分类问题，其中一个类别Yi(i=0,1),特征向量为Xj（j=0,1~~~1000），那么构造一个方程
Yi = W0X0+W1X1···WjXj···W1000X1000+b;
其中W为权重系数，那么通过L1范数约束求解，得到的W系数是稀疏的，那么对应的X值可能就是比较重要的，这样就达到了特征选择的目的

L1 正则化在零点不可微，因此权重以趋近于零的常数因子增长。很多神经网络在权重衰减公式中使用一阶步骤来解决非凸 L1 正则化问题。

elastic net 的提出 是为了 可以解决feature之间的 高相关性 问题，单纯Lasso 一般会在一个 高相关性 的 特征group 里面选取一个显著特征， zou 的paper 里面有相关证明。 当然解决 高相关性的方法还有 group lasso ， general fused lasso 等
从几何解释来讲 elastic net 很像 L1 到 L2 之间一个 penalty， 但不同之处在于 elastic net 具有 L1 的特性，sparsity， 函数并不是smooth 的。这个具体可以参考 Element of statistical learning 的第三章。

https://www.zhihu.com/question/38081976

L2

二范数，等价于Gauss共轭先验

L2使得模型参数更趋近于0，提高泛化能力

稀疏约束

普通参数的稀疏约束

一范数，等价于Laplace共轭先验

归一化后的参数稀疏

$$P=(p_1,p_2…p_n)$$

• 共轭先验是狄利克雷分布，可通过先验参数控制稀疏程度。

• 可用二范数

• 可用1范数。

其他约束

1. 正交约束：
   AA’ = 对角阵

2. 单位正交约束：
   AA’ = I

3. 另外sum=1 + 平方和=1
   这就是稀疏约束。

AA’为对角阵

|AA’-E|_2

参考

http://www.cnblogs.com/stevenlk/p/6247992.html

生物学背景

神经科学（英语：neuroscience），又称神经生物学，是专门研究神经系统的结构、功能、发育、演化、遗传学、生物化学、生理学、药理学及病理学的一门科学。对行为及学习的研究都是神经科学的分支。

对人脑研究是个跨领域的范畴，当中涉及分子层面、细胞层面、神经小组、大型神经系统，如视觉神经系统、脑干、脑皮层。

最高层次的研究就是结合认知科学成为认知神经科学，其专家被称为认知心理学家。一些研究人员相信认知神经科学提供对思维及知觉的全面了解，甚至可以代替心理学。

神经元结构

树突 细胞体 轴突 细胞核 兰氏结 突触 施旺细胞 髓鞘
典型神经元的结构(来自wikipedia)

• 树突为神经元的输入通道，其功能是将自其他神经元所接收的动作电位（电信号）传送至细胞本体。其他神经元的动作电位借由位于树突分支上的多个突触传送至树突上。与长度可达约1米的轴突相比，树突通常较短。

• 轴突（Axon）由神经元组成，即神经细胞之细胞本体长出突起，功能为传递细胞本体之动作电位至突触。

生物学功能

• 陈述性记忆：对事件、人物等有意识回忆，相对容易记住和忘记

• 非陈述性记忆：对抽象、感知、动作和习惯等无意识操作

• 突触可塑性（Synaptic plasticity）指神经细胞间的连接，即突触，其连接强度可调节的特性。突触可塑性的产生有多种原因，例如：突触中释放的神经递质数量的变化，细胞对神经递质的反应效率。突触可塑性被认为是构成记忆和学习的重要神经化学基础。

脉冲

Biological neurons use short and sudden increases in voltage to send information.
action potentials, spikes or pulses.

SNN 脉冲神经网络

信息承载

SNN的信息承载，仅仅是靠脉冲频率吗？等价于二值的普通编码吗？

neurons encode information in the timing of single spikes, and not only just in their average
firing frequency.

独特之处

they can encode temporal information in their signals, but therefore do also need different and biologically more plausible rules for synaptic plasticity.

疑问

SNN的图像分类等常见任务上效果怎样？

SNN的优势是什么，独特之处是什么？

一个image怎样转化成脉冲作为网络输入？

firing rate表示信号强弱，单个脉冲有什么意义？

快速搭建

1

$ pip install chatterbot

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

from chatterbot import ChatBot

chatbot = ChatBot(
    'Ron Obvious',
    trainer='chatterbot.trainers.ChatterBotCorpusTrainer'
)

# Train based on the english corpus
chatbot.train("chatterbot.corpus.chinese")

# Get a response to an input statement
chatbot.get_response("你是谁")

后台算法

https://chatterbot.readthedocs.io/en/stable/faq.html#what-kinds-of-machine-learning-does-chatterbot-use

基于搜索和分类

• 搜索
• 分类
  • 利用朴素贝叶斯 判断是否 an input statement meets a particular set of criteria that warrant a response
    
    说的好模糊

倒排索引又叫反向索引

背景

索引数据的规模为TB级。TB相当于1 000 GB，一个1 000 GB的文件是不可想象的。因此将全部索引文件存放在一台主机上，不仅是不合适的，而且是不安全的。这样一旦这个倒排文件损坏，全部服务就会受到很大影响，因此倒排索引的分布式存储技术应运而生了。

大数据遇到的问题

单机的瓶颈

• 存储：索引数据大
• 网络：传输瓶颈(网络负载)，尽量减少网络开销
• 磁盘I/O：

多机需要解决的问题 (集群或分布式)

• 数据倾斜问题
• 可靠性
• 网络
• 查询速度，memory db？如何

策略

如何解决以上各种问题？

• 没什么特别好的办法…就是各种切分索引，然后把结果合并之类的

常见操作

• 重建索引 周期性重建索引
• 基于主索引的前提下，构建辅助索引，用于储存新文档，维护于内存中，当辅助索引达到一定的内存占用时，写入磁盘与主索引进行合并；

种切分索引，然后把结果合并之类的

服务功能的分布式拆分

• 尽量减少网络开销
• 各个子服务应该是无状态的
• 每个子服务都应该是可横向扩展的

分布式 VS 集群

数据的分布式拆分

• 搜索引擎索引分片
• Log

参考 https://juejin.im/entry/58abf9432f301e006bdbc373

常见疑问

切分索引

多机分布式索引一般按照文档编号(docId)或者按照索引词编号(wordId)进行划分。按照DocId划分的结果称为局部倒排文件（Local inverted file）；按照WordId划分的结果称为全局倒排文件（Global inverted file）

1
2
3
4
5
6
7

apple -> 1, 13, 24, 33, 46, 52, 77
banana -> 4, 8, 33, 34, 52, 66, 88
grapes -> 7, 22, 46, 77, 89
pineapple -> 15, 37, 52
delicious -> 24, 34, 46, 77, 89
rotten -> 8, 66
exotic -> 37

按照docid来切分，比如1-100和101-200分在不同的服务器。

按照wordid来切分，比如apple banana分在不同的服务器。

索引的存储结果我们人为能看到的就是segment文件，其实索引文件segment的下层结构就是field域（类似于数据库里面的列名，但是这两个概念区别还是蛮大的，只是拿过来类比），对于每一个field里面存储的就是倒排文件，而我们进行查询的过程时，为了加快查询效率就会制定field域去查询，对于每一个term来说会·去查找字典的一种结构（现在存储结构有FST（英文字典存储结构），前缀树等），因为字典是已经排好序的了，所以这里只需要进行二分查找就可以了，对于每一个term查找到的倒排链进行交集或者并集的合并，在合并的过程若要是按照文本相关性排序（不指定排序股则），就会在合并的过程中会进行相关的score分数计算（例如BM25，或者TF-IDF等一些算法），计算出来的文档会存储在一个top-N的小根堆里面，最后返回给用户。对于倒排链的合并过程交集是一个比较消耗性能的操作，比如lucene对于OR操作的优化比较多，比如说把现在N条倒排链按照长度排序（短的文档在前，长的在后），然后分成两组最短的1条一个组，剩下的N-1条一组，然后对于这两个组进行合并。在OR的合并过程中，可以指定最少有几个term满足要求，这样在前N-1中要是没有满足要求，这样最后一条就不需要在进行合并了。

##

倒排索引，当有100台server，要把索引表

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
71

/*
An inverted index is used to support text search. The inverted index has a record for each term. Each record has the list of documents that the term appears in. Documents are identified by an integer document ID. The list of document IDs is sorted in ascending order. For the purpose of this problem, assume that the only operation performed on the inverted index is intersection to find the documents that contain all terms in the search query.
For example, the inverted index could have the following data.
Term
Document IDs

apple -> 1, 13, 24, 33, 46, 52, 77
banana -> 4, 8, 33, 34, 52, 66, 88
grapes -> 7, 22, 46, 77, 89
pineapple -> 15, 37, 52
delicious -> 24, 34, 46, 77, 89
rotten -> 8, 66
exotic -> 37

Expected results from intersections are as follows:
Terms intersected
Document IDs with all terms

delicious apple -> 24, 46, 77
delicious apple grapes -> 46, 77
apple banana -> 33, 52
We have an inverted index that is very large and requires N servers to "fit". Assume N is 100.
*/




/* This class will be given a list of words (such as might be tokenized
 * from a paragraph of text), and will provide a method that takes two
 * words and returns the shortest distance (in words) between those two
 * words in the provided text.
 * Example:
 *   WordDistanceFinder finder = new WordDistanceFinder(Arrays.asList("the", "quick", "brown", "fox", "quick"));
 *   assert(finder.distance("fox", "the") == 3);
 *   assert(finder.distance("quick", "fox") == 1);
 *
 * "quick" appears twice in the input. There are two possible distance values for "quick" and "fox":
 * 	(3 - 1) = 2 and (4 - 3) = 1.
 * Since we have to return the shortest distance between the two words we return 1.
 */
public class WordDistanceFinder {
    public WordDistanceFinder (List<String> words) {
      Map<String, List<Integer>> map = new HashMap<String, List<Integer>>();
      for(int i = 0; i < words.size(); i++) {
        if(!map.contains(word))
          map.put(word, new ArrayList<Integer>());
        map.get(word).add(i);         
      }
    }

    public int distance (String wordOne, String wordTwo) {
      List<Integer> index1 = map.get(wordOne);
      List<integer> index2 = map.get(wordTwo);
      int i = 0; j = 0;
      int min_distance = map.size();
      while(i < index1.size() && j < index2.size()) {
        ind1 = index1[i];
        ind2 = index[j];
        current_distance = math.abs(ind1 - ind2);
        min_distance = current_distance>min_distance?min_distance:current_distance;

        if(ind1 < ind2) {
          i++;
        } else {
          j++;
        }
      }
      return min_distance;
        // implementation here
    }
}

基础概念

• NN
• 前馈网络: 前馈是相对反馈(backward)，带反馈的网络就构成了环，即有环网络。通常所用到的网络都是前馈网络。
• 感知机
• 多层感知机
• autoencoder
• RBM

答疑

梯度爆炸 梯度消失

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

Q: 梯度消失就是0.9^30≈0.04？梯度爆炸就是1.1的n次方？
   怎样不消失，不爆炸呢？就是1的n次方吗？
A: 是的，ReLU就是这么干的

Q: 那sigmoid和tanh，是不是就彻底被淘汰了？
A: 网络不深可以用，具体情况具体分析
   再说了batch normalization的作用对于mitigate这种情况效果不错

Q: 除了ReLU，还有什么能防止梯度爆炸、梯度消失的策略？
A: 还有一些特殊的网络结果诸如resnet LSTM，也可以防止梯度小时或者爆炸，但不能根本解决

Q: 为什么BN能起到一定的作用？
A: 避免了梯度非常小，或者非常大。将梯度归一化到一个固定范围，相当于他说的消除了柔性
   通过mini-batch来对相应的activation做规范化操作，使得结果（输出信号各个维度）的均值为0，方差为1

Q: 为什么resnet LSTM，能防止梯度爆炸 梯度消失？
A: 因为避免了连乘。

Q: 可以理解bn是集中到标准正态分布范围内，但是网络里用的ReLU抑制负数所以有损失吗？
A:

Q: RNN 为什么会出现 Gradient Vanish？LSTM为什么能防止梯度消失？

激活函数 (activation function)

VGG ResNet都采用ReLU

##

每一次commit都可以选择性的与某个issue关联。比如在 message中添加#n，就可以与第n个 issue 进行关联。
commit message title, #1

官方doc：

• https://guides.github.com/features/issues/
• https://help.github.com/articles/closing-issues-using-keywords/

By prefacing your commits with:

• fix
• fixes: 例如提交messeage为Fixes #45，当commit被merge到master上时，会自动关闭issue 45
• fixed
• close
• closes
• closed
• resolve
• resolves
• resolved

when the commit is merged into master, it will also automatically close the issue.

同时操作多个issue

This closes #34, closes #23, and closes example_user/example_repo#42

常用标签

Labels，标签。包括 enhancement、bug、invalid 等，表示 issue 的类型，解决的方式。除了自带的以外，也可以去自定义。

Milestone，里程碑。几经修改后，它现在已经与git tag和Github release区分开来，仅仅作为issue的一个集合。通常用来表示项目的一个阶段，比如demo、release等，保护达成这些阶段需要解决的问题。有时候，也会与版本计划重合，比如v1.0、v2.0等。issue不能设置截止时间，但是milestone可以。

Assignee，责任人。指定这个 issue 由谁负责来解决。

常见疑问

Logistic

什么意思？对数？逻辑？

Regression

明明是Classification的算法，为什么叫Regression

LR是线性分类器还是非线性的？

误区一：逻辑回归的模型引入了sigmoid函数映射，所以是非线性分类器

1. 逻辑斯蒂的sigmoid是似然函数，即一种loss，跟是不是线性模型没关系。所有的似然函数都是非线性函数，照这个逻辑，所有的分类器就都是非线性分类器了。

2. 判断一个分类器是不是线性，要看分界面。比如加kernel后的分界面就是非线性。logistic的分界面是 y=wx+b, 是线性的。

3. 神经网络中间层的sigmoid是映射，跟逻辑斯蒂回归的sigmoid不是一个东西。最后一层softmax才是LR分类器。

总结

LR可以看成 “只有一层softmax层的神经网络”。增加隐层数，就是增加了非线性映射。

如何用LR解决非线性分类的问题

• 自己定义这个非线性映射
  • 这样也就不叫LR了
  • https://zhuanlan.zhihu.com/p/20545718
• 用kernel
  • 和svm是不一样的，svm使用kernel不容易过拟合，而lr更容易过拟合。因为在lr里面vc dimension是随变量数线性增长的，而在svm中vc dimension随变量数对数级增长 (没看懂，知乎小活泼)
  • 通常使用的kernel都是隐式的，也就是找不到显式地把数据从低维映射到高维的函数，而只能计算高维空间中数据点的内积。https://www.zhihu.com/question/29385169

卷积在深度学习中的应用

Convolutional neural networks therefore constitute a very useful tool for machine learning practitioners. However, learning to use CNNs for the first time is generally an intimidating experience.

CNN为什么work？

• 局部连接代替全连接，& 权值共享
• pooling层，
• 是

发展

• 2012年， 基于深度学习CNN网络的AlexNet在ILSVRC竞赛的ImageNet上大放异彩
• 检测: 2014年Ross Girshick利用CNN成功取代了HOG、DPM等特征提取， ross等人把目标检测分成了三个步骤，首先是对图像提取detection proposal，其实就是图像中一些可能是检测物体的区域，然后使用cnn对这些proposal进行特征提取，最后用svm对这些提取到的特征进行分类，从而完成检测的任务，这是 Two-stage object detectors鼻祖。

卷积的类型

简单卷积

卷积核为3、步幅为1和带有边界扩充的二维卷积结构

• 卷积核大小（Kernel Size）：定义了卷积操作的感受野。在二维卷积中，通常设置为3，即卷积核大小为3×3。
• 步幅（Stride）：定义了卷积核遍历图像时的步幅大小。其默认值通常设置为1，也可将步幅设置为2后对图像进行下采样，这种方式与最大池化类似。
• 边界扩充（Padding）：定义了网络层处理样本边界的方式。当卷积核大于1且不进行边界扩充，输出尺寸将相应缩小；当卷积核以标准方式进行边界扩充，则输出数据的空间尺寸将与输入相等。
• 输入与输出通道（Channels）：构建卷积层时需定义输入通道I，并由此确定输出通道O。这样，可算出每个网络层的参数量为I×O×K，其中K为卷积核的参数个数。例，某个网络层有64个大小为3×3的卷积核，则对应K值为 3×3 =9。

group conv

对channel 分group，然后各group独立，最后再合并。

关于group之间是否共享卷积核？以及影响？

实例

AlexNet中采用group conv的初衷是为了利用多GPU。为了减少GPU之间的交互带来的速度影响，只在特定的层才有共享权重

最小 卷积核

最小的卷积核，在1维卷积中是kernel size为1的卷积，二维卷积中是kernel size为1*1的卷积。

这种卷积又叫Pointwise convolution，即feature map上的每个point采用相同的卷积操作。

作用

在channel上升维、降维。

1*1 卷积 (二维卷积)

针对[w,h,in_channel]的输入，进行 1,1二维卷积

$$
[w,h,in] \xrightarrow[1 \times 1 \times in \times out]{conv2d} [w,h,out]
$$

1*1卷积并未对图像尺寸进行调整，仅仅是channel之间的融合。

当$out_channel > in_channel$时，起到升维的作用；反之，则起到降维的作用。

1*1kernel广泛用于NIN、GoogLeNet、ResNet

注意

• 缺陷: 1*1卷积并未考虑空间邻域的信息，仅仅是channel之间的整合。所以一般会配合
• 优势: 计算量小，参数少

实战架构:

1. 构造bottleneck架构:
   • 由于1*1卷积方便维度变换，很多网络构造bottleneck架构，即高维的IO，低维的middle，目的是在低维下进行复杂运算，减少计算量。
   • 实例: NIN, GoogLeNet, ResNet
2. 卷积的分解
   • 所有的depthwise seprable convolution

对应一维卷积，就是kernel_size 为1卷积

最大卷积核 - 全卷积

全卷积(FCN)

Transposed Convolutions

可分离卷积、分解卷积

Separable Convolution，Factorized Convolutions
应该是一个意思吧？

• Separable
  • 即分离(split)的意思，将传统的一层conv分离为两层，一层用于filtering，一层用于combining

不可分离呢？

很自然我们会有两个疑问：为什么要分解？为什么能分解？

要解答这两个疑问，首先我们要搞清楚以下这件事情

卷积，就是局部的全连接，即矩阵乘法

[w,h,in] * [k,k,in,out]
这样的卷积，可以视为输入图像一个[k,k]局部的全连接。

conv([k,k,in], [k,k,in,out]) 等价于 [k*k*in] * [k*k*in*out]的一个全连接。就是个矩阵乘法。

当k*k*in比较大时，仍然计算量很大。

如何减小计算量 - 矩阵分解

上面我们看到了，卷积就是局部的全连接。
那么一个最简单的减小计算量方式，就是矩阵分解(张量分解)。

[kkin] [kkinout]
我们需要对Tensor[in,k*k,out]进行分解，只需要保持[in,out]不变即可。
卷积核张量可以变成尺寸为$(whc) \times n)$的二维矩阵。
比如使用秩为$d$的SVD分解，因此每层的卷积核被分解成两个卷积核 $w \times h \times c \times d$ 和 $1 \times 1 \times d \times n$。这就是depthwise-conv + pointwise-conv吗？

回顾张量分解

1
2
3

[I,J,K] = [I,R] [J,R] [K,R] [R,R,R] # 最后一项可以省略，相当于降维到R，R要小于IJK。如果R较大，则是升维了。
        = [I*J,R] [R,K]  # 视为矩阵分解
        = [I,R] [R,J*K]  # 视为矩阵分解

张量分解，维度乱了，不再是conv形式了。既想矩阵分解，又想保持卷积形式，那么还是采用矩阵分解吧。

1
2
3

[in,k*k,out] = [in, k*k, R] [R, out]  # 维度不够，1来凑
             = [in, k*k, R] [R, 1*1, out]  #
             # [depthwise]   [pointwise]

通常情况下R怎么取值？既然是降低运算量，那么R的取值要小于in和out咯？

这里看到，这里的depthwise中，每个channel并不是independently，而是进行了R的交叉。

UV分解，USV分解。

为什么要分解？

要了解为什么要分解

为什么能分解？

深度可分离卷积

深度可分离卷积结构（depthwise separable convolution）

• Depthwise
  • depth: channel数
  • depthwise: 顾名思义，就是对所有input channel采用相同的操作。channel之间的操作是独立的，不交互的。

DSC是分解卷积(factorized convolutions)的一种，它将常规的卷积分解为一个depthwise conv与一个1*1 conv。

• depthwise conv: 用于channel内的filtering
• pointwise conv(1*1): 用于channel间的combining

定义:

DepthSepConv defines kxk depthwise convolution followed by 1x1 convolution

• 因为depthwise卷积是channel间独立的，所以一般会后接1*1卷积，做channel间的融合

优势:

• Depthwise separable convolutions reduce the number of parameters and computation used in convolutional operations while increasing representational efficiency.

传统卷积 (这里不关心$[w,h]$)
$$
[w, h,in] \xrightarrow[k \times k \times in \times out]{conv2d} [w,h,out]
$$

• 卷积参数量: $k \times k \times in \times out$
• 计算量:

参数

• depth_multiplier:
  -

历史 & 应用

• Rigid-motion scattering for image classification 2014 首次提出
• Inception models在前几层用到了，用于减小模型复杂度
• MobileNet 2017 首次
• SliceNet 2017 | 机器翻译, s

factorized convolutions是什么鬼？

• Factorized Networks
• Xception network
• Squeezenet

为什么能降低参数量，同时还能保持精度？

类似矩阵分解的思想。

Group conv是一种channel分组的方式，Depthwise +Pointwise是卷积的方式，只是ShuffleNet里面把两者应用起来了。因此Group conv和Depthwise +Pointwise并不能划等号。

而group卷积只是单纯的通道分组处理，降低复杂度。

Dilated Convolutions

空洞卷积（atrous convolutions）又名扩张卷积（dilated convolutions），向卷积层引入了一个称为 “扩张率(dilation rate)”的新参数，该参数定义了卷积核处理数据时各值的间距。

一个扩张率为2的3×3卷积核，感受野与5×5的卷积核相同，而且仅需要9个参数。你可以把它想象成一个5×5的卷积核，每隔一行或一列删除一行或一列。

在相同的计算条件下，空洞卷积提供了更大的感受野。空洞卷积经常用在实时图像分割中。当网络层需要较大的感受野，但计算资源有限而无法提高卷积核数量或大小时，可以考虑空洞卷积。

扩展阅读

1. Andrew Ng 的UFLDL教程
2. 各种卷积结构原理及优劣 | Medium 比较新
3. 一文了解各种卷积结构原理及优劣 | Medium & 中文翻译|知乎
4. 理解深度学习中的卷积 | Tim Dettmers & 中文翻译 | 码农场
5. Understanding Convolutions | colah
6. 卷积为什么叫「卷」积？ | 知乎
7. 如何通俗易懂地解释卷积？ | 知乎
8. A guide to convolution arithmetic for deep learning

简介

Is learning better networks as easy as stacking more layers?

深层网络会遭遇退化问题(degradation): 随着网络层数的增加，精度会到达饱和区，而后迅速下降。

作者在CIFAR-10数据进行实验，采用3x3 卷积层的简单堆叠来测试网络深度的影响。
发现当层数增加到20层的时候网络进入饱和区(即使再增加网络的深度，精度也不会提高)。
不仅如此，继续增加深度还会导致模型退化，训练精度和测试精度迅速下降。
这说明当网络变得很深以后，深度网络就变得更加难以训练了。(注意：这不是过拟合。过拟合是训练误差小，测试误差大)

(难以训练，训练误差)

随着网络层级的不断增加，模型精度不断得到提升。
而当网络层级增加到一定的数目以后，

“Overly deep” plain nets have higher training error

【问题来了】为什么随着网络层级越深，训练误差越大了？

模型

如何又能加深网络层数、又能解决梯度消失问题、又能提升模型精度呢？

那么我们作这样一个假设：假设现有一个比较浅的网络（Shallow Net）已达到了饱和的准确率，这时在它后面再加上几个恒等映射层（Identity mapping，也即y=x，输出等于输入），这样就增加了网络的深度，并且起码误差不会增加，也即更深的网络不应该带来训练集上误差的上升。而这里提到的使用恒等映射直接将前一层输出传到后面的思想，便是著名深度残差网络ResNet的灵感来源。

这里没看懂。恒等映射层是 y=x, 还是y=f(x)+x ?

创新点

Residual Learning

• 普通网络中：
  $H(x)$ is any desired mapping,
  hope the 2 weight layers fit $H(x)$
• 残差网络：$H(x)$ is any desired mapping,
  hope the 2 weight layers fit 𝐻(𝑥)
  hope the 2 weight layers fit $F(x)$
  let $H(x)=F(x)+x$

恒等映射

Identity Mapping by Shortcuts

bottle neck

右侧是bottleneck连接，左右两个网络具有相似的复杂度，但是右侧的bottlenect设计能够用于更深层的网络。

疑问

为什么不能简单地增加网络层数？

对于原来的网络，如果简单地增加深度，会导致梯度弥散或梯度爆炸。

对于该问题的解决方法是正则化初始化和中间的正则化层（Batch Normalization），这样的话可以训练几十层的网络。

虽然通过上述方法能够训练了，但是又会出现另一个问题，就是退化问题，网络层数增加，但是在训练集上的准确率却饱和甚至下降了。这个不能解释为overfitting，因为overfit应该表现为在训练集上表现更好才对。
退化问题说明了深度网络不能很简单地被很好地优化。
作者通过实验：通过浅层网络+ y=x 等同映射构造深层模型，结果深层模型并没有比浅层网络有等同或更低的错误率，推断退化问题可能是因为深层的网络并不是那么好训练，也就是求解器很难去利用多层网络拟合同等函数。

怎么解决退化问题？

深度残差网络。如果深层网络的后面那些层是恒等映射，那么模型就退化为一个浅层网络。那现在要解决的就是学习恒等映射函数了。 但是直接让一些层去拟合一个潜在的恒等映射函数H(x) = x，比较困难，这可能就是深层网络难以训练的原因。但是，如果把网络设计为H(x) = F(x) + x,如下图。我们可以转换为学习一个残差函数F(x) = H(x) - x. 只要F(x)=0，就构成了一个恒等映射H(x) = x. 而且，拟合残差肯定更加容易。

维度设计

从上到下：

• 整体的feature_map变小
• 整体的channel数目在增大

源码

• 官方实现 | KaimingHe caffe

keras

强调identity_block，恒等映射

pytorch

强调bottlenect

• resnet示例-pytorch
  • 依赖 resnet模型-pytorch
• 另外一个resnet版本 https://github.com/keras-team/keras/blob/master/keras/applications/resnet50.py
• resnet-tensorflow
  • 提供cifar10 imagenet的示例

ResNet可视化

参考

• SGD在两层神经网络上是怎么收敛的？ | 知乎
• ResNet及其多种变体
• https://www.jianshu.com/p/e58437f39f65