Perplexity in language model

1.PPL

PPL是用在自然语言处理领域(NLP)中,衡量语言模型好坏的指标。它主要是根据每个词来估计一句话出现的概率,并用句子长度作normalize,公式为

由公式可知,perplexity越小,模型越好。从公式最后一部分,感觉更像是描述GPT这种生成模型。

还有一种说法是:

2.Language Model

  • autoregressive (AR) language model

GPT:

 

  • autoencoding (AE)language model

BERT(denoising auto-encoding):

where mt = 1 indicates xt is masked.

3.Reference

文本生成中的解码策略

一.Language model decoding

given a sequence of m tokens as context, the task is to generate the next n continuation tokens to obtain the completed sequence . We assume that models compute using the common left-to-right decomposition of the text probability,

which is used to generate the generation token-by-token using a particular decoding strategy

二.Decoding Strategies

1.Maximization-based decoding

解码器的输出层后面通常会跟一个softmax函数来将输出概率归一化。如果词表比较大的话,softmax的计算复杂度会比较高(分母需要计算整个词表大小的维度)

  • Greedy decoding

每次选最高概率的一项作为输出,直到遇到结束符号,将这些输出的概率相乘,得到该sequence的概率。

缺点:每次选择都是最大的,但是整体的概率不一定是最大的,有可能错过最优的结果

  • Beam-search decoding

考虑到`Beam Size=2`,第一步选择概率最大的两个A和B,第二步选择AB和BB(橙色大箭头)。然后以选择的AB和BB继续向上传播,又出现了四种情况ABA/ABB/BBA/BBB,依然是选择综合概率最大的两个ABB/BBB。以此类推,直至句子结束。

缺点:

    • 由于beam search的概率是一個连续相乘的結果,越早遇到结束符号,所得到的概率会越大,所以更倾向于生成短文本。解决办法是对输出概率取log,然后相加求最大概率。
    • beam size过大会导致计算复杂度过高,时间复杂度为O(N*b*V),N为序列长度,b为beam size,v为词表大小
    • 语言模型通常为格式良好的文本分配高分,但较长文本的最高分往往是通用的、重复的和尴尬的。beam search的输出,与人讲话的概率分布,很不一样。

2.Stochastic Decoding

  • Sampling with temperature

解码器的输出层计算softmax时,通过改变T可以控制概率的形貌。当t大的时候,概率分布趋向平均,随机性增大(uniform sampling/pure sampling);当t小的时候,概率密度趋向于集中,即强者愈强,随机性降低(poisson distribution/greedy decoding)。
实验证明,降低t会改善生成的质量,但是会降低生成的多样性。
  • Top-k Sampling

从词表选择topk个词,使得概率之和最大,即

缺点:k的取值难以界定。k太小,会生成比较bland和generic的结果,即缺乏diversity;k太大,会退化成随机sampling(pure sampling),会陷入语义表达错误,即sample from tail distribution

  • Top-p Sampling(nucleus sampling)

丛词表选择p个概率之和大于给定阈值的词,即

采样集的大小将根据每个时间步长的概率分布动态调整。对于高的阈值来说,这一个小部分的词汇,就占据了绝大多数的概率—-核。

三.Implementation

def top_k_top_p_filtering(logits, top_k=0, top_p=0.0, filter_value=-float('Inf')):
    """ Filter a distribution of logits using top-k and/or nucleus (top-p) filtering
        Args:
            logits: logits distribution shape (vocabulary size)
            top_k >0: keep only top k tokens with highest probability (top-k filtering).
            top_p >0.0: keep the top tokens with cumulative probability >= top_p (nucleus filtering).
                Nucleus filtering is described in Holtzman et al. (http://arxiv.org/abs/1904.09751)
    """
    assert logits.dim() == 1  # batch size 1 for now - could be updated for more but the code would be less clear
    top_k = min(top_k, logits.size(-1))  # Safety check
    if top_k > 0:
        # Remove all tokens with a probability less than the last token of the top-k
        indices_to_remove = logits < torch.topk(logits, top_k)[0][..., -1, None]
        logits[indices_to_remove] = filter_value

    if top_p > 0.0:
        sorted_logits, sorted_indices = torch.sort(logits, descending=True)
        cumulative_probs = torch.cumsum(F.softmax(sorted_logits, dim=-1), dim=-1)

        # Remove tokens with cumulative probability above the threshold
        sorted_indices_to_remove = cumulative_probs > top_p
        # Shift the indices to the right to keep also the first token above the threshold
        sorted_indices_to_remove[..., 1:] = sorted_indices_to_remove[..., :-1].clone()
        sorted_indices_to_remove[..., 0] = 0

        indices_to_remove = sorted_indices[sorted_indices_to_remove]
        logits[indices_to_remove] = filter_value
    return logits

# Here is how to use this function for top-p sampling
temperature = 1.0
top_k = 0
top_p = 0.9

# Get logits with a forward pass in our model (input is pre-defined)
logits = model(input)

# Keep only the last token predictions of the first batch item (batch size 1), apply a temperature coefficient and filter
logits = logits[0, -1, :] / temperature
filtered_logits = top_k_top_p_filtering(logits, top_k=top_k, top_p=top_p)

# Sample from the filtered distribution
probabilities = F.softmax(filtered_logits, dim=-1)
next_token = torch.multinomial(probabilities, 1)

四.Reference

[Hard]鸡蛋掉落

887. 鸡蛋掉落

你将获得 K 个鸡蛋,并可以使用一栋从 1 到 N  共有 N 层楼的建筑。

每个蛋的功能都是一样的,如果一个蛋碎了,你就不能再把它掉下去。

你知道存在楼层 F ,满足 0 <= F <= N 任何从高于 F 的楼层落下的鸡蛋都会碎,从 F 楼层或比它低的楼层落下的鸡蛋都不会破。

每次移动,你可以取一个鸡蛋(如果你有完整的鸡蛋)并把它从任一楼层 X 扔下(满足 1 <= X <= N)。

你的目标是确切地知道 F 的值是多少。

无论 F 的初始值如何,你确定 F 的值的最小移动次数是多少?

 

示例 1:

输入:K = 1, N = 2
输出:2
解释:
鸡蛋从 1 楼掉落。如果它碎了,我们肯定知道 F = 0 。
否则,鸡蛋从 2 楼掉落。如果它碎了,我们肯定知道 F = 1 。
如果它没碎,那么我们肯定知道 F = 2 。
因此,在最坏的情况下我们需要移动 2 次以确定 F 是多少。
示例 2:

输入:K = 2, N = 6
输出:3
示例 3:

输入:K = 3, N = 14
输出:4
 

提示:

1 <= K <= 100
1 <= N <= 10000
class Solution {
   public:
    //方法一:暴力动规(超时),比较好理解
    int superEggDrop(int K, int N) {
        vector<vector<int>> dp(K + 1, vector<int>(N + 1, 0));
        //初始化
        for (int i = 1; i <= K; i++) {
            for (int j = 1; j <= N; j++) {
                dp[i][j] = j;
            }
        }
        for (int i = 2; i <= K;) {
            for (int j = 1; j <= N; j++) {
                for (int k = 1; k < j; k++) {
                    /**
                     * 最坏情况下的最少扔鸡蛋次数
                     * 当前鸡蛋总数为i,楼层总数为j,在第k层楼扔鸡蛋时,鸡蛋碎了往楼下走(dp[i-
                     * 1][k - 1],鸡蛋没碎dp[i][j - k],在第k层扔得算1次
                     */
                    dp[i][j] =
                        min(dp[i][j], max(dp[i - 1][k - 1], dp[i][j - k]) + 1);
                }
            }
        }
        return dp[K][N];
    }

    //方法二:数学动规,重新定义dp
    int superEggDrop2(int K, int N) {
        /**
         * dp[k][m]:当前状态为 k 个鸡蛋,尝试扔 m 次鸡蛋,
         * 返回这个状态下最高的确认楼层数
         */
        vector<vector<int>> dp(K + 1, vector<int>(N + 1, 0));
        int m = 0;
        while (dp[K][m] < N) {
            m++;
            for (int k = 1; k <= K; k++)
                /**
                 * 1. 鸡蛋没碎: dp[k][m - 1] 就是楼上的楼层数,因为鸡蛋个数 k
                 * 不变,扔鸡蛋次数 m 减一;
                 * 2. 鸡蛋碎了: dp[k - 1][m - 1]
                 * 就是楼下的楼层数,因为鸡蛋个数 k 减一,同时扔鸡蛋次数 m
                 * 减一;
                 * 3.是当前楼层数
                 *
                 */
                dp[k][m] = dp[k][m - 1] + dp[k - 1][m - 1] + 1;
        }
        return m;
    }
}

 

mac读取ntfs

1.查看ntfs u盘名

(base) MacBook-Pro-3:~ gonenlei$ diskutil list
/dev/disk0 (internal):
   #:                       TYPE NAME                    SIZE       IDENTIFIER
   0:      GUID_partition_scheme                         500.3 GB   disk0
   1:                        EFI EFI                     314.6 MB   disk0s1
   2:                 Apple_APFS Container disk1         500.0 GB   disk0s2

/dev/disk1 (synthesized):
   #:                       TYPE NAME                    SIZE       IDENTIFIER
   0:      APFS Container Scheme -                      +500.0 GB   disk1
                                 Physical Store disk0s2
   1:                APFS Volume Macintosh HD            206.5 GB   disk1s1
   2:                APFS Volume Preboot                 106.7 MB   disk1s2
   3:                (base) MacBook-Pro-3:~ gonenlei$ diskutil list
/dev/disk0 (internal):
   #:                       TYPE NAME                    SIZE       IDENTIFIER
   0:      GUID_partition_scheme                         500.3 GB   disk0
   1:                        EFI EFI                     314.6 MB   disk0s1
   2:                 Apple_APFS Container disk1         500.0 GB   disk0s2

/dev/disk1 (synthesized):
   #:                       TYPE NAME                    SIZE       IDENTIFIER
   0:      APFS Container Scheme -                      +500.0 GB   disk1
                                 Physical Store disk0s2
   1:                APFS Volume Macintosh HD            206.5 GB   disk1s1
   2:                APFS Volume Preboot                 106.7 MB   disk1s2
   3:                APFS Volume Recovery                1.6 GB     disk1s3
   4:                APFS Volume VM                      1.1 GB     disk1s4

/dev/disk2 (external, physical):
   #:                       TYPE NAME                    SIZE       IDENTIFIER
   0:     FDisk_partition_scheme                        *256.6 GB   disk2
   1:               Windows_NTFS gongel                  255.3 GB   disk2s1
   2:                       0x1B                         469.2 MB   disk2s2APFS Volume Recovery                1.6 GB     disk1s3
   4:                APFS Volume VM                      1.1 GB     disk1s4

/dev/disk2 (external, physical):
   #:                       TYPE NAME                    SIZE       IDENTIFIER
   0:     FDisk_partition_scheme                        *256.6 GB   disk2
   1:               Windows_NTFS gongel                  255.3 GB   disk2s1
   2:                       0x1B                         469.2 MB   disk2s2

2. sudo vim /etc/fstab

增加一行:LABEL=u盘名 none ntfs rw,auto,nobrowse

3. 接下来可以在 /Volumns下看到你的u盘

4.(可选)sudo ln -s  /Volumns ~/Desktop/Volumns

注意事项:

1.用了几次之后发现不能识别了?

原因是u盘拔出时没有正确弹出,请再次插入windows电脑然后正确弹出即可

2.需要重启吗?

不需要