Metallurgy in Computer Science

資訊冶金,不僅僅是技術上的紀錄,還有一些生活經驗啥的

0%

研究所實驗室的同屆同學不少有打算去金融業工作,一個家境比較殷實的同學上二年級之後就主要在修金融那方面的課了,而我室友更是打算之後去投資銀行工作,於是我的室友就推薦我去看投資銀行學的網課,以下是我整理看到一半的筆記,以及一些延伸出來的問題

需要注意的一點是,因為 課程 本身是復旦教授開的,因此授課內容偏向中國 2015 時期的,不僅部份制度跟其他地方有出入,一些金融體制在這幾年也有著相當大的變化(像是由審核制轉往註冊制);因此我同時也想釐清跟更新這堂課講述的內容

最後是儘管題目是投資銀行,但是由於我本身完全沒有這方面的基礎(最多也就是聽到同學聊天用到的名詞,並沒有系統性的了解)

Read more »

夏農熵

要講到訊息論就不能不提到開創這個領域的「夏農熵」了

夏農熵用了一個很神奇的方式定義「資訊量」的多寡,

TODO: brief about shannon entropy

這個公式乍看之下可能不是那麼直觀,首先 p(1-p) 是為了把概率的不均衡性考慮進去,也就是說當 p=0.5 時,熵會是最大的(這也非常合理,因為一半一半的發生率是最混亂的,我們完全無法預測)

但是那個取對數是為了什麼?而且還是用底數為二的對數,不是用自然對數為定義,這是因為我們已經考慮到這是一個「二進制的應用」,也就是「最有效表示該訊息的比特數」

但是為什麼我們可以透過上述的數學式得到這樣的物理意義?我們可以透過 Asymptotic Equipartition Property (AEP)

AEP

關於這章,對於各位跟我一樣數學程度不是太好的朋友,不建議去看理論說明,包含 Elements of Information Theory 還是其他大學課程的教材,會看到一堆數學證明但是沒有著重在工程上的解釋

感謝 Asymptotic Equipartition Property (AEP) 的熱情解釋

這代表什麼呢,一旦你確定輸入字元們的分佈機率後,這樣「符合對應機率的隨機輸入們」都會落在 typical region 裡;透過從原本廣大的可行範圍,利用我們事先得知的「概率分佈」,我們可以將可行解數量向下縮減,在無損壓縮的前提下最多能夠壓縮到「 typical region 內所有可行解的數目」,這個數目又正好對應到「夏農熵能夠表達的數值範圍」

你可能會想,如果今天輸入不落在 typical region 裡,像是「all tail 的情況」,那麼就不能只用熵的比特數來表示了;不過事實是,因為「all tail」 這個事件本身就不符合我們原先假設的概率範圍內,因此不能表示是很正常的;因此 依據輸入分佈決定編碼 是一件非常重要的事

工程應用

以我自己之前做的研究為例,我嘗試在一個「只支援有限指令操作的機器」上壓縮路由訊息,這邊的路由是類似 Source routing 的變動長度編碼(實際上狀況更為複雜一點,是一個 multicast 的 source routing,所以每一跳可能會有變動大小的 nexthop)

我們要怎麼把這個冗長且變動長度的路由訊息壓縮到(希望可以)定長,這同時也是要實做在該機器上的要求(因為底層不支援遞迴解析)

非常尷尬的是,編碼大多需要

Reference

  1. Stanford EE 376A: Information Theory
  2. CMU
  3. 訊息論基礎
  4. A mathematical theory of communication

Gurobi 是一個數學規劃工具,用於解線性規劃 (Linear Programming) 或是二次規劃(Quadratic Programming)

使用者首先需要將應用場景以數學描述抽象化(成一次方程式或最多二次方程式),隨後 Gurobi 會根據給定的目標以及條件找出最符合需求的解(如果解存在的話)

值得注意的是,電腦科學中不少優化方法都是 non-deterministic 的,以機器學習來說就是 local minimum 與 global minimum 的差異,但是線性規劃是一種確定性的最佳解(再重申一次,前提是要有解)

儘管線性規劃乍看之下非常相似國中小學習解方程式組的過程,但是就跟論文研究一樣,從廣到深能夠探討研究的東西還真的不少,並且也需要考慮到「理論與實做的差距」這個老問題

以下我會從線性規劃(儘管 Gurobi 能夠支援二次規劃,但是本文不打算討論到那個部份)的背景簡單帶入,

Read more »

今天跑去清華台生組的聖誕活動,遇到一個美術學院的博士生,由於他本身已經從事這個行業(辦展覽、賣畫等等)一定時間了,我意外的從他身上更新了我對「當代藝術」的看法,更精確的應該說是「深入思考這個行業的運作邏輯」

以下部份主要會講到當代藝術品的「用途」,正如大家所理解的,當代藝術品早就不是藝術為主體的存在,更多是一種投資標的,一種商品

Read more »

最近在 LWN 看到 Theoretical vs. practical cryptography in the kernel 這篇關於 Linux 中隨機數生成機制的討論,原本是想說簡單寫個翻譯,但沒想到為了 trace 原文 patch 改動而跑去看原始碼,發現看不懂之後看到註解裡面提到這個很神奇的論文The Linux Pseudorandom Number Generator Revisited,這是一篇兼具實做但是理論分析相當充實(充實到我都看不懂的那種)的「技術文件」(個人覺得,作為菜鳥看這個比直接去 trace code 學到的東西多一點)

因此以下會從 LWN 那篇文章作為切入點,希望能夠看懂 LWN 那篇文章是在 討論什麼,並且簡單討論一下 Linux 隨機數生成的機制(具體機制有效性證明的部份,儘管論文裡有不少都是在討論這個方向,然而由於個人才疏學淺目前還不會 cover 到那塊)

Read more »

最近兩天跟著同學去聽清華經管跟五道口金融學院的課,想說趁記憶還在的時候紀錄一下

先聲明我是完全的經濟/金融/投資菜鳥,literally 完全沒有碰過,我會覺得這個很好玩還是要感謝當初去香港城市大學交換的時候跟助教 / 當地學生的交流

以下我應該會總結一下我這兩天的認知,非常零散的寫點觀察與心得

Read more »

最近在 trace Matrix 的原始碼,它(目前比較完整的是 Synapse)的底層用到了 python 的事件驅動框架 – Twisted,雖然說不懂底層大概還是可以模糊的理解整體流程,但是這樣對整個非同步的事件處理流程理解上可以說是完全沒有辦法,舉例來說:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
# We process PDUs and EDUs in parallel. This is important as we don't
# want to block things like to device messages from reaching clients
# behind the potentially expensive handling of PDUs.
pdu_results, _ = await make_deferred_yieldable(
defer.gatherResults(
[
run_in_background(
self._handle_pdus_in_txn, origin, transaction, request_time
),
run_in_background(self._handle_edus_in_txn, origin, transaction),
],
consumeErrors=True,
).addErrback(unwrapFirstError)
)

因此在這一篇文章我主要會著重在理解 python twisted 非同步函式呼叫的模型,還有討論一下 python async/await 這個語法糖

Read more »

最近在靠北工程師上面看到這張梗圖,其實我也沒寫過 PHP,不知道那邊狀況怎樣,但是其實浮點數運算這個議題挺廣泛的,也並不侷限於只有 PHP 有這個「問題」,正好之前在 Jserv 老師課堂上有稍微研究一下這個議題也寫了些筆記(我們自己寫的是浮點數運算和定點數操作,老師的講義是你所不知道的 C 語言: 浮點數運算),現在重新整理一下筆記,並且看能不能順便更新一點內容

Read more »

The Josephus Problem 似乎是一個相當有名的問題,我則是在 Concrete Math 這本書上第一次看到,本來針對這麼一個被廣泛討論的問題寫文章好像有點沒意思,但是我邊看感覺問題挺有趣的

以下我應該不會著重在怎麼實做,因為說白了它可以很好的簡化成 Rotate-shift,我應該會著重在 Concrete Math 上的觀點跟我的思考

Read more »