Posted on Edited on

命名实体识别学习-用lstm+crf处理conll03数据集

[TOC]

一直想写的一篇文章，虽然好像也不是很忙，但是一直拖着没做。就是讲下面两篇文章介绍的数据集和算法做一个整合

命名实体识别学习-数据集介绍-conll03

命名实体识别学习-从基础算法开始（02）lstm+crf序列标注

一 整合时要解决的问题

  1. 要为数据和模型读入设计合理的数据结构：即vocab-vecterizer-dataset这个pipeline，几乎所有的nlp任务都要走这个pipeline的模式（看别人的源码发现，真正实现这些数据结构时代码五花八门，不过数据结构本来就是ADT的物理实现，只要把核心功能实现就好了。）

  2. 原有的算法是一句一句读入的，我实现的时候要用mini-batch, mini-batch已经被证明了其在深度学习应用的作用和功能。不过应用mini-batch要考虑输入句子长短不一的问题，使用pad和mask的技术，尽量避免模型看到pad的元素。本模型主要有三处用到，第一是lstm读入时，然后是crf的算句子得分，和loss计算的时候。在这三处要用mask的方法避免模型读到pad的元素。

  3. 原代码，即pytorch官网上放的教程为了使代码便于理解，使用了很多for循环，不利于cuda对代码的加速，尽量将能够变为矩阵运算的for循环变为矩阵的计算。

要解决的三个问题：数据结构，pad和mask，for循环改为矩阵计算。还有一个使代码可以在GPU上运行。（不过我自己最近没法找到卡，所以代码都是凭感觉debug的，不过这次代码已经在学弟卡上跑过了）

二 mask和pad

变长序列的处理是深度学习框架的一大难题，各个框架都有比较成熟的解决问题，

lstm读入

其中pytorch为RNN的读入专门做了处理。所以对于lstm读入时处理就很简单，只需简单调用torch.nn.utils.rnn.pack_padded_sequence()和torch.nn.utils.rnn.pad_packed_sequence即可：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def _get_lstm_features(self, embedded_vec, seq_len):
        """
        :param embedded_vec: [max_seq_len, b_s, e_d]
        :param seq_len: [b_s]
        :return:
        """
        # 初始化 h0 和 c0,可以缺省 shape:
        # ([num_layers * num_directions, batch, hidden_size],[num_layers * num_directions, batch, hidden_size])
        # self.hidden = self.init_hidden(1, seq_len.size(0))
        pack_seq = pack_padded_sequence(embedded_vec, seq_len)
        # 不初始化状态，默认初始状态都为0
        # lstm_out, self.hidden = self.lstm(pack_seq, self.hidden)
        lstm_out, self.hidden = self.lstm(pack_seq)
        lstm_out, _ = pad_packed_sequence(lstm_out, batch_first=True) #[b_s, seq_len, h_d]
        lstm_feats = self.hidden2tag(lstm_out)  #[b_s, seq_len, tag_size]
        lstm_feats = self.dropout(lstm_feats)
        return lstm_feats

注意：使用这两个自带函数有个问题，并不能恢复百分百恢复原来的输入，他恢复后的句长是输入最长句子的长度，也就是说如果你输入时最长句子也有一定长度的pad元素，那样是没办法恢复的。

涉及转移分矩阵的计算

第二处mask是在转移分的计算，因为self.transitions给pad元素留了位置，代码如下：

1
2
self.transition = nn.Parameter(
            torch.randn(self.tagset_size, self.tagset_size))

这其实不符合我们尽量避免模型看到pad元素的原则（我尝试不在transition里给pad留位置，但是由于 变长序列总会有pad元素，如果没有pad元素的位置，索引就会报错。）这里我使用折中处理，在涉及到转移分矩阵的运算并直接关联结果的都mask掉，（其实存在于矩阵里无所谓，只要最后计算不影响结果即可。

涉及到转移分的计算，主要是loss的计算，在官网文档里：

1
2
3
4
5
def neg_log_likelihood(self, sentence, tags):
    feats = self._get_lstm_features(sentence)
    forward_score = self._forward_alg(feats)
    gold_score = self._score_sentence(feats, tags)
    return forward_score - gold_score

其中，gold_score的计算和forward_score的计算都需要mask机制。

首先是得到mask：

1
mask = (token_vec != self.token_vocab.lookup_token(self.pad)).to(self.device)  # [b_s, max_seq_len]

这个token_vec就是句子向量，mask是一个布尔值向量，其中不等于pad的位置为true，等于pad的位置为false。

1
2
3
4
5
6
7
8
9
def _score_sentence(self, feats, tags):
    # Gives the score of a provided tag sequence
    score = torch.zeros(1)
    tags = torch.cat([torch.tensor([ self.tag_to_ix[START_TAG]], dtype=torch.long), tags ])
    for i, feat in enumerate(feats):
        score = score + \
            self.transitions[tags[i + 1], tags[i]] + feat[tags[i + 1]]
    score = score + self.transitions[self.tag_to_ix[STOP_TAG], tags[-1]]
    return score

这个gold_score的代码相对简单：逻辑就是把真实tag对应的转移分和发射分相加，（其实这里的for循环可以去掉换成矩阵运算）因为feats中每个句子（即每个时间步）都参与一次计算，且可能有pad元素，对mask的处理：

1
total_score = (score * mask.type(torch.float)).sum(dim=1)

forward_score出的mask的处理，官网关于foward_score的计算比较长，就不放了，简述下逻辑，forward_score的计算本质上就是前向算法，前向算法就是DP。（在前面的博客里介绍的比较详细）在每个时间步里求前向变量，而我们用了mini-batch那么一个时间步计算的就不是一个token了。而是一批token，而由于一个mini-batch里句子是不等长的，可能一个句子还没结束，其他句子就已经运算的pad元素了，所以要用mask机制避免pad元素参与到运算中。

1
2
3
for feat_index in range(1, feats.size(1)):
    n_unfinish = mask[:, feat_index].sum()
    d_uf = d[:n_unfinish] #[uf, 1, tag_size]

这里是直接算出非pad元素的个数，因为我们的输入是按句长排列的，所以可以直接取前n_finish个进行计算。

三 将for循环改为矩阵运算

原官网代码为了代码可读性，使用的了几处for循环，是可以用矩阵运算代替的，同时代码里的前向算法和维特比解码算法是动态规划算法，可能是不适合改为矩阵运算（不过也不一定，可能有大神实现了）

哪些可以改为for循环？这个问题我也没有查到，我的理解就是看能不能并行，能并行的话大部分都可以用矩阵运算（这是句废话），当然如何分析能不能并行，这个还有待后续查资料继续学习。

gold_score的计算

在计算neg_log_likelihood时需要计算gold_score,其代码如下：

1
2
3
4
5
6
7
8
9
def _score_sentence(self, feats, tags):
        # Gives the score of a provided tag sequence
        score = torch.zeros(1)
        tags = torch.cat([torch.tensor([ self.tag_to_ix[START_TAG]], dtype=torch.long), tags ])
        for i, feat in enumerate(feats):
            score = score + \
                self.transitions[tags[i + 1], tags[i]] + feat[tags[i + 1]]
        score = score + self.transitions[self.tag_to_ix[STOP_TAG], tags[-1]]
        return score

但看这段代码，因为score计算依赖上一个时间步的score，乍一看似乎不能无法更改（不能因为依赖上一步的结果就认为是个dp算法，关键看有没有最优子结构），不过稍加分析，其实这个是最容易改为矩阵计算的，证明如下：

1
2
3
4
5
6
score0=transition[tags[1], tags[0]]+feat[tags[1]]
score1=score0+transition[tags[2], tags[1]]+feat[tags[2]]
...
scorei+1=scorei+transition[tags[i+1], tags[i]]+feats[tags[i+1]]

score=score0+score1+...+scorei+1=transition[tags[1], tags[0]]+feat[tags[1]]+...+transition[tags[i+1], tag[i]]+feat[tags[i+1]]

从上面的分析，很容易将这段代码改为矩阵计算，同时加上mask机制。最终代码如下：

1
2
3
4
5
def _score_sentence(self, feats, tags, mask):
    score = torch.gather(feats, dim=2, index=tags.unsqueeze(dim=2)).squeeze(dim=2)
    score[:, 1:] += self.transition[tags[:, :-1], tags[:, 1:]]
    total_score = (score * mask.type(torch.float)).sum(dim=1)
    return total_score

forward_score的计算

原官网的代码：

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
def _forward_alg(self, feats):
       # Do the forward algorithm to compute the partition function
       init_alphas = torch.full((1, self.tagset_size), -10000.)
       # START_TAG has all of the score.
       init_alphas[0][self.tag_to_ix[START_TAG]] = 0.

       # Wrap in a variable so that we will get automatic backprop
       forward_var = init_alphas

       # Iterate through the sentence
       for feat in feats:
           alphas_t = []  # The forward tensors at this timestep
           for next_tag in range(self.tagset_size):
               # broadcast the emission score: it is the same regardless of
               # the previous tag
               emit_score = feat[next_tag].view(
                   1, -1).expand(1, self.tagset_size)
               # the ith entry of trans_score is the score of transitioning to
               # next_tag from i
               trans_score = self.transitions[next_tag].view(1, -1)
               # The ith entry of next_tag_var is the value for the
               # edge (i -> next_tag) before we do log-sum-exp
               next_tag_var = forward_var + trans_score + emit_score
               # The forward variable for this tag is log-sum-exp of all the
               # scores.
               alphas_t.append(log_sum_exp(next_tag_var).view(1))
           forward_var = torch.cat(alphas_t).view(1, -1)
       terminal_var = forward_var + self.transitions[self.tag_to_ix[STOP_TAG]]
       alpha = log_sum_exp(terminal_var)
       return alpha

下面简单分析下,假设tag_size=2，值集合为：{0,1}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
emit_score=feat[0].expand(1, self.tagset_size) #经过扩展emit_score变为shape为[1，2]的矩阵，因为pytorch的广播机制，其实就是[feat[0], feat[0]]
trans_score = self.transitions[0].view(1, -1)# 这个本身就是shape为[1，2]的矩阵，表示tag分别从0，1转为0的转移分。
next_tag_var0= forward_var + trans_score + emit_score=forward_var +[feat[0], feat[0]]+self.transitions[0]

# 下一个迭代
emit_score=feat[1].expand(1, self.tagset_size) #经过扩展emit_score变为shape为[1，2]的矩阵，因为pytorch的广播机制，其实就是[feat[0], feat[0]]
trans_score = self.transitions[1].view(1, -1)# 这个本身就是shape为[1，2]的矩阵，表示tag分别从0，1转为0的转移分。
next_tag_var1= forward_var + trans_score + emit_score=forward_var +[feat[1], feat[1]]+self.transitions[1]

从这个分析很明显可以看出可以转为矩阵计算，大致思路为：
next_tag_var = forward_var+feats.unsqueeze(dim=1)+self.transitions

其中：
feat.unsqueeze(dim=1)+self.transitions # shape为[tag_size, tag_size]
forward_var的shape为[1，tag_size]， 这里的矩阵计算，会通过广播机制，自动复制其自身的值。

加上batch所处的维度，刚好是三维张量的计算，是一个比较习惯处理的维度，再加去掉for循环，加高维度没有必要。最终结果：

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
def _forward_alg(self, feats, mask):
    """前向算法
    :param feats: [b_s, seq_len, tag_size]
    :param mask: [b_s, seq_len]
    :return:
    """
    # Do the forward algorithm to compute the partition function
    init_alphas = torch.full((feats.size(0), self.tagset_size), -10000., device=self.device)    #[b_s, tag_size]
    # START_TAG has all of the score.along dim=1,
    init_alphas[:, self.begin_tag_idx]=0.

    # Wrap in a variable so that we will get automatic backprop
    forward_var_list=[]
    forward_var_list.append(init_alphas)
    d = torch.unsqueeze(feats[:,0], dim=1)  #[b_s, 1, tag_size]
    for feat_index in range(1, feats.size(1)):
        n_unfinish = mask[:, feat_index].sum()
        d_uf = d[:n_unfinish] #[uf, 1, tag_size]
        emit_and_transition = feats[: n_unfinish, feat_index].unsqueeze(dim=1)+self.transition #[uf,tag_size,tag_size]
        log_sum = d_uf.transpose(1, 2)+emit_and_transition  #[uf, tag_size, tag_size]
        max_v = log_sum.max(dim=1)[0].unsqueeze(dim=1)  #[uf, 1, tag_size]
        log_sum = log_sum - max_v   #[uf, tag_size, tag_size]
        d_uf = max_v + torch.logsumexp(log_sum, dim=1).unsqueeze(dim=1) # [uf, 1, tag_size]
        d = torch.cat((d_uf, d[n_unfinish:]), dim=0)
    d = d.squeeze(dim=1)    #[b_s, tag_size]
    max_d = d.max(dim=-1)[0]  # [b_s]
    d = max_d + torch.logsumexp(d - max_d.unsqueeze(dim=1), dim=1)  # [b_s]
    return d

维特比解码算法的修改思路和前向算法大致一致，修改后的代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def _viterbi_decode(self, feats, mask, seq_len):
    batch_size = feats.size(0)
    tags = [[[i] for i in range(len(self.tag_vocab))]] * batch_size  # list, shape: (b, K, 1)
    d = torch.unsqueeze(feats[:, 0], dim=1)  # shape: (b, 1, K)
    for i in range(1, seq_len[0]):
        n_unfinished = mask[:, i].sum()
        d_uf = d[: n_unfinished]  # shape: (uf, 1, K)
        emit_and_transition = self.transition + feats[: n_unfinished, i].unsqueeze(dim=1)  # shape: (uf, K, K)
        new_d_uf = d_uf.transpose(1, 2) + emit_and_transition  # shape: (uf, K, K)
        d_uf, max_idx = torch.max(new_d_uf, dim=1)
        max_idx = max_idx.tolist()  # list, shape: (nf, K)
        tags[: n_unfinished] = [[tags[b][k] + [j] for j, k in enumerate(max_idx[b])] for b in range(n_unfinished)]
        d = torch.cat((torch.unsqueeze(d_uf, dim=1), d[n_unfinished:]), dim=0)  # shape: (b, 1, K)
    d = d.squeeze(dim=1)  # [b_s, tag_size
    score, max_idx = torch.max(d, dim=1)  # shape: (b,)
    max_idx = max_idx.tolist()
    tags = [tags[b][k] for b, k in enumerate(max_idx)]
    return score, tags

整个工程代码地址：https://github.com/SStarLib/NERfromBasic/tree/master/Day03minibatch-lstm%2Bcrfs/conll03Ner

结果：

![image-20200719003342138](/Users/wei/Library/Application Support/typora-user-images/image-20200719003342138.png)

这个是加入了预训练embedding的结果，比不加稍微好一点。不过好的有限。甚至有的地方还要更差。

总结

整个工程代码花费了接近一天的时间，写代码的时候出现了各种奇奇怪怪的bug，有的是变量命名差个s，结果写的时候没有注意出错，好不容易调通了，结果发现loss一直不变化，我还以为是我的代码实现的有问题，结果把代码改的面目全非，甚至很多地方已经背离了我最初的思路了，几乎是把整个工程推翻重写，最后debug时，发现lstm生成的feats几乎不变化，才开始意识到模型根本没起作用，最终发现是因为没有对模型参数初始化的原因，（真的是太久不写pytorch的代码了，连模型参数初始化都先不起来）虽然最后整个工程项目成功了，但是花费了大量时间，真的，写出bug free的工程代码是一个人素质的体现!

关于加入了预训练embedding的结果不显著的问题，可能是glove，只有小写字母，而字母的大小写本身就是实体的一个重要特征，使用了glove反而可能丢失了这个重要特征，解决办法是加入char embedding ,下次可以在模型中加入，或者一步到位，使用Elmo的embedding，

尽量要使用 mini batch

for循环改为矩阵计算，提高并行性，提升运算速度很重要，一般常用的都是三维张量，包含一维batch，所以尽量改成三维张量的运算为好。

pad和mask机制的使用，有空可以专门写一篇文章，介绍这个，并总结一下。

pipeline的数据结构，有空了再介绍吧，不难，主要是要明确要实现的功能，并抽象出来，然后用代码实现即可。

一直想要系统性的学一下pytorch，可是到现在连本相关的书都没买过，（甚至30分钟的官网视频也没看），甚至不知道pytorch能做啥不能做啥。所以我的coding过程非常痛苦，使用google的频率非常高。pytorch的api，几乎要不停的查。磨刀不误砍柴工,真的应该系统性的学习下这个框架，然后再想着复现论文。

比赛的时候一定不会用pytorch，相比keras的搭积木似的coding过程，pytorch的开发周期确实有点长了，甚至要一直照顾shape，所以我在我的代码里要一直备注shape的变化，和广播机制将要怎么发生。

要好好了解下pytorch的广播机制，这个是代码可读性的天敌，不好好了解，有时候无法看懂别人的代码。

Posted on

命名实体识别学习-数据集介绍-conll03

[TOC]

conll 2003 是命名实体中最常见的公开数据集。其官网：https://www.clips.uantwerpen.be/conll2003/ner/

有很详细的介绍。

一 类别个数

Named entities are phrases that contain the names of persons, organizations, locations, times and quantities. Example:

[ORG U.N. ] official [PER Ekeus ] heads for [LOC Baghdad ] .

The shared task of CoNLL-2003 concerns language-independent named entity recognition. We will concentrate on four types of named entities: persons, locations, organizations and names of miscellaneous entities that do not belong to the previous three groups.The participants of the shared task will be offered training and test data for two languages. They will use the data for developing a named-entity recognition system that includes a machine learning component. For each language, additional information (lists of names and non-annotated data) will be supplied as well. The challenge for the participants is to find ways of incorporating this information in their system.

上文来自官网，高亮部分介绍其所要分的类别。总共四类：persons, locations, organizations ,miscellaneous entities

二 数据集样例

image-20200714231551083

这是其训练集中某个部分。

通过其官网介绍，可知改数据集第一例是单词，第二列是词性，第三列是语法快，第四列是实体标签。在NER任务中，只关心第一列和第四列。实体类别标注采用BIO标注法，前面博客介绍这种标注法。

以下是官网的介绍：

The CoNLL-2003 shared task data files contain four columns separated by a single space. Each word has been put on a separate line and there is an empty line after each sentence. The first item on each line is a word, the second a part-of-speech (POS) tag, the third a syntactic chunk tag and the fourth the named entity tag. The chunk tags and the named entity tags have the format I-TYPE which means that the word is inside a phrase of type TYPE. Only if two phrases of the same type immediately follow each other, the first word of the second phrase will have tag B-TYPE to show that it starts a new phrase. A word with tag O is not part of a phrase. Here is an example:

1
2
3
4
5
6
7
U.N.         NNP  I-NP  I-ORG 
official     NN   I-NP  O 
Ekeus        NNP  I-NP  I-PER 
heads        VBZ  I-VP  O 
for          IN   I-PP  O 
Baghdad      NNP  I-NP  I-LOC 
.            .    O     O

The data consists of three files per language: one training file and two test files testa and testb. The first test file will be used in the development phase for finding good parameters for the learning system. The second test file will be used for the final evaluation. There are data files available for English and German. The German files contain an extra column (the second) which holds the lemma of each word.

三 预处理

上面已经介绍了数据集的结构，同时，我们想要将数据输入变为下面这种数据结构，所以要对文本数据做一定处理：

1
2
3
4
5
6
7
 [(
    "the wall street journal reported today that apple corporation made money".split(),
    "B I I I O O O B I O O".split()
), (
    "georgia tech is a university in georgia".split(),
    "B I O O O O B".split()
)]

上面代码在命名实体识别学习-从基础算法开始（02）lstm+crf序列标注 里介绍过。

预处理思路：获取每句话的tokens数组和tags数组，其中每句话用一个空行分隔。

根据上面思路，处理起来很简单：

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
from tqdm import tqdm
import os
class Conll03Reader:
    def read(self, data_path):
        data_parts = ['train', 'valid', 'test']
        extension = '.txt'
        dataset = {}
        for data_part in tqdm(data_parts):
            file_path = os.path.join(data_path, data_part+extension)
            dataset[data_part] = self.read_file(str(file_path))
        return dataset

    def read_file(self, file_path):
        samples = []
        tokens = []
        tags = []
        with open(file_path,'r', encoding='utf-8') as fb:
            for line in fb:
                line = line.strip('\n')

                if line == '-DOCSTART- -X- -X- O':
                    # 去除数据头
                    pass
                elif line =='':
                    # 一句话结束
                    if len(tokens) != 0:
                        samples.append((tokens, tags))
                        tokens = []
                        tags = []
                else:
                    # 数据分割，只要开头的词和最后一个实体标注。
                    contents = line.split(' ')
                    tokens.append(contents[0])
                    tags.append(contents[-1])
        return samples
if __name__ == "__main__":
    ds_rd = Conll03Reader()
    data = ds_rd.read("./conll2003_v2")
    for sample in data['train'][:10]:
        print(sample)

四 总结

将数据集处理为模型可读的标准化输入是整个模型的第一步，接下来文章将尝试用模型处理该数据集，并介绍一种可通用的数据处理的pipeline。

Posted on Edited on

面试中常见的图论问题

[TOC]

二分图问题：

LeetCode 785. Is Graph Bipartite?

这是一个直白的二分图问题：二分图问题，就是可否将图的所有节点分成两个集合，有连边两个点不在一个集合。

将二分图问题可以看成二染色问题，即使用两种颜色对图进行染色，相连的两个点，颜色不能相同。

解决办法：遍历染色

DFS+染色：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public boolean isBipartite(int[][] graph) {
        // 染色状态; 0-未染色，1-蓝色，-1-红色
        int[] colors = new int[graph.length];
        for (int i = 0; i < colors.length; i++) {
            if(colors[i]==0 && !dfs(i, 1, colors, graph)){
                return false;
            }
        }
        return true;
    }
    private boolean dfs(int v, int color, int[] colors, int[][] graph) {
        colors[v]=color;
        for(int adjV:graph[v]){
            if(colors[adjV]==color) return false;
            if(colors[adjV]==0 && !dfs(adjV, -color, colors, graph)){
                return false;
            }
        }
        return true;
    }
}

也可以BFS+染色：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public class Solution {
    public boolean isBipartite(int[][] graph) {
        // 染色状态; 0-未染色，1-蓝色，-1-红色
        int[] colors = new int[graph.length];
        for (int i = 0; i < colors.length; i++) {
            if(colors[i]==0 && graph[i].length>0){
                colors[i] = 1;
                Queue<Integer> q = new LinkedList<>();
                q.offer(i);
                while(!q.isEmpty()){
                    int curr = q.poll();
                    for(int adjV:graph[curr]){
                        if(colors[adjV]==0){
                            colors[adjV]=-colors[curr];
                            q.offer(adjV);
                        }
                        else if(colors[adjV]==colors[curr]) return false;
                    }
                }
            }
        }
        return true;
    }
}

886. Possible Bipartition

这道题加了点丰富的背景，但是很容易看出来还是一个二分图问题。据说这道题是今年字节跳动的笔试题

多了一点构建图。

DFS+染色：

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
public class Solution {
    public boolean possibleBipartition(int N, int[][] dislikes) {
        // 构建图
        List<Integer>[] graph = new ArrayList[N+1];
        for (int i = 1; i < N+1; i++) {
            graph[i] = new ArrayList<>();
        }
        for (int[] l : dislikes) {
            graph[l[0]].add(l[1]);
            graph[l[1]].add(l[0]);
        }
        // 状态数组
        int[] colors = new int[N+1];
        for (int i = 1; i < N+1; i++) {
            if(colors[i]==0 && !dfs(i, graph, colors, 1)){
                return false;
            }
        }
        return true;
    }
    private boolean dfs(int pid, List<Integer>[] graph, int[] colors, int color){
        colors[pid] = color;
        for (int other_pid : graph[pid]) {
            if(colors[other_pid]==color) return false;
            if(colors[other_pid]==0 && !dfs(other_pid, graph, colors, -color)){
                return false;
            }
        }
        return true;
    }
}

拓扑排序问题

详细介绍见我这篇博客：BFS DFS 判断DAG(有向无环图)

207. Course Schedule

这道题原先用Python写过。BFS+入度，和DFS暴力搜索两种，直接上java代码；

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
class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        //邻接表建图
        ArrayList<Integer>[] graph = new ArrayList[numCourses];
        //记录每个节点的入度
        int[] indegree = new int[numCourses];
        for (int i = 0; i < numCourses; i++) {
            graph[i]=new ArrayList<>();
        }
        for(int[] prq:prerequisites){
            // 需要先修的课程指向后修的课程
            graph[prq[1]].add(prq[0]);
            // 后修的课程入度+1；
            indegree[prq[0]]++;
        }
        // BFS 拓扑排序
        Queue<Integer> q = new LinkedList<>();
        int cnt=0;
        for (int i = 0; i < numCourses; i++) {
            if(indegree[i]==0){
                q.offer(i);
            }
        }
        while(!q.isEmpty()){
            int curr = q.poll();
            cnt++;
            for(int adjV:graph[curr]){
                indegree[adjV]--;
                if(indegree[adjV]==0) q.offer(adjV);
            }        
        }
        return cnt==numCourses;
    }
}
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
public class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        //邻接表建图
        ArrayList<Integer>[] graph = new ArrayList[numCourses];
        // 状态数组
        int[] mark = new int[numCourses];
        for (int i = 0; i < numCourses; i++) {
            graph[i]=new ArrayList<>();
        }
        for(int[] prq:prerequisites){
            // 需要先修的课程指向后修的课程
            graph[prq[1]].add(prq[0]);
        }
        for (int i = 0; i < numCourses; i++) {
            if(!dfs(i, mark, graph)) return false;
        }
        return true;
    }
    private boolean dfs(int v, int[] mark, ArrayList<Integer>[] graph) {
        mark[v]=1;
        for(int adjV:graph[v]){
            if(mark[adjV]==0){
                if(!dfs(adjV, mark, graph)) 
                    return false;
            }else if(mark[adjV]==1)
                return false;
        }
        mark[v]=2;
        return true;
    }
}

210. Course Schedule II

这道拓扑排序，唯一的不同就是讲排序结果输出，用BFS+入度，再加个数组。

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
class Solution {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        int[] res = new int[numCourses];
        // 建图，
        ArrayList<Integer>[] graph = new ArrayList[numCourses];
        int[] indegree = new int[numCourses];
        int cnt = 0;
        for (int i = 0; i < numCourses; i++) {
            graph[i]=new ArrayList<>();
        }
        for(int[] p: prerequisites){
            graph[p[1]].add(p[0]);
            indegree[p[0]]++;
        }
        Queue<Integer> q = new LinkedList<>();
        for(int i=0; i<numCourses; i++){
            if(indegree[i]==0){
                q.offer(i);
            }
        }
        while(!q.isEmpty()){
            int cur = q.poll();
            res[cnt++] = cur;
            for(int adjV: graph[cur]){
                indegree[adjV]--;
                if(indegree[adjV]==0)
                    q.offer(adjV);
            }
        }
        return cnt==numCourses?res:new int[0];
    }
}

并查集检查冗余

并查集详细介绍：并查集原理及联通分量个数问题

注：并查集上的点至少有两个属性：（data, parent),其中指向parent，这种映射关系，完全可以用数组的index-value代替，故我们可以有两个数组 parent，rank(用于UF的优化，路径压缩等等),而data作为index存在，映射关系则用数组实现。

684. Redundant Connection

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
class Solution {
    class UF{
        private int[] parent;
        private int[] rank;
        public UF(int n){
            parent = new int[n];
            rank = new int[n];
            for (int i = 0; i < n; i++) {
                parent[i] = i;
            }
        }
        public int find(int p){
            // 查找集合根节点
            int r = p;
            while(r!=parent[r]){
                r = parent[r];
            }
            // 路径压缩
            int k = p;
            while(k!=r){
                int par = parent[k];
                parent[k] = r;
                k = par;
            }
            return r;
        }
        public void union(int p, int q) {
            int rootp = find(p);
            int rootq = find(q);
            if (rootp==rootq) return;
            if(rank[rootp]>=rank[rootq]){
                if(rank[rootp]==rank[rootq]){
                    rank[rootp]+=1;
                }
                parent[rootq]=rootp;
            }else{
                parent[rootp]=rootq;
            }
        }
        public boolean connect(int p, int q){
            return find(p)==find(q);
        }
    }
    public int[] findRedundantConnection(int[][] edges) {
        UF uf = new UF(edges.length+1);
        for(int[] edg:edges){
            int p=edg[0],q=edg[1];
            if(uf.connect(p, q)){
                return edg;
            }
            uf.union(p, q);
        }
        return new int[]{-1, -1};
    }
}

547. Friend Circles

单纯的并查集问题

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
class Solution{
    class UnionFind{
        private int numSets = 0;
        private int[] parent, rank;
        public UnionFind(int n){
            numSets = n;
            parent = new int[n];
            rank = new int[n];
            for(int i=0;i<n; i++){
                parent[i]=i;
            }
        }
        public int find(int p){
            int r = p;
            while(r!=parent[r]){
                r = parent[r];
            }
            int k = p;
            while(k!=r){
                int j = parent[k];
                parent[k]=r;
                k = j;
            }
            return r;
        }
        public void union(int p, int q){
            int rootP = find(p);
            int rootQ = find(q);
            if (rootP==rootQ) return;
            if (rank[rootP]>=rank[rootQ]){
                if (rank[rootP]==rank[rootQ]){
                    rank[rootP]+=1;
                }
                parent[rootQ]=rootP;
            }else{
                parent[rootP]=rootQ;
            }
            numSets-=1;
        }
        public int getNumSets() {
            return numSets;
        }
    }
    public int findCircleNum(int[][] M) {
        UnionFind uf = new UnionFind(M.length);
        for(int i=0;i<M.length;i++){
            for(int j=i+1; j<M.length;j++){
                if(M[i][j]==1) uf.union(i, j);
            }
        }
        return uf.getNumSets();
    }
}

图论还有最短路问题，网络流问题（这个面试应该不会问）等等。以后遇到了接着补充

Posted on Edited on

命名实体识别学习-从基础算法开始（02）lstm+crf序列标注

[TOC]

代码地址：https://github.com/SStarLib/NERfromBasic

序列标注

将命名实体识别看作序列标注问题，则可以用词性标注的方法来做。

标注方法：Inside–outside–beginning (tagging)

LSTM的不足

序列标注问题，lstm就可以做，但是lstm生成的标注序列是无约束的。而CRFs可以给模型增加约束，以下面例子为例，单纯的lstm极有可能生成第二个非法序列（没有先出现B，就出现了I），而条件随机场可以从训练数据中学习约束

1
2
3
4
5
6
7
合法序列：
"the wall street journal reported today that apple corporation made money"
" B   I      I      I       O       O     O    B        I       O     O"

非法序列：
"the wall street journal reported today that apple corporation made money"
" I   I      I      I       O       O     O    B        I       O     O"

条件随机场(CRFs):

image-20200622213107290

概率图模型：

image-20200622213529664

隐马尔可夫模型和条件随机场的区别：在CRFs中，观察序列X并不是由模型生成的。标记序列取值以观察序列为条件，同时来自于其邻接点。

从CRFs模型推到代码实现

模型要解决序列标注问题。所以主要使用的是线性链式的CRFs。

李航老师在《统计学习方法》里的定义：

条件随机场(conditional random field)是给定随机变量X条件下，随机变量Y的马尔可夫随机场。其中线性链条件随机场可以用于标注等问题。这时， 在条件概率模型$\hat{P}(Y|X)$中，Y是输出变量，表示标记序列，X是输入变量，表示需要标注的观测序列。也把标记序列称为状态序列(参见隐马尔可夫模型)。学习时，利用训练数据集通过极大似然估计或正则化的极大似然估计得到条件概率模型 $\hat{P}(y|x)$;预测时，对于给定的输入序列$x$，求出条件概率 $\hat{P}(y|x)$最大的输出序列 。

线性链条件随机场参数化形式如：
$$
P(y | x) = \frac{1}{Z(x)}exp\bigg(
\sum_{i,k}\lambda_k t_k (y_{i-1}, y_i, x, i)
+
\sum_{i,l}\mu_l s_l (y_i, x, i)
\bigg) \
Z(x) = \sum_{y}exp\bigg(
\sum_{i,k}\lambda_k t_k (y_{i-1}, y_i, x, i)
+
\sum_{i,l}\mu_l s_l (y_i, x, i)
\bigg) \
$$
可以使用梯度下降的方法对CRF参数进行梯度学习。（这里跟HMM模型很像），同时需要用前向算法递归的计算概率及期望值。前向算法本质是动态规划算法，基本思想L：定义前向变量 $\alpha_t(i)$，递推式：
$$
\alpha_t(i)=p(O_1 O_2 \cdots O_t, q_t=S_i | \mu)
$$

在时间$t+1$的前向变量可以根据时间$t$的前向变量$\alpha_t(1),\cdots \alpha_t(N)$的值递推计算,前向算法如下：

image-20200623223927451

前向算法，可以求出对应的概率，不但可以计算出预测标签的概率，同时可以计算真实标签的概率。然后应用损失函数，梯度下降的思想，可以逐渐优化LSTM的参数和CRF的参数。但是将CRF真正应用到LSTM的顶层，还需要做一些相应的变换，至少应该以训练网络的思想。已知句子序列$X$, 用前向算法判断标注序列的得分
$$
P_X(y_1,y_2,\cdots,y_T)\
=P_X(y_1) P_X(y_2|y_1) P_X(y_3|y_2) \cdots P_X(y_T|y_{T-1})\
=P_X(y_1) \frac{P_X(y_1, y_2)}{P_X(y_1) P_X(y_2)} P_X(y_2) \frac{P_X(y_2, y_3)}{P_X(y_2) P_X(y_3)}P_X(y_3) \dots \frac{P_X(y_{T-1}, y_T)}{P_X(y_{T-1}) P_X(y_T)} P_X(y_T)
$$

以$P_X(y_1, y_2)$为例，即在观察序列X下，在i=1位置标注记为$y_1$,在i=2位置标注记为$y_2$的概率。从序列标注的角度和CRF的定义出发，我们可以分解这个概率，即在i=1位置标注为$y_1$的概率$P_X(y_1)$, 假设L为标签集合，$y_1=l_i,y_2=l_j$,$i,j \in L$,则有转移概率$P(l_i->l_j)$,然后是$P_X (y_2)$ 即在观察序列X下，在i=2位置标注记为$y_2$的概率。然后可以在对数空间去看这个公式，并舍弃概率的意义。
$$
P_X(y_1,y_2,\cdots,y_T) \
= \frac{1}{Z} \exp \Big[emit(y_1;X)+
trans(y_1, y_2;X) + emit(y_2;X)
+\cdots + trans(y_{T-1}, y_T;X) + emit(y_T;X) \Big]
$$
定义函数 $ emit(y_i ; X) $ 为在观察序列X下，i位置标记为$y_i$的分数。定义函数$ trans(y_i, y_j ; X) $为在观察序列X下,$y_i$标记转移到$y_j$的分。对等式整理得如下所示：
$$
\log{P} = \sum_{i=1}^T emit(y_i) + \sum_{i=1}^{T-1} trans(y_i,y_{i+1}) + \log{Z}
$$
用前向算法的思想实现以上等式,整理递推表达式:
$$
foward_{i+1} = forward_{i} + emit(i) + trans(y_i, y_{i+1})
$$
用Python语言实现该前向算法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def _forward_alg(self, feats):
        init_alphas = torch.full((1, self.tagset_size), -10000.).to(device)
        init_alphas[0][self.tag_to_ix[START_TAG]] = 0

        forward_var = init_alphas

        # Iterate through the sentence
        for feat in feats:
            alphas_t = [] # The forward tensors at this timestep 前向张量
            for next_tag in range(self.tagset_size):
                emit_score = feat[next_tag].view(1, -1).expand(1, self.tagset_size)
                trans_score = self.transitions[next_tag].view(1, -1)
                next_tag_var = forward_var + trans_score + emit_score
                alphas_t.append(log_sum_exp(next_tag_var).view(1))
            forward_var = torch.cat(alphas_t).view(1, -1)
        terminal_var = forward_var + self.transitions[self.tag_to_ix[STOP_TAG]]
        alpha = log_sum_exp(terminal_var)
        return alpha

设计损失函数

有了前向算法，就可以设计损失函数， 由于训练的目的是为了学习到更准确的发射矩阵(emit score matrix)和转移矩阵(trans score matrix)，可以将真实标注输入前向算法得到一个分数，以及预测标注输入前向算法得到一个分数，以这两个分数的差值作为损失函数。这不只是经验上的选择，已有文献进行了数学上的证明，就不再赘述。损失函数的实现代码：

1
2
3
4
5
6
7
8
9
10
11
12
def _score_sentence(self, feats, tags):
        score = torch.zeros(1).to(device)
        tags = torch.cat([torch.tensor([self.tag_to_ix[START_TAG]], dtype=torch.long).to(device), tags]).to(device)
        for i, feat in enumerate(feats):
            score = score + self.transitions[ tags[i + 1], tags[i] ] + feat[ tags[i + 1] ]
        score = score + self.transitions[ self.tag_to_ix[STOP_TAG], tags[-1] ]
        return score
    def neg_log_likelihood(self, sentence, tags):
        feats = self._get_lstm_features(sentence)
        forward_score = self._forward_alg(feats)
        gold_score = self._score_sentence(feats, tags)
        return forward_score - gold_score

LSTM提取特征

代码: lstm的参数就是emit score 即，对于观察序列，给每个可能的标注打分。这是个矩阵，可以用反向传播进行学习。

1
2
3
4
5
6
7
def _get_lstm_features(self, sentence):
    self.hidden = self.init_hidden()
    embeds = self.word_embeds(sentence).view(len(sentence), 1, -1)
    lstm_out, self.hidden = self.lstm(embeds, self.hidden)
    lstm_out = lstm_out.view(len(sentence), self.hidden_dim)
    lstm_feats = self.hidden2tag(lstm_out)
    return lstm_feats

模型整体框架

image-20200623225600435

总结

lstm学习emit score，crf优化trans score，前向算法+neg-log-sum 进行计算loss，维特比算法解码出标记序列在新样本上进行推断。

Posted on

命名实体识别学习-从基础算法开始（01）-维特比算法

[TOC]

代码地址：https://github.com/SStarLib/NERfromBasic

Day1: 维特比算法

HMM的小例子

从一个小例子开始实现维特比算法：

例子来自知乎一个答案对维特比算法和HMM的讲解：

如何通俗地讲解 viterbi 算法？ - Kiwee的回答 - 知乎
https://www.zhihu.com/question/20136144/answer/239971177

大致介绍下这个例子：

题目背景

从前有个村儿，村里的人的身体情况只有两种可能：健康或者发烧。
假设这个村儿的人没有体温计或者百度这种神奇东西，他唯一判断他身体情况的途径就是到村头我的偶像金正月的小诊所询问。
月儿通过询问村民的感觉，判断她的病情，再假设村民只会回答正常、头晕或冷。
有一天村里奥巴驴就去月儿那去询问了。
第一天她告诉月儿她感觉正常。
第二天她告诉月儿感觉有点冷。
第三天她告诉月儿感觉有点头晕。
那么问题来了，月儿如何根据阿驴的描述的情况，推断出这三天中阿驴的一个身体状态呢?

将问题抽象为一个HMM

从问题中过可以看出，{健康，发烧}对应隐马尔可夫模型中的状态序列，{正常，冷，头晕}，则对应观察序列。（本例子其实不严谨，冷，头晕这两个观察现象是可以同时存在的，不过本例中假设其不同时存在）

问题要求：推断出这三天中阿驴的一个身体状态

问题本质：解码这三天的状态序列。

模型参数：状态转移概率矩阵，状态-观察概率分布矩阵，初始状态

  • 初始状态：月儿预判的阿驴身体状态的概率分布 = { 健康：0.6 , 发烧： 0.4 }

  • 状态转移概率矩阵： {
    健康->健康： 0.7 ,
    健康->发烧： 0.3 ,
    发烧->健康：0.4 ,
    发烧->发烧： 0.6
    }

  • 状态-观察概率分布矩阵：{
    健康，正常：0.5 ，冷 ：0.4 ，头晕： 0.1 ；
    发烧，正常：0.1 ，冷 ：0.3 ，头晕： 0.6
    }

    image-20200622160308608

有了模型参数。就可以构建模型并用维特比算法进行解码了即预测三天的身体状态。

Python实现维特比算法

为了方便后面学习，使用Pytorch框架（其实numpy应该更简单些）

手算维特比过程：

image-20200622155623835

伪代码：

维特比算法的伪代码（来自宗成庆老师的ppt）：

image-20200622161813184

代码前期准备

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def main():
    states = [ "健康", "发烧"]
    observations = ["正常","冷", "头晕"]
    tran_matrix = torch.Tensor([[0.7, 0.3], [0.4, 0.6]]) #A_ij
    emit_matrix = torch.Tensor([[0.5, 0.4, 0.1], [0.1, 0.3, 0.6]])
    init_state = [0.6, 0.4]
    observation_seq = ["正常","冷", "头晕"]
    viterbi = Viterbi(toIdx(states), toIdx(observations), tran_matrix, emit_matrix)
    maxpro, path = viterbi.viterbi(init_state, observation_seq)
    print("最大概率为：{}".format(maxpro))
    print("最大概率下路径为：")
    pt = ""
    for i in path:
        pt += states[i] + "->"
    print(pt)
main()

将模型主要参数：有状态空间，观察空间，状态转移概率矩阵，状态-观察概率分布矩阵（发射矩阵），初始状态

输入：观察序列（代码里也将初始状态作为了输入了）

1
2
3
4
5
6
7
class Viterbi:
    def __init__(self,s_to_idx, v_to_idx, tran_matrix, emit_matrix):
        self.s_to_idx = s_to_idx
        self.v_to_idx = v_to_idx
        self.tran_matrix = torch.Tensor(tran_matrix).transpose(0,1)
        self.emit_matrix = torch.Tensor(emit_matrix).transpose(0,1)
        self.state_size = len(s_to_idx)

维特比算法本质是动态规划算法，具有最优子结构，需要确定初始量，和递推关系。

小数的乘法计算会导致数越来越小，所以代码在对数空间上进行计算

第一步计算初始维特比变量：

1
2
3
4
5
6
7
8
9
10
11
12
# 在对数空间初始化维特比变量
      res = []
      init_state=torch.Tensor(init_state)
      for i, s in enumerate(init_state):
          v = self.v_to_idx[v_seq[0]]
          tmp = torch.log(s)+torch.log(self.emit_matrix[v][i])
          res.append(tmp)

      del init_state
      init_vvars = torch.stack(res)

      forward_var = init_vvars

第二步 迭代计算：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
for v in v_seq[1:]:
    bptrs_t =[]
    viterbivars_t = []
    v_index = self.v_to_idx[v]
    for s in range(self.state_size):
        next_tag_var = forward_var+torch.log(self.tran_matrix[s])
        best_tag_id = argmax(next_tag_var)
        bptrs_t.append(best_tag_id)
        viterbivars_t.append(next_tag_var[best_tag_id])
    forward_var = (torch.Tensor(viterbivars_t)+torch.log(self.emit_matrix[v_index]))
    backpointers.append(bptrs_t)
# 终结
terminal_var = forward_var
best_tag_id = argmax(terminal_var)
path_score = terminal_var[best_tag_id]

回溯解码：

1
2
3
4
5
6
7
8
# 回溯解码
      best_path = [best_tag_id]
      for bptrs_t in reversed(backpointers):
          best_tag_id = bptrs_t[best_tag_id]
          best_path.append(best_tag_id)

      best_path.reverse()
      return torch.exp(path_score), best_path

结果：

1
2
3
最大概率为：0.015120003372430801
最大概率下路径为：
健康->健康->发烧->

结果和手算的一致

总结

维特比算法本质就是动态规划代码。使用pytorch基本都是向量的运算。涉及到分数的连乘除最好转为对数的加减

Posted on

Chinese NER Using Lattice LSTM -笔记

[TOC]

简介：

论文题目：《Chinese NER Using Lattice LSTM》

论文链接：https://arxiv.org/abs/1805.02023

这是一篇发表在2018年自然语言处理领域顶级会议ACL的文章，提出了一种用于中文NER（命名实体识别）的Lattice LSTM模型。

Motivation

中文NER与分词有关。因为NEs(命名实体)是分词任务中OOV的重要来源。由于跨域分词（cross- domain word segmentation）仍然是一个未解决的问题。故在open domain 分词OOV更严重。

character-based方法优于word-based方法

Posted on Edited on

NBSVM (Naive Bayes - Support Vector Machine)学习

[TOC]

相关资料

论文：Baselines and Bigrams: Simple, Good Sentiment and Topic Classification.

fastai课程： Naive Bayes video.

kaggle：NB-SVM strong linear baseline

Motivation

NB(Naive Bayes)在短文本上表现好，SVM在长文本上表现好。(论文里的观点，实际可能未必！)

NB(Naive Bayes)

贝叶斯公式（西瓜书里有比较有趣的介绍）。一些基本概念（ppt来自刘成林老师）：

image-20200614214846240

举例说明，假如一个要判定一个comment是不是有毒(toxic), 如果看不到文本内容情况下，自然可以用抛硬币的模型则p(toxic=1)=0.5, 如果看到了内容里的一个单词，比如‘fxxk’，那么p(toxic=1｜word=‘fxxk’)的概率可能要远远大于0.5，而目标就是求这个后验概率p(w|x)，$P(w_i)$ 为类别为i的概率,贝叶斯公式：

$$p(w_i|x)= \frac{p(x|w_i)P(w_i)}{p(x)}$$

因为贝叶斯公式有理论指导，理论情况下是百分百准确的决策器，（主要看概率密度函数的估计，先验概率是否准确等。）但是一般情况下对条件概率的估计不会完全准确（本例中使用最大似然估计）

举例：

包含某单词x，的toxic=1的文本为200个，toxic=1的文本总共为1000，那么就能用最大似然估计出p(x｜w=1)，估计出p(x|w=-1),

本论文中的贝叶斯：

image-20200614210256663

image-20200614210401856

image-20200614210339659

image-20200614225506214

上式是该模型的主要公式，其中r将作为模型的权重，r为特征f在正性文本的比率比上f在负性文本的比率。

$r = \log \frac{\text{ratio of feature $f$ in positive comments}}{\text{ratio of feature $f$ in negative comments}}$

为了能够结合SVM，本文中的正负类用1, -1 表示。

数据介绍：

image-20200614211002446

（159571, 426005）表示共有159571个评论，字典大小为426005。也即x是由159571个426005维的count vector 构成的矩阵。

第一眼看论文部分,没太看懂哪里用了贝叶斯，假设train_i为159571个评论文本中的第i个, 对toxic这个label进行分类。特征维度为V(V=426005)，特征矩阵即矩阵x，维度为（159571, 426005）的矩阵表示词典里的每个词在每个文本中出现的次数。最大似然估计条件概率：p(x|y=1), p(x|y=-1), 对应代码为 x[y==y_i].sum(0),y_i={0,1}, 这个维度为(1, 426005)表示每个特征出现在正/负文本中的文档数。求出包含某单词（特征）的正/负文本数，然后除以正/负文本的总个数，估计出 $p(x_j|w=0), p(x_j|w=1)$, j=1,…426005.其中$p(x_j|w=1)=p/||p||_1, p(x_j|w=-1)=q/||q||_1$ 然后论文用这两个设计了一个新的特征，r， 并且用来作为线性模型的权重。（详细见论文）

r的解释：

如果r>0,则表示该特征（该单词）更容易出现在正文本中，否则更容易出现在负文本中（结合线性模型比较符合经验判断。

线性模型的解释

image-20200614210256663

上图中的w=r,b为正负样本的数量比值，$x^{(k)}$为第k个case的特征向量。如果某个单词更容易出现在正样本中，则乘以一个正数的权重（这样的单词越多，文本越容易为正向），否则乘以负数的权重（这样的单词越多，越容易为负向）。b是现实正负样本的比值，总是偏向样本多的那个类别。

维度情况：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
x.shape
(159571, 426005)

y = train['toxic'].values
x[y==1].shape
(15294, 426005)

x[y==1].sum(0).shape
(1, 426005)

(y==1).shape
(159571,)

(y==1).sum()
15294

SVM

将贝叶斯部分设计的特征作为输入。其他部分就是普通SVM模型。

image-20200614212008887

上面文章的最后一段也直接说明了：信任NB，除非SVM具有非常高的置信度。

实现r和NBSVM的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
  def pr(y_i, y):
      print(y)
      p = x[y==y_i].sum(0)
      return (p+1) / ((y==y_i).sum()+1)
     
  x = trn_term_doc
  test_x = test_term_doc
  
  def get_mdl(y):
      y = y.values
      r = np.log(pr(1, y)/pr(0, y))
      m = LogisticRegression(C=4, dual=True )
      x_nb = x.multiply(r)
      return m.fit(x_nb, y), r
      
preds = np.zeros((len(test), len(label_cols)))

for i, j in enumerate(label_cols):
    print('fit', j)
    m,r = get_mdl(train[j])
    preds[:,i] = m.predict_proba(test_x.multiply(r))[:,1]

SVM用的是sklearn中的LogisticRegression。x是tf-idf生成的文本稀疏矩阵。

image-20200614211002446

（159571, 426005）表示共有159571个评论，字典大小为426005。也即x是由159571个426005维的count vector 构成的矩阵。

本任务中要预测多个label，16-21行代码是对多个label分别预测，模型是分开的。

总结

虽然论文里直说了

Posted on Edited on

高楼扔鸡蛋-memorization search

[TOC]

题解:

LeetCode 887. Super Egg Drop.

这是一道经典的谷歌面试题，某公司今天的笔试题出了这道题（只不过扔的不是鸡蛋）。

理解题意

这道题是总共有N层楼，K个鸡蛋，找到鸡蛋摔破的极限楼层。最小需要尝试多少次，

(表示我第一次看到这道题，以为是一道数学题，并且还想眼巴巴的算出来。)

考虑状态转移，很容易想到动态规划。

假设从h楼摔下，如果摔碎，则状态变为：（K-1, h-1) （即K-1个鸡蛋，总共有h-1楼）

如果没摔碎，则状态变为：（K, N-h)

由此很容易写出递推式：

$$dp[k][n] = min(1+max(dp[k-1][i-1], dp[k][n-i])) \ i=1…n $$

由递推式得到代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int superEggDrop(int K, int N) {
        int[][] dp = new int[K+1][N+1];
        for (int i = 1; i < K+1; i++) {
            for (int j = 1; j < N+1; j++) {
                dp[i][j] = j;
            }
        }
        for (int i = 2; i < K+1; i++) {
            for (int j = 1; j < N+1; j++) {
                for (int j2 = 1; j2 < j; j2++) {
                    dp[i][j] = Math.min(dp[i][j], Math.max(dp[i-1][j2-1], dp[i][j-j2])+1);   
                }
            }
        }
        return dp[K][N];
    }
}

递归版：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public int superEggDrop(int K, int N) {
        int[][] memo = new int[K + 1][N + 1];
        return dfs(K, N, memo);
    }
    public int dfs(int K, int N, int[][] memo){
        // base case
        if(N<=1 || K==1){
            return N;
        }
        // memorization
        if(memo[K][N]>0) 
            return memo[K][N];
        int min = N;
        for (int i = 1; i < N; i++) {
            int left = dfs(K-1, i-1, memo);
            int right = dfs(K, N-i, memo);
            min = Math.min(min, Math.max(left, right)+1); 
        }
        memo[K][N] = min;
        return min;
    }
}

这样会超时，优化！从迭代版的代码可以看出，时间复杂度为 $O(KN^2)$,其中搜索$dp[k][n] = min(1+max(dp[k-1][i-1], dp[k][n-i])) \ i=1…n $中的i可以用二分搜索。从而将时间复杂度将为$O(KNlogN)$.

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
class Solution {
    public int superEggDrop(int K, int N) {
        int[][] dp = new int[K+1][N+1];
        for (int i = 1; i < K+1; i++) {
            for (int j = 1; j < N+1; j++) {
                dp[i][j] = j;
            }
        }
        for (int i = 2; i < K+1; i++) {
            for (int j = 1; j < N+1; j++) {
                int lo =1, hi  = j;
                int min = dp[i][j];
                while(lo<hi){
                    int mid = lo+(hi-lo)/2;
                    int left = dp[i-1][mid-1];
                    int right = dp[i][j-mid];
                    min = Math.min(min, Math.max(left, right)+1);
                    if(left == right)
                        break;
                    else if(left < right)
                        lo = mid+1;
                    else
                        hi = mid;
                }
                dp[i][j] = min;
            }
        }
        return dp[K][N];
    }
}

递归版：

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
class Solution {
    public int superEggDrop(int K, int N) {
        int[][] memo = new int[K + 1][N + 1];
        return dfs(K, N, memo);
    }
    public int dfs(int K, int N, int[][] memo){
        // base case
        if(N<=1 || K==1){
            return N;
        }
        // memorization
        if(memo[K][N]>0) 
            return memo[K][N];
        int lo=1, hi =N, res = N;
        while(lo<hi){
            int mid = lo + (hi-lo)/2 ;
            int left = dfs(K-1, mid-1, memo);
            int right = dfs(K, N-mid, memo);
            res = Math.min(res, Math.max(left, right)+1);
            if(left==right){
                break;
            }else if(left<right){
                lo = mid+1;
            }else{
                hi=mid;
            }
        }
        memo[K][N] = res;
        return res;
    }
}

Posted on

并查集原理及联通分量个数问题

[TOC]

一、并查集

并查集是一个复杂的数据结构。在lc中大概有30道题左右（官方给出）

集合运算

常见的集合运算有：

交、并、补、差、判定一个元素是否属于某一集合

并查集： 集合并、查某元素属于什么集合

存储实现

使用树结构表示集合，树的每个结点代表一个集合元素

图示

image-20200513205634171

如图所示有两个集合，如何判定A-I九个元素属于哪个集合？

例：E 和 C是否为同一个集合。

可以不停的向上查找元素的父节点。判断是否有同一个根节点：

E->B->A

C->A

可见 E和C是同一集合

实际刷题中往往会给一个关系矩阵, 需要自己创建所有集合。

初始化每个元素为一个集合：

image-20200513210537820

有九个集合，通过关系矩阵在集合进行并操作：

例： 在关系矩阵中，A和B在同一集合。则将{A}和{B}并起来。即B指向A。

image-20200513211007745

最终构造出由关系矩阵得到的并查集

抽象数据

元素类型：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Node(object):
    def __init__(self, data, parent=None):
        self.data = data
        self.parent = parent
        
class DisjointSet(object):
    def __init__(self):
        self.map = {}
        self.num_sets = 0

    def make_set(self, data):
        node = Node(data)
        node.parent = node
        self.map[data] = node
        self.num_sets += 1
    
    def union(self, data1, data2):
        pass
    
    def find(self, data):
        pass

优化

随着树的高度的增加，find方法进行查询的时候，随着大量的union操作调用，导致复杂度的线性上升。导致树结构变成一个类似于线性表的结构。这种变化叫做树的退化，并查集算法需要对此问题进行优化。

定义Rank

对于每棵树，记录树的高度Rank，当进行union操作，合并两棵树时，如果其Rank不同，那么由Rank小树的连向Rank大的树。

image-20200513212325663

上图中左边的树Rank=3，右边的树Rank=2，Rank小的连向Rank大的。

路径压缩

image-20200513212846766

上图中C的根节点是A，可以直接将C指向A，进行路径压缩操作。

优化后的代码实现

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
class Node(object):
    def __init__(self, data, parent=None, rank=0):
        self.data = data
        self.parent = parent
        self.rank = rank
class DisjointSet(object):
    def __init__(self):
        self.map = {}
        self.num_sets = 0
    def make_set(self, data):
        node = Node(data)
        node.parent = node
        self.map[data]=node
        self.num_sets+=1
    def find(self, data):
        node = self.map[data]
        r = node
        while r!= r.parent:
            r = r.parent
        k = node
        while k!=r:
            j = k.parent
            k.parent = r
            k = j
        return r
    def union(self, data1, data2):
        parent1 = self.find(data1)
        parent2 = self.find(data2)
        if parent1.data == parent2.data:
            return
        if parent1.rank >= parent2.rank:
            if parent1.rank == parent2.rank:
                parent1.rank+=1
            parent2.parent = parent1
        else:
            parent1.parent = parent2
        self.num_sets -=1

LC #547

LeetCode第547题的答案就出来了：

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
class Node(object):
    def __init__(self, data, parent=None, rank=0):
        self.data = data
        self.parent = parent
        self.rank = rank
class DisjointSet(object):
    def __init__(self):
        self.map = {}
        self.num_sets = 0
    def make_set(self, data):
        node = Node(data)
        node.parent = node
        self.map[data]=node
        self.num_sets+=1
    def find(self, data):
        node = self.map[data]
        r = node
        while r!= r.parent:
            r = r.parent
        k = node
        while k!=r:
            j = k.parent
            k.parent = r
            k = j
        return r
    def union(self, data1, data2):
        parent1 = self.find(data1)
        parent2 = self.find(data2)
        if parent1.data == parent2.data:
            return
        if parent1.rank >= parent2.rank:
            if parent1.rank == parent2.rank:
                parent1.rank+=1
            parent2.parent = parent1
        else:
            parent1.parent = parent2
        self.num_sets -=1
class Solution:
    def findCircleNum(self, M: List[List[int]]) -> int:
        ds = DisjointSet()
        for i in range(len(M)):
            ds.make_set(i)
        for i in range(len(M)):
            for j in range(i+1, len(M)):
                if M[i][j] == 1:
                    ds.union(i, j)
        return ds.num_sets

Posted on

Pycharm 远程连接 Docker

[TOC]

引用：pycharm连接远程linux服务器的docker

为什么要用pycharm远程连接， docker

  1. 使用docker可以节省安装深度学习环境的时间。

  2. pycharm远程连接为了方便debug

安装Docker

  1. 首先要有一台服务器，最好装linux系统（推荐centos，稳定，当然稳定就意味着万年不更新）安装显卡驱动。

  2. 安装方式docker挺简单的，最好安装nvidia-docker，方便调用GPU，

  3. pull下来一个镜像。

有空的话可以写一篇docker相关的博客（不过如果只是pull下来一个深度学习环境，貌似没啥好写的）

pycharm连接docker

  1. 首先运行容器，以我的服务器实际运行命令为例：
1
docker run -p 6009:6006 -p 23:22 --name="torch-remote" -v /root/project:/workspace/project -it --gpus all pytorch_1 /bin/bash

6006端口是用来运行tensorboard的，这里重要的是22端口。如果希望通过ssh远程连接docker，需要对容器的22端口做端口映射。

更新容器的apt源，安装ssh和vim

1
2
3
apt-get update
apt-get install openssh-server
apt-get install vim

使用vim打开并修改配置文件，找到PermitRootLogin prohibit-password这一行，修改为PermitRootLogin yes，允许通过ssh远程访问docker。

1
vim /etc/ssh/sshd_config

创建docker中root用户的密码。

1
passwd root

启动ssh服务，至此，服务器端配置完毕。

1
service ssh restart

配置pycharm

在Tools-Deployment-Configuration中，按下图配置。注意Type选择SFTP，Port是步骤1映射的端口，Password是步骤5设置的密码。配置完成后，点击Test SFTP connection，测试连接是否成功。

image-20200424230134133

配置本地文件上传至docker的目录：

image-20200424230318034

在PyCharm-Preferences-Project Interpreter里，点击右上角的设置按钮，选择add remote，配置如下图。注意Python interpreter path指的是docker中python的路径。

![image-20200424230440610](/Users/wei/Library/Application Support/typora-user-images/image-20200424230440610.png)

然后一路next，可能需要更改一下Python interpreter path：改为docker中的python路径即可。

接着需要等待一会，待程序配置结束。点击Tools-Deployment-Automatic Upload打开文件自动上传功能，上传文件需要一定时间。接着我们就可以实现远程运行和调试啦。

![image-20200424230756766](/Users/wei/Library/Application Support/typora-user-images/image-20200424230756766.png)