tf-idf 與 BM25

tf–idfBM25 是兩個在資訊檢索 (IR) 裡面的經典演算法,也常被用在搜尋引擎技術上。

前陣子在練 Go,剛好找個主題來練,tf-idf 已經很熟了,但 BM25 沒有實際寫過,而自己的 blog 也累積了七千多篇,這個數量還算好用,不用自己另外 dump 維基百科的文章跑... (而且量太大)

第一步是拆成 token,我這邊就拿 bigram 拆了,但英文的部分把一整個詞當作一個單位,而非一個字母一個字母拆。

btw,這邊 tf-idf 與 BM25 的公式就請大家自己去維基百科上翻了...

tf-idf 概念上很簡單,而也沒有什麼 magic number 在公式裡面。

如果把 tf-idf 當一個 function 來看的話會是 score = tfidf(w, d, D),表示一個字 w 在一份文件 d 裡面的分數 (而 D 是所有文件)。

而 tf 只跟文件本身有關,可以預先算好放著,df 在後續文件新增刪除時都可以 incremental update,不需要重頭算,是個對於平行化運算很友善的演算法。

接著是看 BM25,如果把 BM25 當作一個 function 來看的話,會是 array = bm25(Q, D),針對 query words Q 與所有文章 D 傳回一個排序結果 array,裡面會是排序過的 document id,通常會包括分數。

而從公式可以看到 BM25 其實就是把 Q 裡面的每個字丟進 tf-idf 後加起來的變形,只是多考慮到文件大小對分數的影響,另外裡面引入了一些花招,像是 k1 與 b 這兩個常數項。

所以我就寫了兩個版本,一個是單純用 tf-idf 相加 (這樣長文章分數應該會比較高),另外一個是用 BM25 的公式跑... 算是趣味趣味的寫法。

算是清掉了之前一直放著的項目...

Kagi 訂閱數量過兩萬

看到 Kagi 公佈了訂閱數量破兩萬的新聞:「Celebrating our first 20,000 members」,翻了一下先前的文章,九月的時候才接近 9k:「Kagi 又恢復 $10/mo 的 Unlimited Search Plan 了」。

目前的目標看起來是訂在 50k (至少圖表上面的是 50k):

Internet Archive 上面查,可以看到九月到十月那波是漲最多的,差不多 22%:(出自 https://web.archive.org/web/20231011042040/https://kagi.com/stats 這邊)

依照 2022 年當時在「Kagi status update: First three months」這篇的說法,要 25k users 才能打平所有的開銷,雖然後來產品線改變蠻多的,但 25k 應該還是會算個重要的 milestone?

We are planning to reach sustainability at around 25,000 users mark, by further improving the product, introducing new offerings and pricing changes. With the product metrics being as good as they are, we should be able to reach this as our visibility increases.

現在看起來應該再給幾個月就會達到了,看起來會證明這塊小眾市場還是能做的?

GitHub 新版 Code Search 後面砍掉重練的過程

Hacker News 上看到「Lessons from building GitHub code search (youtube.com)」這篇在講 GitHub 的 Code Search (今年九月在 Strange Loop 上的演講),同時演講者 Luke Francl (帳號是 100k) 也有在 Hacker News 上留言回答一些問題:

影片裡面有不少資訊,挑我自己覺得有趣的地方整理一下。(不是依照影片的順序)

首先是現成的 search engine (Elasticsearch) 會濾掉太多資訊,其中一種例子就是在程式語言中,各種 token 像是 <= 以及 > 這些,都算是有用的資訊。

另外一方面是 Elasticsearch 的架構下沒有辦法利用 fork 的性質 (以及 Git 的 branch 性質),所以在處理 fork 類的 repository 會造成大量重複的資料,但 fork 的資料會有 99% 以上是與原來的 repository 相同。

舊的系統有 312 servers,包括了 24960 cores 與 20TB RAM,直接平均下來,每一台機器是 80 cores 與 65GB RAM,而跑一次 reindex 會需要幾個月的時間。

新的系統則降到了 130 servers,包括了 8320 cores,但記憶體加到了 65TB RAM,直接平均下來,每一台機器是 64 cores 與 512GB RAM,後面有列出來是 Azure 的 L64s v3,剛好就是 64 cores 與 512GB RAM,然後帶有 640GB temp disk 與 8*1.92TB 的 NVMe disk。

另外有提到這套新的系統雖然比較小 (除了記憶體),但卻是 3 clusters,這也剛好解釋記憶體變成原來三倍的原因。

而更重要的是,因為有多個系統,所以他們可以在上面對 production 等級資料量進行測試,而且不用害怕炸掉東西。

而且新的系統從零 rebuild 一次只需要幾天,不像之前需要好幾個月。這些改變使得 engineer 更容易進行個重嘗試與改善,而不用把精神花在要怎麼維持相容性。

回到 CPU 數量的下降,這邊沒有直接提到原因,但演講裡有提到有不少東西改用 Rust 寫,等於是從 JVM 換到原生程式碼,對於會有大量時間花在 CPU 運算的服務來說是個明顯的加分。

中間有兩個提到演算法的事情也蠻有趣的。

第一個是在 Delta compression 的地方,把 fork 後的差異當作是 delta,要最小化整個 fork tree 的成本,剛好把這個東西轉換成圖論的問題,就可以套用 Minimum spanning tree 這個經典的演算法,而且 MST 太經典,有很多變形也都有人研究過,有限成的演算法可以用。

另外一個提到的是 Alexander Neubeck,從 LinkedIn 上的資料可以看到他在 Google 的時候就是負責 Code Search,後來到 GitHub 看起來剛好加入對應的團隊,他開發了一個新的資料結構 Geometrics XOR filter 來解決 Delta compression 遇到的問題。

在 Hacekr News 上的討論可以看到有人抱怨還是缺了重要的功能,不過這畢竟是砍掉重練開始搞,而且是配合 Git 與 GitHub 的特性設計的,可以預期會缺東西,但就像演講裡提到的,新的架構可以讓整個團隊更快的迭代進行各種嘗試,後續就比較會是官方要取捨實作哪些功能了...

Kagi 又恢復 $10/mo 的 Unlimited Search Plan 了

Kagi 公告 $10/mo 的 Unlimited Search Plan:「Unlimited Kagi searches for $10 per month」。

今天公告以後可以看到有個比較抖一點的成長,但要再觀察看看是不是持續的:

翻了一下文章,還是沒看到為什麼要這樣做,尤其是財務上的理由... 最早從 $10/mo 漲到 $25/mo 就是成本問題,我的猜測是現在有量了所以 discount 比較好談 (從 9/6 的「Kagi Search Stats」的 8034 與現在的相比,的確可以看到一直在成長),然後談完 discount 後重算成本結構,發現有機會衝一波?

也有可能是 VC 那邊有進展?像是找到比較願意放手讓 Kagi 執行這樣的理念的 VC?

Anyway,$10/mo 又回來了...

Kagi 常態公開他們的訂閱數量

在「Kagi Search Stats (kagi.com)」這邊看到 Kagi 公開了訂閱數量:「Kagi Search Stats」。在「Changelog」裡面可以看到發表的資訊,可以看到也沒有給太多解釋。

現在是 7945 users + 232 family plan 的收入 (但不確定到底是合併算還是分開算),另外大約是 150K/day (週間) 與 110K/day (週末) 的 query 量。

成長速度看起來不太快,目前看起來是一個禮拜大概多 100 users,如果等比例的話,一年大概多 5k users?

交叉看一下去年九月的時候寫的資料,差不多就剛好是一年前的文章:「Kagi status update: First three months」。

一年前支出的部分大約是 $26K/mo 左右;粗粗算一下現在的 query 量,假設還是一樣的成本結構,現在大約是 $50K/mo,但今年多了很多 AI 的 API cost,所以應該還會再加上去...

We are currently serving around 2.1M queries a month, costing us around $26,250 USD/month.

一年前提到有 2.6k users,當時只有單一方案 US$10/mo;現在是 7.9k users,不過方案比較多,而且後來進來的人費用有調漲,如果還是拿以前的單價來算的話大約是 US$79k。

Kagi search is currently serving ~2,600 paid customers.

當年提到 $26k/mo 的收入差不多就只能 cover 基礎建設,人事費用就還得從各種 funding 支付;現在應該是能夠額外 cover 一些些人事的部分?

Between Kagi and Orion, we are currently generating around $26,500 USD in monthly recurring revenue, which incidentally about exactly covers our current API and infrastructure costs.

Brave Search 實作了自己的 Image Search

Hacker News 上看到 Brave Search 時作了自己的 Image Search,不再依靠 Bing 的資訊:「Brave Search launches own image and video search (brave.com)」。Brave 原始文章的標題比較長:「With our own image and video search, Brave Search now offers comprehensive independent results, giving users a fully-fledged, privacy-preserving choice outside of Big Tech」。

id=36990055 這邊有提到,這樣有五家搜尋引擎業者有自己的 image search infrastructure 了,包括了 BaiduBing、這次的 BraveGoogle 以及 Yandex

另外一個在討論裡面有提到的是以圖找圖的功能 (像是 id=36989140 這邊),其他幾家都有提供,而 Brave 目前剛出還沒有,不過看下面的回應是有這樣的計畫在跑,但也許優先權不高...

Kagi 繼續提供老用戶 $120/y 的方案?

收到 Kagi 的信,因為我是 unlimited searches 年繳用戶:

You are receiving this email because you have a Kagi legacy annual subscription with unlimited searches.

聽起來是這個方案會持續讓我們用舊價錢 renew?

This is to inform you that you will be able to keep this plan upon renewal. There is no action needed on your end, and your subscription will automatically renew as normal.

不過就他列出來的理由來說有點怪就是了,想要看看 unlimited search 在財務上是否可行?但成本不是算一算就知道了嗎...

We have recently changed the pricing plans [1], adding more searches to our plans. Ultimately in the future, we want to go be able to offer unlimited searches on our Professional plan to the broader public again, when economics allow.

Previously your subscription was set to renew into Early-adopter Professional plan [2]. By allowing a subset of our users (like you) to keep unlimited searches, we can get insights if this will be indeed economically viable. So we have decided to prolong the renewal of the unlimited annual legacy plan for customers who already have them.

[1] https://blog.kagi.com/plan-changes
[2] https://blog.kagi.com/update-kagi-search-pricing#existing

現在的 unlimited search plan 是 US$25/mo,年繳是 85 折,換算是 US$21.25/mo。

然後看了一下用量,最近幾個月用的量愈用愈多啊:

既然是 prolong,聽起來隨時有機會收回去?

Brave 宣佈 Brave Search 完全使用自己的資料,不用 Bing 的了

Brave 宣佈 Brave Search 獨立,不再使用 Bing 的資料了:「Brave Search removes last remnant of Bing from search results page, achieving 100% independence and providing real alternative to Big Tech search」。

依照 Brave 的說明,先前大約 7% 是來自 Bing 的 API:

Every Web search result seen in Brave Search is now served by our own index. We’ve removed all search API calls to Bing, which previously represented about 7% of query results.

但只要商業模式還是廣告,我應該不會去用... 但比起目前市場上一堆包其他家 search engine 的搜尋引擎來說,這的確是個好消息。

測了 PGroonga,PostgreSQL 上的 fulltext search engine

PostgreSQL 的 news 頁上看到「PGroonga 3.0.0 - Multilingual fast full text search」,想到一直沒有測過 PGroonga,就找台機器測了一下。

PGroonga 是以 Groonga 為引擎提供 PostgreSQL 全文搜尋能力的套件,是個能支援 CJK 語系的全文搜尋套件。

可以先看一下支援的 column type 與對應的語法:「Reference manual | PGroonga」,可以發現基本的 texttext[]varcharvarchar[] 都有支援,比較特別的是有 jsonb,看起來是對裡面的 text 欄位搜尋。

另外一個比較特別的是他會去配合 LIKE '%something%' 這樣的語法,對於無法修改的既有程式也會有幫助。

缺點方面,官方有提到產生出來的 index 會比其他的套件大,但畢竟我們在的環境要支援 CJK,場上的選手已經不多了。

另外一個缺點是目前 AWSRDSGCPCloud SQL 看起來都沒支援,要用的話得自己架 & 自己管,也許可以考慮用老方法,replication 接出來?

接下來就是安裝測試了,我在 x86-64 上的 Ubuntu 22.04 上面測試,就照著「Install on Ubuntu | PGroonga」這頁裡面的「How to install for system PostgreSQL」這段就可以了,裝系統的 PostgreSQL 14 以及 postgresql-14-pgroonga,之後要用 PostgreSQL 官方的新版的話可以參考「How to install for the official PostgreSQL」這段的安裝。

後續再到「Tutorial | PGroonga」頁,針對要搜尋的欄位下 index (這邊裱格式 memos,欄位是 content):

CREATE INDEX ON memos USING pgroonga (content);

官方的教學文件裡是用 SET enable_seqscan = off; 關閉 sequence scan,可以用 EXPLAIN 看到使用了 index:

test=# SELECT * FROM memos WHERE content &@ 'engine';
 id |                                content                                 
----+------------------------------------------------------------------------
  2 | Groonga is a fast full text search engine that supports all languages.
(1 row)

test=# EXPLAIN SELECT * FROM memos WHERE content &@ 'engine';
                                   QUERY PLAN                                    
---------------------------------------------------------------------------------
 Index Scan using memos_content_idx on memos  (cost=0.00..43.18 rows=1 width=36)
   Index Cond: (content &@ 'engine'::text)
(2 rows)

先拔掉 index:

test=# DROP INDEX pgroonga_content_index;
DROP INDEX

接著要塞資料,這邊拿 CQD 生的「中文假文產生器」來用,有 API 可以接比較方便。

test=# SELECT COUNT(*) FROM memos;
 count  
--------
 100000
(1 row)

Time: 15.495 ms

接著多跑幾次測試直接用 LIKE '%台北%' 去找,可以看到大概都在 150ms 以上:

test=# SELECT COUNT(*) FROM memos WHERE content LIKE '%台北%';
 count 
-------
   710
(1 row)

Time: 178.784 ms

接著來建立 index:

test=# CREATE INDEX ON memos USING pgroonga (content);
CREATE INDEX
Time: 17638.124 ms (00:17.638)

再跑幾次同樣的 query,可以看到巨大的改善:

test=# SELECT COUNT(*) FROM memos WHERE content LIKE '%台北%';
 count 
-------
   710
(1 row)

Time: 9.876 ms

Kagi 再次漲價

Kagi 在 2022 年九月的時候漲過一次:「Kagi 公佈了收費三個月後的進展」,當時的漲法是把本來不限次數搜尋的方案從 $10/mo 漲到 $19/mo,並且取名叫做 Kagi Unlimited。

這次則是宣佈要在 3/15 把無限搜尋的方案漲到 $25/mo:

We are also introducing the Ultimate plan with unlimited searches for $25/month.

而且本來的用戶 (應該是包括最早期的 $10/mo 與後來的 $19/mo 方案) 都會被強制改到 $25/mo:

Every existing subscriber will have their current subscription honored until expiration. That means if you are a subscriber at the time of the new plan rollout, you will still get unlimited searches as a part of your original plan until your existing subscription expires or is set to renew.

Hacker News 上的討論「Update to Kagi Search Pricing (kagi.com)」可以看到很多人都注意到 Kagi 想要投入 AI 的問題:

This is so incredibly disappointing and basically confirms that we're (at least in part) paying for their AI experiments - something that I personally am not at all interested in.

這次漲價然後把錢拿去投入 AI?而且看起來整個 Kagi 不是自己掌握 machine learning 技術,是用其他人的 API (應該就是 OpenAI)。這鐵定是一堆人不買單...

月底要 renew 的時候再來看看吧...