使用 Lisp 的线性时间余弦相似度
Cosine Similarity in linear time using Lisp
可以使用 for 循环在线性时间内计算两个列表的余弦相似度。我很好奇如何使用类似 Lisp 的语言来实现这一点。下面是我在 Python 和 Hy (Hylang) 中的代码示例。
Python:
def cos_sim(A,B):
import math as _math
n,da,db,d = 0,0,0,0
for a,b in zip(A,B):
n += a*b
da += a*a
db += b*b
da = _math.sqrt(da)
db = _math.sqrt(db)
d = da*db
return n / (d + 1e-32)
Hy (Lisp):
(import math)
(defn l2norm [a]
(math.sqrt (reduce + (map (fn [s](* s s)) a))))
(defn dot [a b]
(reduce + (map * a b)))
(defn cossim [a b]
(/ (dot a b) (* (l2norm a) (l2norm b))))
一个简单的选择是将 Python 版本从字面上翻译成 Hy，如下所示：
(defn cos_sim [A B]
(import math :as _math)
(setv [n da db d] [0 0 0 0])
(for [[a b] (zip A B)]
(+= n (* a b))
(+= da (* a a))
(+= db (* b b)))
(setv
da (_math.sqrt da)
db (_math.sqrt db)
d (* da db))
(/ n (+ d 1e-32)))
"我很好奇如何使用类似 Lisp 的语言实现这一点。" 这实际上取决于您使用的是哪种 Lisp。在 Scheme 中，您可能会执行类似于已发布的 Hy 解决方案的操作：
(define (cos-sim-1 u v)
(/ (dot-prod u v)
(* (norm u) (norm v))))
(define (dot-prod u v)
(fold-left + 0 (map * u v)))
(define (norm u)
(sqrt (fold-left (lambda (acc x) (+ acc (* x x)))
0
u)))
这在时间复杂度上是线性的，但可以通过仅传递一次输入来按常数因子进行改进。 Scheme 提供了一个命名的 let 构造，可用于将名称绑定到过程；这在这里很方便，因为它提供了一种构建点积和范数的简单机制：
(define (cos-sim-2 u v)
(let iter ((u u)
(v v)
(dot-product 0)
(U^2 0)
(V^2 0))
(if (null? u)
(/ dot-product (sqrt (* U^2 V^2)))
(let ((x (car u))
(y (car v)))
(iter (cdr u)
(cdr v)
(+ dot-product (* x y))
(+ U^2 (* x x))
(+ V^2 (* y y)))))))
这两个过程都假定输入列表的长度相同；添加一些验证代码来检查它可能很有用。请注意，fold-left 是 R6RS 方案中的标准，但其他标准为此依赖 SRFI，并且某些实现可能使用不同的名称，但 fold-left 功能通常可用（可能是 foldl 或reduce).
在 Common Lisp 中使用上面显示的任何一种基本方法都可以解决问题，尽管在 Common Lisp 中你会使用 labels 而不是命名 let。但通常会看到使用 loop 宏的 Common Lisp 解决方案。 Common Lisp 标准不保证消除尾部调用（尽管某些实现确实支持），因此显式循环比在 Scheme 中更常见。 loop 宏非常强大，解决此问题的一种方法是只传递一次输入列表：
(defun cos-sim (u v)
(loop :for x :in u
:for y :in v
:sum (* x y) :into dot-product
:sum (* x x) :into u2
:sum (* y y) :into y2
:finally (return (/ dot-product (sqrt (* u2 y2))))))
以下是一些互动示例：
方案（Chez方案）：
> (cos-sim-1 '(1 0 0) '(1 0 0))
1
> (cos-sim-1 '(1 0 0) '(-1 0 0))
-1
> (cos-sim-1 '(1 0 0) '(0 1 0))
0
> (cos-sim-1 '(1 1 0) '(0 1 0))
0.7071067811865475
> (cos-sim-2 '(1 0 0) '(1 0 0))
1
> (cos-sim-2 '(1 0 0) '(-1 0 0))
-1
> (cos-sim-2 '(1 0 0) '(0 1 0))
0
> (cos-sim-2 '(1 1 0) '(0 1 0))
0.7071067811865475
普通 Lisp：
CL-USER> (cos-sim '(1 0 0) '(1 0 0))
1.0
CL-USER> (cos-sim '(1 0 0) '(-1 0 0))
-1.0
CL-USER> (cos-sim '(1 0 0) '(0 1 0))
0.0
CL-USER> (cos-sim '(1 1 0) '(0 1 0))
0.70710677
我认为您提出的解决方案相当 'lispy'：构建几个简短、易于阅读的函数，并将其组合到您的解决方案中。例如：
(defun n (A B)
(sqrt (reduce #'+ (map 'list #'* A B))))
(defun da (A)
(sqrt (reduce #'+ (map 'list #'* A A))))
(defun db (B)
(sqrt (reduce #'+ (map 'list #'* B B))))
(defun cos-sim (A B)
(let ((n (n A B))
(da (da A))
(db (db B)))
(/ (* n n) (+ (* da db) 1e-32)))
但是，请注意 n、da 和 db 看起来非常相似。我们可以看看我们是否可以使它们成为一个函数或宏。在这种情况下，具有可选的第二个列表参数的函数就足够简单了。 （请注意，我以一种稍微奇怪的方式定义了 n 以强调这一点，但我们可能更喜欢 而不是 取平方根然后将其平方用于我们的最终计算。这将是通过检查传递可选参数（包括在下面的 B-p 中）很容易改变；我选择在组合函数内移动平方根）无论如何，这给了我们：
(defun d (A &optional (B A B-p))
(reduce #'+ (map 'list #'* A B)))
(defun cos-sim (A B)
(let ((n (d A B))
(da (sqrt (d A)))
(db (sqrt (d B))))
(/ n (+ (* da db) 1e-32))))
或者，使用 Loop 是非常常见的 Lisp-y，并且更直接地类似于 python:
(defun cos-sim (A B)
(loop for a in A
for b in B
sum (* a b) into n
sum (* a a) into da
sum (* b b) into db
finally (return (/ n (+ (sqrt (* da db)) 1e-32)))))
这是 Racket 中一种相当自然的（我认为）方法。从本质上讲，这是折叠一对数字序列的过程，所以这就是我们所做的。请注意，这没有使用显式赋值，并且还会将平方根拉高一个级别 (sqrt(a) * sqrt(b) = sqrt(a*b) 因为取根可能很昂贵（这在实践中可能无关紧要）。它也不会奇怪地添加一个小浮点数，我认为这是试图将一个可能不是浮点数的值强制转换为浮点数？如果是这样，那是错误的方法，而且它也不需要一种像 Racket（和大多数 Lisp）这样的语言，它努力在可能的情况下正确地进行算术运算。
(define (cos-sim a b)
;; a and b are sequences of numbers
(let-values ([(a^2-sum b^2-sum ab-sum)
(for/fold ([a^2-running 0]
[b^2-running 0]
[ab-running 0])
([ai a] [bi b])
(values (+ (* ai ai) a^2-running)
(+ (* bi bi) b^2-running)
(+ (* ai bi) ab-running)))])
(/ ab-sum (sqrt (* a^2-sum b^2-sum)))))
您可以相对轻松地将其转换为类型化的 Racket：
(define (cos-sim (a : (Sequenceof Number))
(b : (Sequenceof Number)))
: Number
(let-values ([(a^2-sum b^2-sum ab-sum)
(for/fold ([a^2-running : Number 0]
[b^2-running : Number 0]
[ab-running : Number 0])
([ai a] [bi b])
(values (+ (* ai ai) a^2-running)
(+ (* bi bi) b^2-running)
(+ (* ai bi) ab-running)))])
(/ ab-sum (sqrt (* a^2-sum b^2-sum)))))
这可能不会更快，但更麻烦。
虽然这可能会更快：
(define (cos-sim/flonum (a : (Sequenceof Flonum))
(b : (Sequenceof Flonum)))
: Flonum
(let-values ([(a^2-sum b^2-sum ab-sum)
(for/fold ([a^2-running : Flonum 0.0]
[b^2-running : Flonum 0.0]
[ab-running : Flonum 0.0])
([ai a] [bi b])
(values (+ (* ai ai) a^2-running)
(+ (* bi bi) b^2-running)
(+ (* ai bi) ab-running)))])
(/ ab-sum (assert (sqrt (* a^2-sum b^2-sum)) flonum?))))
不过我还没有检查过。
你的Hy例子已经是线性时间了。 None 的嵌套循环根据输入的长度乘以它们的迭代次数。可以对其进行简化以使其更易于查看
(import math)
(defn dot [a b]
(sum (map * a b)))
(defn l2norm [a]
(math.sqrt (dot a a)))
(defn cossim [a b]
(/ (dot a b) (* (l2norm a) (l2norm b))))
我觉得这个版本比Python版本更清晰，因为它更接近数学符号。
让我们也内联 l2norm 以使循环数更容易看到。
(defn cossim [a b]
(/ (dot a b)
(* (math.sqrt (dot a a))
(math.sqrt (dot b b)))))
Python 的 map() 是惰性的，所以 sum() 和 map() 一起只循环一次。您实际上拥有三个循环，每个循环对应 dot，其中 none 是嵌套的。您的 Python 版本只有一个循环，但每次迭代都会进行更多计算。理论上，逐行计算还是逐列计算都没有关系：乘法是可交换的，无论是行逐列还是逐列都是相同的计算次数
然而，在实践中，Python 确实对函数调用有很大的开销，所以我希望使用高阶函数的 Hy 版本比不使用高阶函数的 Python 版本慢在循环体中有任何函数调用。这是一个常数因子减速，所以它仍然是线性时间。
如果您想在 Python 中进行快速循环计算，请将您的数据放入矩阵中并使用 Numpy。
可以使用 for 循环在线性时间内计算两个列表的余弦相似度。我很好奇如何使用类似 Lisp 的语言来实现这一点。下面是我在 Python 和 Hy (Hylang) 中的代码示例。
Python:
def cos_sim(A,B):
import math as _math
n,da,db,d = 0,0,0,0
for a,b in zip(A,B):
n += a*b
da += a*a
db += b*b
da = _math.sqrt(da)
db = _math.sqrt(db)
d = da*db
return n / (d + 1e-32)
Hy (Lisp):
(import math)
(defn l2norm [a]
(math.sqrt (reduce + (map (fn [s](* s s)) a))))
(defn dot [a b]
(reduce + (map * a b)))
(defn cossim [a b]
(/ (dot a b) (* (l2norm a) (l2norm b))))
一个简单的选择是将 Python 版本从字面上翻译成 Hy，如下所示：
(defn cos_sim [A B]
(import math :as _math)
(setv [n da db d] [0 0 0 0])
(for [[a b] (zip A B)]
(+= n (* a b))
(+= da (* a a))
(+= db (* b b)))
(setv
da (_math.sqrt da)
db (_math.sqrt db)
d (* da db))
(/ n (+ d 1e-32)))
"我很好奇如何使用类似 Lisp 的语言实现这一点。" 这实际上取决于您使用的是哪种 Lisp。在 Scheme 中，您可能会执行类似于已发布的 Hy 解决方案的操作：
(define (cos-sim-1 u v)
(/ (dot-prod u v)
(* (norm u) (norm v))))
(define (dot-prod u v)
(fold-left + 0 (map * u v)))
(define (norm u)
(sqrt (fold-left (lambda (acc x) (+ acc (* x x)))
0
u)))
这在时间复杂度上是线性的，但可以通过仅传递一次输入来按常数因子进行改进。 Scheme 提供了一个命名的 let 构造，可用于将名称绑定到过程；这在这里很方便，因为它提供了一种构建点积和范数的简单机制：
(define (cos-sim-2 u v)
(let iter ((u u)
(v v)
(dot-product 0)
(U^2 0)
(V^2 0))
(if (null? u)
(/ dot-product (sqrt (* U^2 V^2)))
(let ((x (car u))
(y (car v)))
(iter (cdr u)
(cdr v)
(+ dot-product (* x y))
(+ U^2 (* x x))
(+ V^2 (* y y)))))))
这两个过程都假定输入列表的长度相同；添加一些验证代码来检查它可能很有用。请注意，fold-left 是 R6RS 方案中的标准，但其他标准为此依赖 SRFI，并且某些实现可能使用不同的名称，但 fold-left 功能通常可用（可能是 foldl 或reduce).
在 Common Lisp 中使用上面显示的任何一种基本方法都可以解决问题，尽管在 Common Lisp 中你会使用 labels 而不是命名 let。但通常会看到使用 loop 宏的 Common Lisp 解决方案。 Common Lisp 标准不保证消除尾部调用（尽管某些实现确实支持），因此显式循环比在 Scheme 中更常见。 loop 宏非常强大，解决此问题的一种方法是只传递一次输入列表：
(defun cos-sim (u v)
(loop :for x :in u
:for y :in v
:sum (* x y) :into dot-product
:sum (* x x) :into u2
:sum (* y y) :into y2
:finally (return (/ dot-product (sqrt (* u2 y2))))))
以下是一些互动示例：
方案（Chez方案）：
> (cos-sim-1 '(1 0 0) '(1 0 0))
1
> (cos-sim-1 '(1 0 0) '(-1 0 0))
-1
> (cos-sim-1 '(1 0 0) '(0 1 0))
0
> (cos-sim-1 '(1 1 0) '(0 1 0))
0.7071067811865475
> (cos-sim-2 '(1 0 0) '(1 0 0))
1
> (cos-sim-2 '(1 0 0) '(-1 0 0))
-1
> (cos-sim-2 '(1 0 0) '(0 1 0))
0
> (cos-sim-2 '(1 1 0) '(0 1 0))
0.7071067811865475
普通 Lisp：
CL-USER> (cos-sim '(1 0 0) '(1 0 0))
1.0
CL-USER> (cos-sim '(1 0 0) '(-1 0 0))
-1.0
CL-USER> (cos-sim '(1 0 0) '(0 1 0))
0.0
CL-USER> (cos-sim '(1 1 0) '(0 1 0))
0.70710677
我认为您提出的解决方案相当 'lispy'：构建几个简短、易于阅读的函数，并将其组合到您的解决方案中。例如：
(defun n (A B)
(sqrt (reduce #'+ (map 'list #'* A B))))
(defun da (A)
(sqrt (reduce #'+ (map 'list #'* A A))))
(defun db (B)
(sqrt (reduce #'+ (map 'list #'* B B))))
(defun cos-sim (A B)
(let ((n (n A B))
(da (da A))
(db (db B)))
(/ (* n n) (+ (* da db) 1e-32)))
但是，请注意 n、da 和 db 看起来非常相似。我们可以看看我们是否可以使它们成为一个函数或宏。在这种情况下，具有可选的第二个列表参数的函数就足够简单了。 （请注意，我以一种稍微奇怪的方式定义了 n 以强调这一点，但我们可能更喜欢 而不是 取平方根然后将其平方用于我们的最终计算。这将是通过检查传递可选参数（包括在下面的 B-p 中）很容易改变；我选择在组合函数内移动平方根）无论如何，这给了我们：
(defun d (A &optional (B A B-p))
(reduce #'+ (map 'list #'* A B)))
(defun cos-sim (A B)
(let ((n (d A B))
(da (sqrt (d A)))
(db (sqrt (d B))))
(/ n (+ (* da db) 1e-32))))
或者，使用 Loop 是非常常见的 Lisp-y，并且更直接地类似于 python:
(defun cos-sim (A B)
(loop for a in A
for b in B
sum (* a b) into n
sum (* a a) into da
sum (* b b) into db
finally (return (/ n (+ (sqrt (* da db)) 1e-32)))))
这是 Racket 中一种相当自然的（我认为）方法。从本质上讲，这是折叠一对数字序列的过程，所以这就是我们所做的。请注意，这没有使用显式赋值，并且还会将平方根拉高一个级别 (sqrt(a) * sqrt(b) = sqrt(a*b) 因为取根可能很昂贵（这在实践中可能无关紧要）。它也不会奇怪地添加一个小浮点数，我认为这是试图将一个可能不是浮点数的值强制转换为浮点数？如果是这样，那是错误的方法，而且它也不需要一种像 Racket（和大多数 Lisp）这样的语言，它努力在可能的情况下正确地进行算术运算。
(define (cos-sim a b)
;; a and b are sequences of numbers
(let-values ([(a^2-sum b^2-sum ab-sum)
(for/fold ([a^2-running 0]
[b^2-running 0]
[ab-running 0])
([ai a] [bi b])
(values (+ (* ai ai) a^2-running)
(+ (* bi bi) b^2-running)
(+ (* ai bi) ab-running)))])
(/ ab-sum (sqrt (* a^2-sum b^2-sum)))))
您可以相对轻松地将其转换为类型化的 Racket：
(define (cos-sim (a : (Sequenceof Number))
(b : (Sequenceof Number)))
: Number
(let-values ([(a^2-sum b^2-sum ab-sum)
(for/fold ([a^2-running : Number 0]
[b^2-running : Number 0]
[ab-running : Number 0])
([ai a] [bi b])
(values (+ (* ai ai) a^2-running)
(+ (* bi bi) b^2-running)
(+ (* ai bi) ab-running)))])
(/ ab-sum (sqrt (* a^2-sum b^2-sum)))))
这可能不会更快，但更麻烦。
虽然这可能会更快：
(define (cos-sim/flonum (a : (Sequenceof Flonum))
(b : (Sequenceof Flonum)))
: Flonum
(let-values ([(a^2-sum b^2-sum ab-sum)
(for/fold ([a^2-running : Flonum 0.0]
[b^2-running : Flonum 0.0]
[ab-running : Flonum 0.0])
([ai a] [bi b])
(values (+ (* ai ai) a^2-running)
(+ (* bi bi) b^2-running)
(+ (* ai bi) ab-running)))])
(/ ab-sum (assert (sqrt (* a^2-sum b^2-sum)) flonum?))))
不过我还没有检查过。
你的Hy例子已经是线性时间了。 None 的嵌套循环根据输入的长度乘以它们的迭代次数。可以对其进行简化以使其更易于查看
(import math)
(defn dot [a b]
(sum (map * a b)))
(defn l2norm [a]
(math.sqrt (dot a a)))
(defn cossim [a b]
(/ (dot a b) (* (l2norm a) (l2norm b))))
我觉得这个版本比Python版本更清晰，因为它更接近数学符号。
让我们也内联 l2norm 以使循环数更容易看到。
(defn cossim [a b]
(/ (dot a b)
(* (math.sqrt (dot a a))
(math.sqrt (dot b b)))))
Python 的 map() 是惰性的，所以 sum() 和 map() 一起只循环一次。您实际上拥有三个循环，每个循环对应 dot，其中 none 是嵌套的。您的 Python 版本只有一个循环，但每次迭代都会进行更多计算。理论上，逐行计算还是逐列计算都没有关系：乘法是可交换的，无论是行逐列还是逐列都是相同的计算次数
然而，在实践中，Python 确实对函数调用有很大的开销，所以我希望使用高阶函数的 Hy 版本比不使用高阶函数的 Python 版本慢在循环体中有任何函数调用。这是一个常数因子减速，所以它仍然是线性时间。
如果您想在 Python 中进行快速循环计算，请将您的数据放入矩阵中并使用 Numpy。