https://docs.inertialsense.com/user-manual/reference/imu_specifications/

The following calculations convert the noise specifications from the IMX-5 inertial measurement unit (IMU) datasheet into usable standard deviation values for simulating sensor noise at a sampling rate of 100 Hz. IMUs typically provide specifications for gyroscope and accelerometer noise in terms of "Angular Random Walk" (ARW) and "Velocity Random Walk" (VRW), expressed per

and then adjusting them based on the sampling interval, yielding noise characteristics that realistically represent the IMU's behavior in a simulated environment.

Given IMU specifications for the IMX-5:

• Gyro Angular Random Walk (ARW): 0.16∘/hr−−√
  

Errors in inertial sensor measurements are accumulated over time, leading to drift in INS navigation outputs. While gyro bias is the main contributor, other factors, such as accelerometer bias and noise, are important to consider for balancing the overall error budget. 

A key benefit of inertial navigation is its self-contained nature as the system can maintain navigation continuity while other navigation aids are (temporarily) unavailable. For example, GNSS/INS mechanization can coast on inertial solution when GNSS is jammed. Yet, as described in the previous column on inertial fundamentals, integration is the main computational operation of the INS: sensor measurements (angular rates and non-gravitational acceleration components also referred to as specific forces) are integrated into navigation outputs (attitude, velocity and position). Measurement errors are integrated as well, which leads to a drift in navigation solution over time. As a result, inertial can be used to bridge over continuity gaps (such as GNSS interference areas), but over a limited time.

Understanding inertial error behavior is a critical component of the overall system design. It is addressed in this column.

Influence of Accelerometer Bias 

We start with a simple one-dimensional (1D) case where a platform moves along the x-axis of the horizontal frame. In this case, the double integration scheme completely defines the INS navigation mechanization because attitude determination, gravity addition and coordinate transformation are not required. A constant bias, b_accel, in accelerometer measurements propagates into velocity and position errors (δv and δr, respectively) as follows:

Influence of Gyro Bias

Gyro bias is first integrated into attitude errors and then propagates into velocity and position errors through coordinate transformation. To understand the error propagation mechanism, let’s consider a simplified two-dimensional (2D) case that is illustrated in Figure 1. 

In Figure 1(a) the relative angle, α, between the body-frame (x_b, z_b) and the navigation frame (x_N, z_N) is perfectly known. In this case, body-frame non-gravitational acceleration is translated exactly into its navigation frame components, a_x and a_z. When gyro bias, b_gyro, is present, it is integrated into the attitude error, δα, during the attitude determination step:

where δα is the initial attitude error. As a result, instead of being computationally aligned with the actual navigation frame, the body-frame is rotated into a tilted frame as shown in Figure 2 (b). In this case, the non-gravitational acceleration transforms as: 

or using the small angle approximations (i.e., cos(δα)≈1 and sin(δα)≈δα):

Hence, the error in the coordinate transformation, δα, leads to acceleration-domain errors, a_zδα and -a_xδα, that are then double integrated into position error. This leads to cubic growth of position error due to gyro bias. To illustrate, consider a stationary case where:

In this case, the coordinate transformation error, δa, is:

When integrated into position error, it becomes:

For a general 3D case, the consideration is substantially more involved mathematically. Yet, the nature of error propagation remains the same: gyro bias-induced position error growths proportionally to time³.

The Shuler Effect 

These considerations show accelerometer and gyro drift lead to unlimited error growth in INS navigation outputs. However, when navigating over the Earth surface, the horizontal error component becomes limited due to a Shuler effect. This effect introduces negative feedback (via the gravity addition step) into the error propagation mechanism, thus transforming the polynomial error growth into an oscillatory behavior. The oscillation period is rather large (about 84 minutes as we will see later in this section). As a result, it does not have much benefit for lower-grade inertial systems as their errors grow to unacceptable levels before the Shuler effect kicks in. Yet, Shuler oscillations effectively limit horizontal errors of a high-quality system such as a navigation-grade INS. Figure 2 illustrates the Shuler effect.

As shown in Figure 2, position error δx leads to the wrong gravitational acceleration vector being applied for the gravity addition step. This creates an acceleration error: 

Because the acceleration error is the second derivative of the position error , Equation 5 can be rewritten as:

Equation 6 is a well-known differential equation of a harmonic oscillator. Thus, the position error has an oscillatory behavior with its (Shuler) oscillation period, T_S, defined as: 

Table 1 shows the INS error propagation mechanism for different error sources when the Shuler effect is taken into account. 

It is noted that for time intervals that are significantly shorter than the Shuler period, the error behavior is well approximated by polynomials: e.g., ~t² and ~t³ for accelerometer and gyro bias components, respectively, as we derived previously. It is also worth mentioning that gyro bias is the only error source that leads to unlimited position error growth (even though over longer periods of time the growth becomes linear rather than cubic thanks to the Shuler feedback mechanism).

Unlike the horizontal channel, the vertical INS channel is inherently unstable. The reason is that gravitational acceleration reduces as the distance from the Earth surface increases. As a result, vertical position error is further amplified through the gravity addition rather than being dampened by it (as in the horizontal channel case). For this reason, higher-quality inertial systems that are designed to maintain stand-alone navigation over long periods of time are commonly augmented with a barometric altimeter to stabilize the vertical channel. 

Sensor Noise and First-Order Gauss-Markov Models

Approximation of accelerometer and gyro measurement errors by a constant bias is good for providing an insight into the key principles of INS error growth. Yet, for practical cases, it is too simplistic even for low-grade MEMS sensors. More adequate modeling of sensor measurement errors includes slow-varying bias and noise terms. Noise is represented by a zero-mean Gaussian random process. Slow-varying time bias is approximated by the first-order Gauss-Markov process. This process has an exponential autocorrelation function:

where 1/β is a time constant that is inversely proportional to the correlation time as illustrated in Figure 3. 

It is noted that for gyroscopes, the noise measurement is commonly characterized by a random angular error, n_δα, that is accumulated over time:

where n_δw is the rate measurement noise and ∆t is the measurement update interval. Accumulated noise is often referred to as a random walk akin to accumulating steps of random (positive and negative) lengths. Assuming uncorrelated noise samples at different measurement instances, the random walk variance is:

where n_δw is the rate measurement noise and ∆t is the measurement update interval. Accumulated noise is often referred to as a random walk akin to accumulating steps of random (positive and negative) lengths. Assuming uncorrelated noise samples at different measurement instances, the random walk variance is:

Other Error Sources 

Other sensor-related error sources that can contribute into the inertial error budget include scale-factors, g-sensitive errors and non-linearity sensitivity errors (e.g., squared acceleration scale factors). There are also two important error sources that are not related to sensor imperfections. The first one is packaging error, more specifically misalignment of sensitive axes from a perfect mutually orthogonal sensor orientation assumed by strapdown mechanization algorithms.

The second non-sensor error source is gravity modeling errors. For consumer-grade INS, a simple gravitational model assumes a downward pointed gravity with the absolute value of 9.8 m/s². As the quality of inertial sensors improves, a more precise gravitational model has to be used to balance the overall error budget. In this case, the orientation and absolute value of the gravity vector are modeled as a function of position. Modeling errors are characterized by gravity anomaly and gravity deflections as illustrated in Figure 4.

Both packaging errors and gravity modeling errors can lead to substantial navigation drift even in a (hypothetical) case where perfect accelerometers and gyroscopes are used. 

Example Error Models

Table 2 shows typical error parameters for different INS grades.

Examples of INS Error Budgets

This final section provides two examples of the INS error budget. The first example is shown in Figure 5 for a consumer-grade INS. Stand-alone inertial functionality over a 1-minute interval is considered.

In this case, gyro bias is clearly the largest contributor into the position error drift, while contributions of other error sources are about an order of magnitude lower. 

The second example is coasting with navigation-grade INS over a GNSS jamming region. In this case, a simulated flight scenario includes (a) an initial INS alignment segment where the GNSS is available (10 minutes), and (b) a complete GNSS outage (10 to 30 minutes). The inertial is first pre-calibrated using GNSS measurements (pseudoranges and carrier phase) and then switches into a stand-alone mode after GNSS becomes jammed. 

Figure 6 shows the contribution of different error sources, which also includes errors in the gravitational model, with modeling parameters illustrated in Figure 4. Interestingly, in this case, gravitational errors are the major 
contributor into the INS error budget after 10 minutes of coasting. Their contribution becomes more balanced with the gyro drift after 30 minutes of GNSS-denied operations. Nevertheless, in this example case, improving INS sensor performance will not significantly improve the overall system accuracy because the gravitational model has to be improved first. 

Conclusion

To summarize, errors in inertial sensor measurements are accumulated over time into drift in INS navigation outputs (position, velocity and attitude). Position errors grow proportionally to (i) time³ due to gyro biases, and (ii) to time² due to biases in accelerometer measurements. This polynomial error growth is stabilized by the Schuler effect for the horizontal channel when duration of stand-alone INS operation is comparable to 84 minutes. 

Gyro bias can be generally considered as the main error contributing factor, especially for longer coasting intervals. Yet, other error sources (accelerometer bias, gyro and accelerometer noise, scale-factors and non-linearity errors) are also important for balancing the overall error budget. In addition, 
sensor packaging and gravity modeling errors must be accounted for in INS error models. For example, a gravitational model error can be the main contributing factor for navigation-grade GNSS/INS when coasting over GNSS outages during relatively limited intervals of 10 to 30 minutes.

https://github.com/ggerganov/llama.cpp

https://github.com/ggml-org/llama.cpp

1、llama支持的分词器类型:

    SPM、SPM、WPM、UGM、RWKV

include/llama.h

2、LLM为什么需要分词器?

      由于神经网络模型不能直接处理文本，因此我们需要先将文本转换为数字，这个过程被称为编码 (Encoding)，其包含两个步骤：

1. 使用分词器 (tokenizer) 将文本按词、子词、字符切分为 tokens；
2. 将所有的 token 映射到对应的 token ID。

       from transformers import AutoTokenizer

       sequence = "Using a Transformer network is simple"

       tokens = tokenizer.tokenize(sequence)

       print(tokens)

       执行结果如下:

上述结果只是分词器的第一步工作，即将句子分解成:tokens, 但依然还是文本语言，而神经网络不能直接处理文本语言，神经网络智能处理张量，

因此分词器的第二步就是将tokens转换为token ID或称为inputs ID,python代码如下：

ids = tokenizer.convert_tokens_to_ids(tokens)print(ids)

当然上述的分词器两个步骤也可以用一个函数实现：

tokens_id = tokenizer.encode(sequence),直接得到tokens ID.

4、LLM分词器的逆过程:解码

      LLM通过分词器将输入语言文本变换成tokens ID,然后由tokens ID映射为张量，再由神经网络推理，得到推理结果，此时的结果依然为tokens ID,

而LLM最终输出和输入相同，即都为语言文本，因此需要将推理结果的tokens ID转换为语言文本：

decoded_string = tokenizer.decode([7993, 170, 11303, 1200, 2443, 1110, 3014])print(decoded_string)

请注意，decode方法不仅将索引简单的转换回token，而且还将作为相同单词一部分的标记组合在一起，以生成可读的句子。当我们使用预测新文本的模型时（无论是从提示生成的文本，还是像翻译或摘要这样的序列到序列问题），这种行为将非常有用。

你应该知道大模型的输入输出的单位是token，不是单词，也不是字母【在中文语境，不是词，不是字】，那么，token是什么呢？

虽然我们经常直接用token，但有的文献会翻译为标记。下文中看到标记，代表token。

Token是使用Tokenizer（翻译为分词器）分词后的结果，Tokenizer是什么呢？Tokenizer是将文本分割成token的工具。

在大模型中，Tokenizer有三种常见的分词方式：word level，char level，subword level,我会从英文（拉丁语系）和中文（汉语系）两个语言的角度来讲解。

word level是最简单的分词方式，就是将文本按照空格或者标点分割成单词。

比如，下面的句子：

Let's do some NLP tasks.

按照空格分词后，得到的token是：

Let's, do, some, NLP, tasks.

按照标点分词后，得到的token是：

Let, ', s, do, some, NLP, tasks, .

在中文中，分词是一个比较复杂的问题。中文没有空格，所以分词的难度要比英文大很多。下面举个例子：

我们来做一个自然语言处理任务。

一个可能的分词结果是：

我们，来，做，一个，自然语言处理，任务。

这种分词方式的优点是简单易懂，缺点是无法处理未登录词（Out-of-Vocabulary，简称OOV）。我们熟悉的jieba分词就是基于这种分词方式的。

jieba分词基于统计和规则的方法，结合了TF-IDF算法、TextRank算法等多种技术，通过构建词图（基于前缀词典）并使用动态规划查找最大概率路径来确定分词结果。此外，对于未登录词，jieba分词使用了基于汉字成词能力的HMM（隐马尔科夫模型）和Viterbi算法来进行识别和分词.

Character level是将文本按照字母级别分割成token。这样的好处是

• 词汇量要小得多；
• OOV要少得多，因为每个单词都可以从字符构建。

比如，下面的句子：

Let's do some NLP tasks.

按照字母分词后，得到的token是：

L, e, t, ', s, d, o, s, o, m, e, N, L, P, t, a, s, k, s, .

在中文中，Character level是将文本按照字级别分割成token。

比如，下面的句子：

我们来做一个自然语言处理任务。

按照字分词后，得到的token是：

我，们，来，做，一，个，自，然，语，言，处，理，任，务，。

这种方法也不是完美的。基于字符而不是单词，从直觉上讲意义不大：在英文中每个字母本身并没有多大意义，单词才有意义。然而在中文中，每个字比拉丁语言中的字母包含更多的信息。

另外，我们的模型最终会处理大量的token：使用基于单词（word）的标记器(tokenizer)，单词只会是单个标记，但当转换为字母/字（character）时，它很容易变成 10 个或更多的标记(token)。

在实际应用中，Character level和Word level都有一些缺陷。Sub-word level是一种介于Character level和Word level之间的分词方式。

Sub-word 一般翻译成子词

子词分词算法依赖于这样一个原则，即不应将常用词拆分为更小的子词，而应将稀有词分解为有意义的子词。

我们来看下面的例子：

Let's do Sub-word level tokenizer.

分词结果为：

let's</ w>, do</ w>, Sub, -word</ w>, level</ w>, token, izer</ w>, .</ w>,

</ w>通常表示一个单词word的结尾。使用 "w" 是因为它是 "word" 的首字母，这是一种常见的命名约定。然而，具体的标记可能会根据不同的实现或者不同的分词方法有所不同。

在中文中，似乎没有子词的概念，最小单元好像就是字了，那该如何使用子词分词？难道是偏旁部首吗？别着急，后面我们一起讨论。

字节对编码 (BPE) 最初是作为一种压缩文本的算法开发的，最早是由Philip Gage于1994年在《A New Algorithm for Data Compression》一文中提出，后来被 OpenAI 在预训练 GPT 模型时用于分词器（Tokenizer）。它被许多 Transformer 模型使用，包括 GPT、GPT-2、RoBERTa、BART 和 DeBERTa。

本文尝试用最直观的语言和示例来解释 BPE 算法。

本文的分词是在英文（拉丁语系）状态下进行的，中文状态下的分词会在后续的文章中讨论。

假设我们有一份语料，其中包含以下单词：

faster</ w>: 8, higher</ w>:6, stronger</ w>:7

其中，数字表示单词出现的次数。

注： </ w> 表示单词的结束，使用 "w" 是因为它是 "word" 的首字母，这是一种常见的命名约定。然而，具体的标记token可能会根据不同的实现或者不同的分词方法有所不同。

首先，我们将其中的每个字符作为一个 token，得到的 token 如下：

f a s t e r</ w>: 8, h i g h e r</ w>: 6, s t r o n g e r</ w>: 7

对应的字典如下：

'a', 'e', 'f', 'g', 'h', 'i', 'n', 'o', 'r', 's', 't', 'r</ w>'

第二步，我们统计每两个token相邻出现的次数，得到如下结果：

'fa':8,'as':8,'st':15,'te':8,'er</ w>':21,'hi':6,'ig':6,'gh':6,'he':6,'tr':7,'ro':7,'on':7,'ng':7,'ge':7

8+8+15+8+21+6+6+6+6+7+7+7+7+7=115

我们将出现次数最多的字符'e'和'r</ w>'对合并'er</ w>'【这就是byte pair 字节对的名称由来】，token变为：

f a s t er</ w>: 8, h i g h er</ w>: 6, s t r o n g er</ w>: 7

对应的字典变化为：

'a', 'f', 'g', 'h', 'i', 'n', 'o', 's','r', 't', 'er</ w>'

注意： 此时的'e'和'r</ w>'被'er'消融了，因为在token中除了'er'中有'e'和'r</ w>'其他地方都没有。

第三步，现在'er</ w>'已经是一个token了，我们继续统计相邻token出现的次数，得到如下结果：

'fa':8,'as':8,'st':15,'ter</ w>':8,'hi':6,'ig':6,'gh':6,'her</ w>':6,'tr':7,'ro':7,'on':7,'ng':7,'ger</ w>':7

我们将出现次数最多的字符't'和'er</ w>'对合并'ter</ w>'，token变为：

f a s ter</ w>: 8, h i g h er</ w>: 6, s t r o n g er</ w>: 7

对应的字典变化为：

'a', 'f', 'g', 'h', 'i', 'n', 'o', 's','r', 't', 'er</ w>', 'ter</ w>'

注意： 此时的'er</ w>'和't'都没有被'ter</ w>'消融了，因为在token中除了'ter</ w>'中有'er</ w>'，其他地方也有'er</ w>'和't'

重复上述步骤，直到达到预设的token数量或者达到预设的迭代次数；

这两个就是BPE算法的超参数，可以根据实际情况调整。

搞清楚了BPE，后续我们再来看wordpiece和sentencepiece。

WordPiece 是 Google 为预训练 BERT 而开发的标记化算法。此后,它在不少基于 BERT 的 Transformer 模型中得到重用,例如 DistilBERT、MobileBERT、Funnel Transformers 和 MPNET。它在训练方面与 BPE 非常相似,但实际标记化的方式不同。

WordPiece算法的名称由来可以追溯到它的核心功能——将单词（Word）分解成片段（Piece）。这个名称直观地反映了算法的基本操作。

本段的分词是在英文（拉丁语系）状态下进行的，中文状态下的分词会在后续的章节中讨论。

wordpiece 分词器的工作流程和BPE算法非常相似，只是在选择合并token的时候有所不同。

假设我们有一份语料，其中包含以下单词：

faster</ w>: 8, higher</ w>:6, stronger</ w>:7

其中，数字表示单词出现的次数。

注： </ w> 表示单词的结束，使用 "w" 是因为它是 "word" 的首字母，这是一种常见的命名约定。然而，具体的标记token可能会根据不同的实现或者不同的分词方法有所不同。

首先，我们将其中的每个字符作为一个 token，得到的 token 如下：

f a s t e r</ w>: 8, h i g h e r</ w>: 6, s t r o n g e r</ w>: 7

对应的字典如下：

'a', 'e', 'f', 'g', 'h', 'i', 'n', 'o', 'r', 's', 't', 'r</ w>'

注意：从第二步开始和BPE有所不同了

第二步，统计两个token之间的score，得到如下结果：

score=(freq_of_pair)/(freq_of_first_element×freq_of_second_element)

你可能或看到带log的公式，这是为了把除法转换成减法，方便计算。

'fa':1/8,'as':1/15,'st':1/15,'te':8/(21*15),'er</ w>':1/21,'hi':1/6,'ig':1/13,'gh':1/13,'he':1/21,'tr':1/15,'ro':1/7,'on':1/7,'ng':1/13,'ge':7/(13*21)

此时，我们将得分最高(1/6)的字符对'h'和'i'合并'hi'，token变为：

f a s t e r</ w>: 8, hi g h e r</ w>: 6, s t r o n g e r</ w>: 7

对应的字典变化为：

'a', 'f', 'g', 'e','r','n', 'o', 's','r', 't', 'hi'

重复上述步骤，直到达到预设的token数量或者达到预设的迭代次数（或其他条件）；

这就是wordpiece算法的超参数，可以根据实际情况调整。

注意：huggingface的berttokenize使用的是wordpiece的分词算法,但是和上面描述不同的地方在于,其中额外使用"##"用于表示某个subword 不是一个单词的开头

搞清楚了wordpiece，后续我们再来看unigram和sentencepiece。

在 SentencePiece 中经常使用 Unigram 算法,该算法是 AlBERT、T5、mBART、Big Bird 和 XLNet 等模型使用的标记化算法。

与 BPE 和 WordPiece 相比,Unigram是不同的思路: 它从一个较大的词汇表开始,然后从中删除token,直到达到所需的词汇表大小。

在训练的每一步,Unigram 算法都会在给定当前词汇的情况下计算语料库的损失。

然后,对于词汇表中的每个token,算法计算如果删除该token,整体损失会增加多少,并寻找损失最少的token。

这些token对语料库的整体损失影响较小,因此从某种意义上说,它们“不太需要”并且是移除的最佳备选。

Unigram 算法的第一步是构建一个基础词汇表,该词汇表包含所有可能的token。

这边，我们不再使用olympic的例子，而是采用HuggingFace官方的例子，原因是这个博主比较懒，不想计算那么多概率值。

假设我们有一个预料库，其中包含以下单词：

("hug", 10), ("pug", 5), ("pun", 12), ("bun", 4), ("hugs", 5)

其中，数字表示单词出现的次数

所以，我们的基础词汇表如下，这个词汇表包含所有子词sub-word：

["h", "u", "g", "hu", "ug", "p", "pu", "n", "un", "b", "bu", "s", "hug", "gs", "ugs"]

首先，我们计算这个基础词汇表中的所有子词的出现频次

("h", 15) ("u", 36) ("g", 20) ("hu", 15) ("ug", 20) ("p", 17) ("pu", 17) ("n", 16) ("un", 16) ("b", 4) ("bu", 4) ("s", 5) ("hug", 15) ("gs", 5) ("ugs", 5)

频次之和为210，那其中一个子词'ug'的概率就是 20/210

unigram模型是最简单的语言模型，它假设每个词都是独立的，所以我们可以直接计算每个词的概率。

比如'pug'的一种分词方式['p','u','g']的概率为：

$$p({[}^{\prime }{p}^{\prime }{,}^{\prime }{u}^{\prime }{,}^{\prime }{g}^{\prime }])=P{(}^{\prime }{p}^{\prime })\ast P{(}^{\prime }{u}^{\prime })\ast P{(}^{\prime }{g}^{\prime })=5/210\ast 36/210\ast 20/210=0.000389$$

而'pug'的另一种分词方式['pu','g']的概率为：

$$p({[}^{\prime }p{u}^{\prime }{,}^{\prime }{g}^{\prime }])=P{(}^{\prime }p{u}^{\prime })\ast P{(}^{\prime }{g}^{\prime })=5/210\ast 20/210=0.0022676$$

所以，对于'pug'这个词，我们可以计算出所有分词方式的概率，然后选择概率最大的那个分词方式。

['p','u','g'] 0.000389['pu','g'] 0.0022676["p", "ug"] : 0.0022676

我们会选择概率最大的['pu','g']作为'pug'的分词方式，当出现概率相同时，我们可以选择第一个。

通过这个方式，我们可以对所有的word进行tokenizer，并生成上文中说的较大的词汇表。

在实际中，会有一个小问题，那就是穷举的话计算量太大了，大到这个博主一时间都计算不过来。

求助： 假设我们的word有n个character，穷举的话一共有几种分词的方法？欢迎在留言区告诉我。

在实际中，我们可以使用维特比（Viterbi）算法来解决这个穷举问题。

维特比算法不在本文的讨论范围内，有兴趣的同学可以自行查阅资料。

此时，我们已经建立了一个较大的词汇表，接下来我们要删除一些token，直到达到我们的目标词汇表大小。

删除和裁员(打工人哭晕在厕所)的逻辑是一样的，谁对整体的影响最小，谁就被删除。

注意：基础的character是不能被删除的，我们需要它们来生成OOV的.

对于上文中的语料：

("hug", 10), ("pug", 5), ("pun", 12), ("bun", 4), ("hugs", 5)

假设我们经过上一步，已经对每一个word进行了分词,得到如下的分词和得分。

"hug": ["hug"] (score 0.071428)"pug": ["pu", "g"] (score 0.007710)"pun": ["pu", "n"] (score 0.006168)"bun": ["bu", "n"] (score 0.001451)"hugs": ["hug", "s"] (score 0.001701)

注意: 上述的tokenizer省略了每一个字母character，比如，"hug"的分词是["h","u","g","hug"]，但是为了简化，我们省略了["h","u","g"].

现在就是计算每个token对整体的影响了，这个影响loss就是这些score的负对数似然 negative log likelihood.

初始loss就是：

$$10\ast (-log(0.071428))+5\ast (-log(0.007710))+12\ast (-log(0.006168))+4\ast (-log(0.001451))+5\ast (-log(0.001701))=169.8$$

假设我们要去除的token是'hug',那么，受影响的是hug的分词和hugs的分词，我们可以更新'hug'后新token表的score:

"hug": ["hu", "g"] (score 0.006802)"hugs": ["hu", "gs"] (score 0.001701)

loss的变化为：

$$hug：-10\ast (-log(0.071428))+10\ast (-log(0.006802))=23.5$$

$$hugs：-5\ast (-log(0.001701))+5\ast (-log(0.001701))=0$$

总变化为23.5.

我们遍历所有的token，找到loss最小的那个token，然后删除它；

重复上述步骤，直到达到我们的目标词汇表大小。

现在你已经明白了BPE和Unigram算法的基本原理，接下来我们讨论一个分词器工具：SentencePiece.

太好了，终于到了大模型中使用最广泛的分词器: SentencePiece了.

之前介绍的分词器，英文（拉丁语系有空格）和中文（没有空格）会采用不同的分词方式，在大模型中，我们需要一个统一的分词器，这个分词器需要能够处理多种语言。

为此，我们需要一个统一的字符编码方式，这个编码方式需要能够处理多种语言，而且不会因为语言的不同而导致编码方式的不同。

SentencePiece是由Google开发的一种通用的分词器，它可以处理多种语言，它的名字就暗示了它的原理。

还记得之前的WordPiece吗？WordPiece是将word先切分成最小piece，然后再合新token。

而SentencePiece是将sentence切分成最小piece，然后再合并成token，（这是其中的BPE实现，当然如果是unigram实现，是另一个逻辑。但名称的由来就是这样。）

SentencePiece的特点包括：

• 纯数据驱动：直接从句子中训练分词和去分词模型，不需要预先分词；
• 语言无关：将句子视为Unicode字符序列，不依赖于特定语言的逻辑；
• 多种子词算法：支持BPE和Unigram算法；
• 快速且轻量：分割速度快，内存占用小；
• 自包含：使用相同的模型文件可以获得相同的分词/去分词结果；
• 直接生成词汇ID：管理词汇到ID的映射，可以直接从原始句子生成词汇ID序列；
• 基于NFKC的规范化：执行基于NFKC的文本规范化

unicode官网： https://home.unicode.org/

Unicode，全称为Unicode标准（The Unicode Standard），其官方机构Unicode联盟所用的中文名称为统一码，又译作万国码、统一字符码、统一字符编码，是信息技术领域的业界标准，其整理、编码了世界上大部分的文字系统，使得电脑能以通用划一的字符集来处理和显示文字，不但减轻在不同编码系统间切换和转换的困扰，更提供了一种跨平台的乱码问题解决方案。

这样，世界上所有的语言都用一个编码方式，对于大模型来说，只有一种语言，那就是Unicode。

在这个基础上，我们就可以用之前介绍的BPE或者Unigram算法来进行分词了。

BPE和Unigram算法的原理和实现，可以参考之前的文章。

最后，我们再来看下BPE的变种：BBPE。

BBPE是一种基于BPE的分词器，它是BPE的一种变种，是由Google Brain团队提出的。BBPE的全称是Byte-level BPE，它是一种基于字节级别的BPE分词器。

BBPE的核心思想是将文本中的字符对（UTF-8编码中是字节对）进行合并，以形成常见的词汇或字符模式，直到达到预定的词汇表大小或者无法继续合并为止。

它和BPE的区别在于，BPE是基于字符级别character的，而BBPE是基于字节byte级别的。

BBPE具有如下的优点：

• 跨语言通用性：由于它基于字节级别，因此可以更容易地跨不同语言和脚本进行迁移；
• 减少词汇表大小：通过合并字节对，BBPE可以生成更通用的子词单元，从而减少词汇表的大小；
• 处理罕见字符OOV问题：BBPE可以更有效地处理罕见字符，因为它不会为每个罕见字符分配单独的词汇表条目，而是将它们作为字节序列处理

在这个分词器系列分享中，我们从最简单的word level,character level开始，讲述了按词和字符分词的优缺点；

接着我们介绍了sub-word level分词器，包括BPE,WordPiece,Unigram等；

最后我们介绍了两个变种，一个是SentencePiece工具，它将多语言视为Unicode字符序列，不依赖于特定语言的逻辑，SentencePiece可以基于BPE或者Unigram算法，（也可是BBPE算法）；

另一个是BBPE算法，它是一种基于字节级别的BPE分词器，即最小单元是字节。

恭喜你已经掌握了分词器的基本原理和实现！

[1] 标记器（Tokenizer）

[2] word_vs_character_level_tokenization

[3] tokenization-in-natural-language-processing

[4] A New Algorithm for Data Compression

[5] wiki:BPE

[6] Byte-Pair Encoding tokenization

[7] WordPiece 标记化

[8] tokenizers小结

[9] Unigram tokenization

[10] github:sentencepiece

[11] Unigram tokenization

|-- example|  |-- main|     |-- main.cpp  # 推理llama 2的主函数|-- ggml-alloc.c #内存分配管理|-- ggml-alloc.h|-- llama.cpp # 整个llama 2的核心文件，包含所有重要interface|-- llama.h|-- ggml.c # 机器学习计算库.定义一些框架的基础数据结构和函数等|-- ggml.h|-- ggml-cuda.cu  #cuda版本的llama2 中的kernel实现与调用|-- ggml-cuda.h|-- ggml-opencl.cpp #opencl版本的llama2 中的kernel实现与调用|-- ggml-opencl.h|-- ... #其他

Llama.cpp 的工作流程

步骤一：解析和设置参数

参数可以控制推理过程的行为。例如，可以设置批量大小来提高推理速度，或者设置温度来控制生成文本的多样性。

1. 解析参数gpt_params_parse()。

2. 可设置的用户参数：

   1. --model 模型地址
   2. --color 颜色区分生成和输入
   3. --interactive 启用交互模式
   4. --prompt 输入的提示词
   5. --file 提示词文件

步骤二：加载模型

加载模型是 LLAMA.cpp 工作流程的第一步。模型文件包含模型的参数和权重，是推理过程所必需的。

1. 根据输入参数生成模型参数,llama_model_params
2. 使用 llama_load_model() 函数加载模型文件。

步骤三：创建 llama_context

llama_context是整个llama.cpp 重要数据结构。存储了各种参数，模型，prompt，backend（cpu/gpu），推理的计算结果。

llama_new_context_with_model()

步骤四：处理输入的 prompt

将输入的文本数据转换为模型可以理解的格式。也就是文本转化为词向量。

1. Tokenization：

   1. 使用llama_tokenize()对输入文本进行分词（Tokenization），将文本拆分为token（词元）。
   2. 再输出为一个整数类型token_id。

2. Embedding：

   1. 将分词后的文本转换为词嵌入向量（Embeddings），这通常涉及到查找预训练的词嵌入矩阵（词汇表）。词向量的长度为hidden_dim，是LLM模型训练后固定的。把每个词元token_id转化为一个向量。
   2. 对于某些模型，可能还需要进行位置编码（Positional Encoding）以保留序列中单词的顺序信息。
   3. 输出为（词元数 * hidden_dim）的矩阵。

步骤五：推理

这是LLAMA.cpp 工作流程的核心步骤。在这个步骤中，模型会根据输入数据生成预测结果。

推理包括两个部分逻辑

Prompt：将转化后的所有词向量进行Transformer-decode计算。

Generate：根据Prompt的结果和前一次生成的结果，进行Transformer-decode计算。最后返回预测结果

下面比较重要的函数

1. llama_decode()开始推理
2. llama_build_graph()构建计算图
3. llama_graph_compute()根据计算图调用对应算子，开始计算。

计算的结果是一组概率数组，表示预测的结果，存放在llama_context中。

步骤六：输出结果

对预测结果进行进一步处理。

1. 根据需要对预测结果进行采样，获取到要输出的token_id。采样（sample）是从模型预测的概率分布中生成下一个词或标记的过程。
2. 将token_id 转换回文本字符，llama_token_to_piece()。
3. 输出结果给用户。

步骤七：释放资源

释放资源是 LLAMA.cpp 工作流程的最后一步。释放模型句柄可以回收内存和计算资源。

调用 llama_free_model() 等函数释放模型资源。

以下是一些 LLAMA.cpp 工作流程的示例代码：

//解析参数gpt_params params;gpt_params_parse(argc, argv, params);// 加载模型llama_model_t *model = llama_load_model("llama-2-7b-chat");//创建llama_contextllama_context * ctx = llama_new_context_with_model(model, params);// 处理输入promptconst char *input = "This is an example input.";vector<llama_token> *embd_input = llama_tokenize(ctx, input);// 推理llama_decode(ctx, embd_input);// 输出结果cllama_token id = llama_sampling_sample(llama_sampling_context, ctx);string token_str = llama_token_to_piece(ctx, id)printf("%s\n", token_str);// 释放资源llama_free(ctx);llama_free_model(model);

3. 数学计算流程

3.1 模型架构

Llama的基础模型架构是Transformer，出自Attention Is All You Need。Transformer目前是大部分生成式人工智能的基础模型架构。

Llama的实现 - LLaMA: Open and Efficient Foundation Language Models

Llama相比基础Transformer，主要优化工作有下面几点：

• 使用RMSNorm作为标准函数
• 使用SwiGLU作为激活函数
• 使用RoPE作为位置编码函数

LLM的核心是Attention的计算。

Attention是计算每个token相对其他token的重要程度，结果是一组权重向量。

"算子"（Operator）通常指的是执行特定数学运算的函数或指令。类似于c/c++的operator关键字，

在机器学习中算子的对象是张量（Tensor）。

张量是用于数学计算的数据结构，它的基本构成是多维数组。

下面是Llama.cpp定义的算子

enum ggml_op {        GGML_OP_NONE = 0,        GGML_OP_DUP,        GGML_OP_ADD,        GGML_OP_ADD1,        GGML_OP_ACC,        GGML_OP_SUB,        GGML_OP_MUL,        GGML_OP_DIV,        GGML_OP_SQR,        GGML_OP_SQRT,        GGML_OP_LOG,        GGML_OP_SUM,        GGML_OP_SUM_ROWS,        GGML_OP_MEAN,        GGML_OP_ARGMAX,        GGML_OP_REPEAT,        GGML_OP_REPEAT_BACK,        GGML_OP_CONCAT,        GGML_OP_SILU_BACK,        GGML_OP_NORM, // normalize        GGML_OP_RMS_NORM,        GGML_OP_RMS_NORM_BACK,        GGML_OP_GROUP_NORM,        GGML_OP_MUL_MAT,        GGML_OP_MUL_MAT_ID,        GGML_OP_OUT_PROD,        GGML_OP_SCALE,        GGML_OP_SET,        GGML_OP_CPY,        GGML_OP_CONT,        GGML_OP_RESHAPE,        GGML_OP_VIEW,        GGML_OP_PERMUTE,        GGML_OP_TRANSPOSE,        GGML_OP_GET_ROWS,        GGML_OP_GET_ROWS_BACK,        GGML_OP_DIAG,        GGML_OP_DIAG_MASK_INF,        GGML_OP_DIAG_MASK_ZERO,        GGML_OP_SOFT_MAX,        GGML_OP_SOFT_MAX_BACK,        GGML_OP_ROPE,        GGML_OP_ROPE_BACK,        GGML_OP_ALIBI,        GGML_OP_CLAMP,        GGML_OP_CONV_TRANSPOSE_1D,        GGML_OP_IM2COL,        GGML_OP_CONV_TRANSPOSE_2D,        GGML_OP_POOL_1D,        GGML_OP_POOL_2D,        GGML_OP_UPSCALE, // nearest interpolate        GGML_OP_PAD,        GGML_OP_ARGSORT,        GGML_OP_LEAKY_RELU,        GGML_OP_FLASH_ATTN,        GGML_OP_FLASH_FF,        GGML_OP_FLASH_ATTN_BACK,        GGML_OP_WIN_PART,        GGML_OP_WIN_UNPART,        GGML_OP_GET_REL_POS,        GGML_OP_ADD_REL_POS,        GGML_OP_UNARY,        GGML_OP_MAP_UNARY,        GGML_OP_MAP_BINARY,        GGML_OP_MAP_CUSTOM1_F32,        GGML_OP_MAP_CUSTOM2_F32,        GGML_OP_MAP_CUSTOM3_F32,        GGML_OP_MAP_CUSTOM1,        GGML_OP_MAP_CUSTOM2,        GGML_OP_MAP_CUSTOM3,        GGML_OP_CROSS_ENTROPY_LOSS,        GGML_OP_CROSS_ENTROPY_LOSS_BACK,        GGML_OP_COUNT,    };

标记为红色的算子是计算Attention中会用到的。

3.2 Attention计算步骤和对应的算子

CUDA是LLM计算中最常采用的计算平台，我们以CUDA算子举例。

CUDA是NVIDIA推出的基于GPU的科学计算软件平台和代码模型，大范围用于机器学习领域的训练和推理的计算工作。它提供了一套API和工具，使得程序员可以编写能够在GPU上执行的并行程序。

Llama.cpp的所有CUDA核函数实现全部在ggml-cuda.cu

算法流程

把上面算法流程进行拆分

Q*K - MatMul - 矩阵乘法

CUDA算子：mul_mat_p021_f16_f32

static __global__ void mul_mat_p021_f16_f32(    const void * __restrict__ vx, const float * __restrict__ y, float * __restrict__ dst,    const int ncols_x, const int nrows_x, const int nchannels_x, const int nchannels_y)     {    }

除以sqrt(dk) - Scale - 缩放

CUDA算子： scale_f32

static __global__ void scale_f32(const float * x, float * dst, const float scale, const int k) {    const int i = blockDim.x*blockIdx.x + threadIdx.x;    if (i >= k) {        return;    }    dst[i] = scale * x[i];}

Mask - Mask

CUDA算子：diag_mask_inf_f32

static __global__ void diag_mask_inf_f32(const float * x, float * dst, const int ncols, const int rows_per_channel, const int n_past) {    const int col = blockDim.y*blockIdx.y + threadIdx.y;    const int row = blockDim.x*blockIdx.x + threadIdx.x;    if (col >= ncols) {        return;    }    const int i = row*ncols + col;    //dst[i] = col > (n_past + row % rows_per_channel) ? -INFINITY : x[i];    //dst[i] = x[i] - (col > n_past + row % rows_per_channel) * INT_MAX; // equivalent within rounding error but slightly faster on GPU    dst[i] = x[i] - (col > n_past + row % rows_per_channel) * FLT_MAX;}

softmax - SoftMax

CUDA算子：soft_max_f32

static __global__ void soft_max_f32(const float * x, const float * mask, const float * pos, float * dst, const int ncols_par, const int nrows_y, const float scale, const float max_bias, const float m0, const float m1, uint32_t n_head_log2) {}

• V - MatMul - 矩阵乘法

CUDA算子：mul_mat_vec_nc_f16_f32

static __global__ void mul_mat_vec_nc_f16_f32( // nc == non-contiguous    const void * __restrict__ vx, const float * __restrict__ y, float * __restrict__ dst, const int ncols_x, const int nrows_x,    const int row_stride_x, const int channel_stride_x, const int channel_x_divisor)     {    }

4. 工程优化

LLAMA.cpp使LLM能够在资源受限的环境中运行，例如在个人电脑、智能手机甚至树莓派等设备上。

已经对各种硬件环境进行了优化。

主要包括：

推理过程中llama_graph_compute()等函数中调用不同平台优化算子。

static void ggml_compute_forward(struct ggml_compute_params * params, struct ggml_tensor * tensor) {    GGML_ASSERT(params);    if (tensor->op == GGML_OP_NONE) {        return;    }#ifdef GGML_USE_CUBLAS    bool skip_cpu = ggml_cuda_compute_forward(params, tensor);//调用ggml-cuda.cu的CUDA算子    if (skip_cpu) {        return;    }    GGML_ASSERT(tensor->src[0] == NULL || tensor->src[0]->backend == GGML_BACKEND_TYPE_CPU);    GGML_ASSERT(tensor->src[1] == NULL || tensor->src[1]->backend == GGML_BACKEND_TYPE_CPU);#elif defined(GGML_USE_VULKAN)    const bool skip_cpu = ggml_vk_compute_forward_cpu_assist(params, tensor);#ifdef GGML_VULKAN_CHECK_RESULTS    if (skip_cpu) {        ggml_vk_check_results_1_cpu_assist(params, tensor);    }#endif    if (skip_cpu) {        return;    }    GGML_ASSERT(tensor->src[0] == NULL || tensor->src[0]->backend == GGML_BACKEND_TYPE_CPU);    GGML_ASSERT(tensor->src[1] == NULL || tensor->src[1]->backend == GGML_BACKEND_TYPE_CPU);#endif // GGML_USE_CUBLAS#ifdef GGML_USE_SYCL    bool skip_cpu = ggml_sycl_compute_forward(params, tensor);    if (skip_cpu) {        return;    }#endif // GGML_USE_SYCL

Gemma.cpp使用Hightway高性能cpp库进行针对CPU的计算优化。

算法优化 Lora - （Low-Rank Adaptation）优化和调整大型预训练语言模型的技术。能够减少计算资源和内存需求。

KVcache - 缓存下Attention计算中产生的Key和Value张量，减少计算量。

量化 - 量化通常涉及将浮点数（如32位的FP32）转换为低精度的表示，如8位的整数（INT8）或其他低精度格式。这种转换可以在不显著影响模型性能的情况下，显著降低模型的内存占用和计算需求。（这段由moonshot 生成）

Ps. 推理过程需要的显存

Llama 7B模型为例，使用FP16数据类型，每个FP16占2个字节。hidden_dim为4096，每个K和V 都要储存。一共32个Transformer Layer。

FP16 * hidden_dim * K,V * 32Layer * context_length = 2 * 4096 * 2 * 32 * context_length(取1024) = 512M

如果输入有1024个token就需要512M显存。