s-serenity

Posted 2024-11-06Updated 2024-11-06algorithm9 minutes read (About 1314 words)

BM25（Best Matching 25）是一种广泛应用于信息检索和文本挖掘的算法，它改进了传统的TF-IDF（Term Frequency-Inverse Document Frequency）方法，考虑了文档长度等因素，使得搜索结果更加准确。

TF-IDF

TF-IDF（Term Frequency-Inverse Document Frequency）是一种用于信息检索和文本挖掘的常用加权技术。它通过评估一个词在文档中的重要性来帮助识别文档的关键内容。TF-IDF 的主要思想是：如果某个词在文档中出现的频率高，并且在其他文档中出现的频率低，则该词对于该文档具有很高的区分能力。

基本概念

词频 (TF)：
- 定义：词频是指某个词在文档中出现的次数。
- 公式： $\text{TF}(t, d) = \frac{\text{词 } t \text{ 在文档 } d \text{ 中出现的次数}}{\text{文档 } d \text{ 中所有词的总数}}$
逆文档频率 (IDF)：
- 定义：逆文档频率反映了词的普遍重要性。如果一个词在很多文档中都出现，则它的 IDF 值较低；如果一个词只在少数文档中出现，则它的 IDF 值较高。
- 公式： $\text{IDF}(t, D) = \log \left( \frac{\text{文档总数}}{\text{包含词 } t \text{ 的文档数} + 1} \right)$ 其中，加 1 是为了避免分母为 0 的情况。
TF-IDF：
- 定义：TF-IDF 是词频和逆文档频率的乘积，用于评估一个词在文档中的重要性。
- 公式： $\text{TF-IDF}(t, d, D) = \text{TF}(t, d) \times \text{IDF}(t, D)$

BM25

基本思想

TF-IDF 的改进：
- 饱和函数：BM25 引入了一个饱和函数来调整词项的出现次数（TF），防止某个词项在文档中出现次数过多导致权重过大。
- 文档长度因子：BM25 考虑了文档的长度，引入了文档长度因子，使得文档长度对权重的影响不是线性的，这样可以更好地适应不同长度的文档。

计算公式

BM25 的具体计算公式如下：

$\text{BM25}(D, Q) = \sum_{i=1}^{n} \text{IDF}(q_i) \cdot \frac{f(q_i, D) \cdot (k_1 + 1)}{f(q_i, D) + k_1 \cdot (1 - b + b \cdot \frac{\text{len}(D)}{\text{avg\_len}})}$

其中：

$ n $ 是查询中的词项数。
$ q_i $ 是查询中的第 $ i $ 个词项。
$ \text{IDF}(q_i) $ 是逆文档频率，计算方式通常是 $ \log \frac{N - n(q_i) + 0.5}{n(q_i) + 0.5} $，其中 $ N $ 是文档总数，$ n(q_i) $ 是包含词项 $ q_i $ 的文档数。
$ f(q_i, D) $ 是词项 $ q_i $ 在文档 $ D $ 中的出现次数（TF）。
$ \text{len}(D) $ 是文档 $ D $ 的长度。
$ \text{avg_len} $ 是所有文档的平均长度。
$ k_1 $ 和 $ b $ 是调整参数，通常设置为 $ k_1 = 1.5 $ 和 $ b = 0.75 $。

Python 实现

以下是一个简单的 Python 实现 BM25 算法的例子：

import math
from collections import Counter

class BM25:
    def __init__(self, corpus, k1=1.5, b=0.75):
        self.k1 = k1
        self.b = b
        self.corpus = corpus
        self.doc_lengths = [len(doc) for doc in corpus]
        self.avg_doc_length = sum(self.doc_lengths) / len(self.doc_lengths)
        self.doc_count = len(corpus)
        self.doc_term_freqs = [Counter(doc) for doc in corpus]
        self.inverted_index = self.build_inverted_index()
    
    def build_inverted_index(self):
        inverted_index = {}
        for doc_id, doc_term_freq in enumerate(self.doc_term_freqs):
            for term, freq in doc_term_freq.items():
                if term not in inverted_index:
                    inverted_index[term] = []
                inverted_index[term].append((doc_id, freq))
        return inverted_index
    
    def idf(self, term):
        doc_freq = len(self.inverted_index.get(term, []))
        if doc_freq == 0:
            return 0
        return math.log((self.doc_count - doc_freq + 0.5) / (doc_freq + 0.5) + 1.0)
    
    def bm25_score(self, query_terms, doc_id):
        score = 0
        doc_length = self.doc_lengths[doc_id]
        for term in query_terms:
            tf = self.doc_term_freqs[doc_id].get(term, 0)
            idf = self.idf(term)
            numerator = tf * (self.k1 + 1)
            denominator = tf + self.k1 * (1 - self.b + self.b * (doc_length / self.avg_doc_length))
            score += idf * (numerator / denominator)
        return score
    
    def rank_documents(self, query):
        query_terms = query.split()
        scores = [(doc_id, self.bm25_score(query_terms, doc_id)) for doc_id in range(self.doc_count)]
        sorted_scores = sorted(scores, key=lambda x: x[1], reverse=True)
        return sorted_scores

# Example usage
corpus = [
    "The quick brown fox jumps over the lazy dog",
    "A quick brown dog outpaces a swift fox",
    "The dog is lazy but the fox is swift",
    "Lazy dogs and swift foxes"
]

bm25 = BM25(corpus)
query = "quick brown dog"
result = bm25.rank_documents(query)
print(f"BM25 Scores for the query '{query}':")
for doc_id, score in result:
    print(f"Document {doc_id}: {score}")

解释

初始化：
- corpus 是文档集合。
- k1 和 b 是调整参数。
- doc_lengths 存储每个文档的长度。
- avg_doc_length 是所有文档的平均长度。
- doc_term_freqs 存储每个文档中每个词项的出现次数。
- inverted_index 是倒排索引，用于快速查找词项在哪些文档中出现。
构建倒排索引：
- build_inverted_index 方法构建倒排索引，记录每个词项出现在哪些文档中及其频率。
计算逆文档频率：
- idf 方法计算词项的逆文档频率。
计算 BM25 得分：
- bm25_score 方法计算查询中每个词项在指定文档中的 BM25 得分。
排序文档：
- rank_documents 方法计算查询与每个文档的 BM25 得分，并按得分从高到低排序。

测试用例

查询："quick brown dog"
结果：输出每个文档的 BM25 得分，并按得分从高到低排序。

Posted 2021-08-29Updated 2024-11-04algorithma minute read (About 213 words)

机器学习(4)-决策树

决策树

决策树是一种用于分类和回归问题的监督学习算法。它通过树状图的结构来表示和推断决策规则。每个内部节点表示一个特征或属性，每个分支代表一个决策规则，而每个叶节点表示一个类别标签或一个数值。

决策树的学习过程形成了一个递归的分治算法，其中每个节点都对应于一个特征，并且通过节点上的决策规则将数据集分割成更纯的子集。在决策树的构建过程中，选择最佳特征和分割数据的目标是提高每个节点的纯度，使得决策树在训练数据上达到最佳的拟合效果。

Posted 2021-08-29Updated 2024-11-04algorithm6 minutes read (About 908 words)

机器学习(3)-支持向量机

支持向量机

支持向量机（Support Vector Machine，SVM）是一种用于分类和回归分析的监督学习算法。它的主要目标是找到一个超平面，将数据集划分成两个类别，同时使得两个类别中距离最近的数据点到该超平面的距离最大化。这两个最近的数据点被称为支持向量。

SVM 可以使用核函数来处理非线性可分的数据。核函数可以将输入特征映射到高维空间，从而在高维空间中找到一个线性超平面来解决原始空间中的非线性问题。

支持向量机公式

硬间隔支持向量机（Hard Margin SVM）

硬间隔支持向量机适用于线性可分的数据集。

\subsubsection*{优化问题}

目标是最大化间隔，同时保证所有样本都正确分类：

$\min_{\mathbf{w}, b} \frac{1}{2} \|\mathbf{w}\|^2$

约束条件：

$y_i (\mathbf{w} \cdot \mathbf{x}_i + b) \geq 1, \quad i = 1, 2, \ldots, n$

其中：

$ \mathbf{w} $ 是权重向量。
$ b $ 是偏置项。
$ \mathbf{x}_i $ 是第 $ i $ 个样本的特征向量。
$ y_i $ 是第 $ i $ 个样本的标签，取值为 $ \pm 1 $。

软间隔支持向量机（Soft Margin SVM）

软间隔支持向量机适用于线性不可分的数据集，允许一定程度的误分类。

\subsubsection*{优化问题}

目标是最大化间隔，同时引入松弛变量 $ \xi_i $ 来允许一些样本在间隔内部或错误分类：

$\min_{\mathbf{w}, b, \boldsymbol{\xi}} \frac{1}{2} \|\mathbf{w}\|^2 + C \sum_{i=1}^{n} \xi_i$

约束条件：

$y_i (\mathbf{w} \cdot \mathbf{x}_i + b) \geq 1 - \xi_i, \quad \xi_i \geq 0, \quad i = 1, 2, \ldots, n$

其中：

$ C $ 是正则化参数，控制误分类和间隔大小之间的平衡。
$ \xi_i $ 是松弛变量，表示第 $ i $ 个样本允许的误分类程度。

对偶问题

通过拉格朗日乘子法，可以将原始问题转化为对偶问题。

\subsubsection*{拉格朗日函数}

$\mathcal{L}(\mathbf{w}, b, \boldsymbol{\alpha}, \boldsymbol{\xi}, \boldsymbol{\mu}) = \frac{1}{2} \|\mathbf{w}\|^2 + C \sum_{i=1}^{n} \xi_i - \sum_{i=1}^{n} \alpha_i [y_i (\mathbf{w} \cdot \mathbf{x}_i + b) - 1 + \xi_i] - \sum_{i=1}^{n} \mu_i \xi_i$

其中：

$ \alpha_i $ 是拉格朗日乘子。
$ \mu_i $ 是非负的拉格朗日乘子。

\subsubsection*{对偶问题}

通过求解拉格朗日函数关于 $ \mathbf{w} $ 和 $ b $ 的偏导数并令其为零，可以得到对偶问题：

$\max_{\boldsymbol{\alpha}} \sum_{i=1}^{n} \alpha_i - \frac{1}{2} \sum_{i=1}^{n} \sum_{j=1}^{n} \alpha_i \alpha_j y_i y_j (\mathbf{x}_i \cdot \mathbf{x}_j)$

约束条件：

$0 \leq \alpha_i \leq C, \quad i = 1, 2, \ldots, n$ $\sum_{i=1}^{n} \alpha_i y_i = 0$

决策函数

通过求解对偶问题，可以得到支持向量机的决策函数：

$f(\mathbf{x}) = \sum_{i=1}^{n} \alpha_i y_i \mathbf{x}_i \cdot \mathbf{x} + b$

其中，只有当 $ \alpha_i > 0 $ 时，对应的样本 $ \mathbf{x}_i $ 才是支持向量。

核技巧（Kernel Trick）

对于非线性可分的数据集，可以通过核函数将数据映射到高维空间，使数据在高维空间中线性可分。

常见的核函数

线性核：
$K(\mathbf{x}_i, \mathbf{x}_j) = \mathbf{x}_i \cdot \mathbf{x}_j$
多项式核：
$K(\mathbf{x}_i, \mathbf{x}_j) = (\mathbf{x}_i \cdot \mathbf{x}_j + c)^d$
高斯核（RBF核）：
$K(\mathbf{x}_i, \mathbf{x}_j) = \exp\left(-\gamma \|\mathbf{x}_i - \mathbf{x}_j\|^2\right)$
Sigmoid核：
$K(\mathbf{x}_i, \mathbf{x}_j) = \tanh(\gamma \mathbf{x}_i \cdot \mathbf{x}_j + c)$

Posted 2021-08-29Updated 2024-11-04algorithm6 minutes read (About 864 words)

机器学习(2)-朴素贝叶斯

朴素贝叶斯

朴素贝叶斯（Naive Bayes）是一种基于贝叶斯定理的分类算法，被广泛用于文本分类和其他分类问题。它被称为”朴素”是因为它假设每个特征与其他特征之间都是相互独立的，这是一个较为简化的假设，但在实践中，朴素贝叶斯通常表现得相当好。

在朴素贝叶斯中，我们考虑一个分类问题，其中 A 是类别，而 B 是特征。贝叶斯定理用于计算给定特征的情况下某个类别的概率。我们可以使用训练数据中的频率估计概率，并计算每个类别的概率。然后，给定一个新的特征向量，我们可以使用贝叶斯定理计算每个类别的后验概率，并选择具有最高概率的类别作为预测结果。

朴素贝叶斯公式

贝叶斯定理

贝叶斯定理描述了在已知某些证据的情况下，某个假设的概率：

$P(A|B) = \frac{P(B|A) P(A)}{P(B)}$

其中：

( P(A|B) ) 是在事件 B 发生的情况下，事件 A 发生的后验概率。
( P(B|A) ) 是在事件 A 发生的情况下，事件 B 发生的条件概率。
( P(A) ) 是事件 A 发生的先验概率。
( P(B) ) 是事件 B 发生的边缘概率。

\subsection*{朴素贝叶斯分类器}

在朴素贝叶斯分类器中，假设特征之间相互独立。对于一个给定的样本 ( x = (x_1, x_2, \ldots, x_n) )，我们需要计算每个类别的后验概率 ( P(C_k | x) )，并选择具有最高后验概率的类别作为预测结果。

后验概率

根据贝叶斯定理，后验概率可以表示为：

$P(C_k | x) = \frac{P(x | C_k) P(C_k)}{P(x)}$

其中：

( P(C_k | x) ) 是在特征向量 ( x ) 给定的情况下，类别 ( C_k ) 的后验概率。
( P(x | C_k) ) 是在类别 ( C_k ) 给定的情况下，特征向量 ( x ) 的条件概率。
( P(C_k) ) 是类别 ( C_k ) 的先验概率。
( P(x) ) 是特征向量 ( x ) 的边缘概率。

条件概率

由于假设特征之间相互独立，条件概率 ( P(x | C_k) ) 可以分解为各个特征的条件概率的乘积：

$P(x | C_k) = P(x_1 | C_k) P(x_2 | C_k) \cdots P(x_n | C_k) = \prod_{i=1}^{n} P(x_i | C_k)$

类别先验概率

类别先验概率 ( P(C_k) ) 通常通过训练数据中的类别频率来估计：

$P(C_k) = \frac{\text{类别 } C_k \text{ 的样本数}}{\text{总样本数}}$

边缘概率

边缘概率 ( P(x) ) 可以通过全概率公式计算：

$P(x) = \sum_{k=1}^{K} P(x | C_k) P(C_k)$

但在实际应用中，通常不需要显式计算 ( P(x) )，因为它是所有类别的后验概率的归一化常数，不会影响类别的选择。

最大后验概率

选择具有最大后验概率的类别作为预测结果：

$\hat{C} = \arg\max_{C_k} P(C_k | x) = \arg\max_{C_k} \frac{P(x | C_k) P(C_k)}{P(x)} = \arg\max_{C_k} P(x | C_k) P(C_k)$

Posted 2021-08-29Updated 2024-11-04algorithm3 minutes read (About 440 words)

机器学习(1)-逻辑回归

逻辑回归

逻辑回归（Logistic Regression）是一种用于解决二分类问题的监督学习算法，尽管名称中包含”回归”一词，但实际上它用于分类任务。
逻辑回归使用一个假设函数（sigmoid函数），将输入特征的线性组合映射到一个在0和1之间的概率值。逻辑回归将概率值转换为二分类的决策，通常使用一个阈值（例如0.5）。逻辑回归使用交叉熵损失函数来衡量预测概率与实际标签之间的差异。损失函数的目标是最小化误差。

交叉熵损失函数（Cross-Entropy Loss）

$L(y, p) = -[y \log(p) + (1 - y) \log(1 - p)]$

逻辑回归的梯度计算

对于单个样本 $(x^{(i)}, y^{(i)})$，其损失为：

$L(w, b) = -[y^{(i)} \log(\hat{y}^{(i)}) + (1 - y^{(i)}) \log(1 - \hat{y}^{(i)})]$

其中 $\hat{y}^{(i)} = \sigma(z^{(i)})$ 是模型的输出，$z^{(i)} = w^T x^{(i)} + b$，而 $\sigma(z) = \frac{1}{1 + e^{-z}}$ 是 sigmoid 函数。

对于整个训练集，总损失 $J(w, b)$ 为所有样本损失的平均值：

$J(w, b) = -\frac{1}{m} \sum_{i=1}^{m} [y^{(i)} \log(\hat{y}^{(i)}) + (1 - y^{(i)}) \log(1 - \hat{y}^{(i)})]$

对 $w_j$ 的梯度

$\frac{\partial J(w, b)}{\partial w_j} = \frac{1}{m} \sum_{i=1}^{m} (\hat{y}^{(i)} - y^{(i)}) x_j^{(i)}$

对 $b$ 的梯度

$\frac{\partial J(w, b)}{\partial b} = \frac{1}{m} \sum_{i=1}^{m} (\hat{y}^{(i)} - y^{(i)})$

参数更新

在每次迭代中，参数 $w$ 和 $b$ 会根据计算出的梯度进行更新：

$w_j := w_j - \alpha \frac{\partial J(w, b)}{\partial w_j}$ $b := b - \alpha \frac{\partial J(w, b)}{\partial b}$

其中 $\alpha$ 是学习率，控制着每次参数更新的步伐大小。

TF-IDF

基本概念

BM25

基本思想

计算公式

Python 实现

解释

测试用例

决策树

支持向量机

支持向量机公式

硬间隔支持向量机（Hard Margin SVM）

软间隔支持向量机（Soft Margin SVM）

对偶问题

决策函数

核技巧（Kernel Trick）

常见的核函数

朴素贝叶斯

朴素贝叶斯公式

贝叶斯定理

后验概率

条件概率

类别先验概率

边缘概率

最大后验概率

逻辑回归

交叉熵损失函数（Cross-Entropy Loss）

逻辑回归的梯度计算

对 $w_j$ 的梯度

对 $b$ 的梯度

参数更新

Links

Categories

Recents

Archives

Tags

Subscribe for updates

follow.it