zw-fast-quantile: Approximate Quantile for high-speed data stream in Rust
A couple of weeks ago I exchanged messages with ljw1004, where he was surveying fast quantiles implementation in rust. He conducted a thorough benchmark against the GK01 and CKMS algorithms in the postmates/quantiles crate, in order to understand the tradeoffs among the error rate, memory usage and the update/query time. He mentioned the Zhang Wang algorithm in a literature review, where I later found that it was actually adopted in the boosted tree implementation in Tensorflow. I got intrigued and decided to roll my sleeves and give it a shot to implement the algorithm in rust
I spent a few days to read the paper and read the reference implementation done by jasonge27 in C++. The C++ implementation only implemented the fixed size approach in the paper but lack the generalized approach to support the online streaming update. I read the paper carefully and implement the generalized algorithm and then we have zw-fast-quantile crate.
The naive benchmark with criterion shows that the update operation is 2.6x faster than GK01 implementation in postmates/quantiles
zw unbound quantile update
time: [60.780 us 60.855 us 60.936 us]
change: [-1.4032% -0.9510% -0.5005%] (p = 0.00 < 0.05)
Change within noise threshold.
Found 8 outliers among 100 measurements (8.00%)
2 (2.00%) high mild
6 (6.00%) high severe
gk quantile update time: [156.84 us 157.02 us 157.24 us]
change: [-0.1907% -0.0503% +0.0969%] (p = 0.50 > 0.05)
No change in performance detected.
Found 11 outliers among 100 measurements (11.00%)
6 (6.00%) high mild
5 (5.00%) high severe
and query operation is 1.5x faster than GK01
zw unbound quantile query
time: [229.62 ns 230.16 ns 230.77 ns]
change: [+1.3422% +1.8105% +2.2504%] (p = 0.00 < 0.05)
Performance has regressed.
Found 11 outliers among 100 measurements (11.00%)
3 (3.00%) high mild
8 (8.00%) high severe
gk quantile query time: [350.21 ns 350.48 ns 350.76 ns]
change: [-0.4638% -0.3109% -0.1670%] (p = 0.00 < 0.05)
Change within noise threshold.
Found 8 outliers among 100 measurements (8.00%)
1 (1.00%) low severe
2 (2.00%) high mild
5 (5.00%) high severe
It matches with the emprical study from the paper that it is able to achieve 200-300x speedup over GK01.
To benchmark the memory usage, by storing complete 100M values in the Vec
and calculating the quantiles is using up 7812k
of heap, and with the error rate set to 0.01
the zw-fast-quantile
is only using up 1947k
of heap. It looks like it fulfills the goal of approximate quantile by saving the storage size without sacrificing the precision too much.
Implementing zw-fast-quantile
is a lot of fun and I learned a lot. By reading the review paper now I understand we can categorize the approximate quantile algorithm by different use cases. They could be
- Streaming Model: Your data would arrive one by one and you might not know the size of your stream beforehand. You should be able to calculate the result in one pass without blowing up the memory. You might also improve the algorithm complexity if you know that you just gonna query the quantiles for the trailing N values.
- Distributed Model: where you have a network of nodes, each of them have some values. However, the communication cost is high and you would like to avoid the communication cost as much as possible.
- Update Time: In the real-time application like video/audio streaming, your data update would be very fast and it requires you the low latency on your update time. You would like to strike a balance between update time and the space complexity and accuracy.
- Data Skewness: The famous t-digest would leverage on the fact where the error percentage is more imporatnt to the 99th percentile than 50th percentile. By leveraging the data skewness you can invent another set of algorithms.
zw-fast-quantile
is falling on the category 3, and it is good to know that it influenced the implementation in Tensorflow’s boosted trees. It could be another handy algorithm put in your toolbox and use it when the use case is right.
對於投資想法的一些轉變
前陣子看了阿堯跟威宇最新上傳的 youtube 影片關於對於投資的再思考,我也想花時間紀錄一下自己對於投資理解的改變以及手法上的改變。
對於投資跟投機的定義,市場上對於不同人一直有不同的定義。許多人會依照自身經驗,把比較不熟悉跟新生的事物,或是基本面比較模糊的東西就直接定義成投機。對照自己學習的來說,與其因為符號的關係而把事物認定成二元是本末倒置,事實上實際的運作更有可能的是一個光譜。這有點像是李小龍開創的 Mixed Martial Art,把原本各個流派有用的理論結合成現代武術,或是按照實證醫學的講法可能就是結合運動科學跟實驗精神去打造實證武術。我自己的路程由於工程師背景最早其實接觸的是 Quant,但意識到 Quant 基本上是拼機器跟基礎建設的軍備競賽而轉向基本面,對於傳統技術面來說大概已經比不太過經過實證統計的 Quant,大概只有在對手比較弱或散戶組成比較多的市場還顯著有效,記得有看過索羅斯的前交易員說傳統技術面在美股已經不太有效,但也許像是陸股或台股之類散戶組成比較多的地方大概還是有效,只是弱化而已。正由於手法如此多種而自己都多少接觸過,先來說說我自己覺得不同面向的投資定義方式
- 不需要在乎明天市場開不開,而關注商業競爭本身。價值投資人跟或是激進投資人以及 PE 等等大概落於此光譜
- 在乎市場是否開,但關注於期望值,而在乎市場是否開的長短以及多少主觀判斷來決定了是類似 Event-Driven 投資人,或是像是 cis 類型的瘋狗流,以及是全自動交易的 Quant
- 造市商,也就是所謂的高頻交易,這幾乎快是市場的基礎建設,比較難說是純粹的投資。
這幾種定義反應的是對於這世界理解,自身的限制,能力以及與哲學上的態度。由於你的交易總是會有不如預期的時候,如果你沒有一套自己的哲學跟邏輯論述,在交易不如預期的時候會陷入進退失據的狀態。在最開始的時候雖然我能接受純技術面或 Quant 能夠賺錢,但自己操作的時候是無法接受純技術面去操作的,主要是心理面無法克服。隨著越讀越多,還有實際看到其他人找到市場中暫時 displacaement 的部分去博弈,漸漸反思自己的整體作法而逐漸改變。
能夠調整主要是意識到,其實不只在投資中,我們在生活中經常依賴所謂的技術面來外包我們的判斷給其他人,就算是那些堅稱自己做價值投資的人,我是很難想像他們在生活中不曾因為某些餐廳大排長龍而,或是在新聞中看到比較多次關鍵詞而被影響去吃一些餐廳。現代社會是複雜的而個人時間有限,對於工程師來說就好像是一個複雜的分散式系統一樣,而我們不可能讀完所有的原始碼,而我們也並沒有一個 dashboard 來追蹤經濟這個機器的每一個面向。所以這時候難免會需要依賴於一些看似巫術的指標去逼近,只要逼近得足夠好不妨礙到我們生活就沒必要改變,除非是指標不夠準而需要精進。反應回交易,這就是必須承認我們實在玩 partial information 的遊戲,如何去權衡在自己的主場中玩 full information 的遊戲或是依賴於一些指標去逼近,就依賴於自己的哲學。而我自己是比較傾向於索羅斯定義的反身性以及他老師 Carl Popper 的科學哲學,就算你相信自己在玩 full information 的遊戲,很多事情是只能被証偽的,相信自己在玩 full information 跟使用巫術來選股,哲學上在被証偽之前可能都是被金融市場視為非無效,這該怎麼取捨還是取決於你自己的貝氏機率的 prior,而這個 prior 很可能決定於你出身的時代,你經歷過的事,當這些成為市場參與者的心理共識時,又會進一步改變市場結構。
說到共識,投資是一個尋求共識的過程,而有些方法就是比較容易說服別人。而所謂的別人,就是市場中資金的參與者,這會根據散戶的比率而造成某些現象在不同市場的差異,因為所需說服的人不同。有些研究說歷史上或有價值跟成長投資的風格切換週期,通常成長股表現比較好是在 Big Debt Cycle 裡面的經濟成長週期,而價值表現比較好通常是經濟走出低谷剛進入復甦的階段。我覺得就是市場在不同的階段,市場上的參與者具有說服力的說詞是不同的,在成長週期中,業績成長就是一番兩瞪眼,不需要多聰明都可以明白。而困境反轉是比較有難度的,畢竟原本的氣氛可能是十分悲觀,但只要業績沒有那麼慘,就可以用數據說服市場的參與者。那究竟能不能用一些指標來知道何時會風格切換呢?目前研究應該是覺得沒辦法,所以反應在自己的作法就是類似艾謝克那樣,用總經資訊像是零售,美元強弱,PMI 等等判斷持股水位,跟風格的倉位。總經方面的資訊很難用到實際的交易,但我覺得用來決定配置的資訊還是有些顯著性的,這就好像是玩大亂鬥之中有一些場地的亂入攻擊你必須要避開,這會來決定你整體策略為何。
手法方面,自己對於每種方法適用的情境,還有自己對於不同產業的估值模型也比較純熟,甚至對於 position sizing 從原本的無所是從,也漸漸有自己的因情境改變的手法。
例如這陣子很流行的瘋狗流,雖然我目前還沒看到有嚴謹的定義,就我的理解,比較像是利用基本面或籌碼面或其他經濟的另類指標,抓到起漲點然後去衝浪,並且加大資金 turn-over 來有效幫助資金成長。這看似不是價值投資但其實我覺得也是非常吃操盤人的經驗跟基本面分析主觀判斷的,但差別點在於他更多的是看待投資為期望值打法,承認自己有些許資訊優勢,但在整個波段可能不是資訊最強的,所以會外包很多判斷給籌碼跟資金流向。然後用停損來控制期望值是正的。對於操盤人本身的心理素質要求也是蠻高的。我個人認為適用的主場是像是台股這樣沒有個人資本利得稅,而且半導體,電子股還有傳產是或多或少算是週期較短的地方,畢竟週期股波峰跟底可能會相差到十倍。在美股的話,如果交易人是美國資本利得稅務身分,而美股市場又是期權市場比較發達的地方,改用 Options 的策略來做區間或是波段會是更適合的作法,但風險不對稱還有下檔保護風險的打法我覺得精神上都是類似的,就是建造一個期望值為正的系統,並且讓你心理可以承受的住。
由於知道瘋狗流的作法,對於一般人理解傳統價值投資的一些盲點也有了更深的體會。我覺得傳統價值投資麻煩的一點就是你不知道會不會是價值陷阱,而多數的書裡面對於 position sizing 以及下檔保護等等的著墨並不多,多數的價值投資人都是說並不會停損,好一點的會說會依照新的資訊如果對於原本進場的 thesis 造成實質的改變就會賣掉。而實際去檢視其實說這些話的人多半都是股東會有實際話語權甚至是決策權的,因為實質的權力可以保護下檔。就算沒有控制權,他們可能也是在挑對手比較弱的主場,譬如說是 micro-cap space,對手沒有其他法人的話就可以優先接觸到管理層,因而有資訊優勢,當然壞處就是 micro-cap 的流動性比較不好,在系統性風險發生的時候不是很好逃跑。對於部位不夠大而價值投資做的好的人,我觀察到的幾乎其實都是在做 Value Trading,其實他們賭的並不見得是三年以上的維度,而是幾季甚至是一年為 timeline 的短暫 value displacement,因而要跑的判斷可能比較容易定義。如果是要完全不停損的話,另一種方式就是要等安全邊際夠大的時期左側交易,大概只能等那種十年一次的系統性風險,那就是變成十年一次壓身家。太過分散的話超額報酬又不高,畢竟超額報酬是博弈而來的。 但這又會牽扯到 position sizing 的問題,萬一你錯了怎麼辦?按照 Joel Greenblatt 的訪談時說法,他的 position sizing 原則是他不是看風險報酬比,而是他覺得會輸錢的絕對數值不大的時候他才會放大部位。如果一個 binary event 上檔是十倍但下檔是歸零的時候是不符合壓大的定義的,但這其實跟期望值打法是異曲同工之妙,只是是利用基本面的計算來控制下檔風險,畢竟下檔控制不外乎幾種方法。
- 跑得快,那就要要求流動性。利用停損來控制損失部位。
- 基本面來看沒什麼系統性風險,或是提升 security 的優先順位買 preferred stock 或 senior bond。
- 找博弈對手弱的主場,比別人早知道消息。
- 利用衍生性金融工具,賭不對稱,譬如波動率高的時候賣 put,在下跌趨勢中買 call
從書裡描寫的價值投資直接照搬一般個人情況,在艱難時期或是看錯的時候,常常就是賠大錢的時候。
零零總總打了一堆,算是紀錄一些想法的改變。