Linear Function
Linear Function
「線性函數」。加權總和函數。
f(x₁, x₂, ..., xₙ) = w₁ x₁ + w₂ x₂ + ... + wₙ xₙ
線性函數是計算機科學經常使用的函數,熱門程度遠勝二元樹。現實世界相當複雜,經常出現難以計算的事物,此時工程師就會將事情簡化為線性函數。線性函數擁有強悍的數學性質和演算法,儘管艱深晦澀,但是質樸實用。
詳情請見本站文件「Linear Function」。
Stochastic Function
Stochastic Function
「隨機函數」。輸入是浮動數字。輸出顯然也是浮動數字。
f(X, Y, Z) = a X + Y Z where X, Y, Z are random variable
古代數學家沒有仔細區分「浮動:有規矩」和「隨機:無規矩」的差別,把兩者都命名為隨機,混淆視聽。大家搞不清楚狀況的情況下,Stochastic Function跟Random Function被當作相同。
Random Function
Random Function
「隨機函數」。輸入輸出隨機對應的函數。
隨機函數的輸入輸出,可以是連續數字、也可以是離散數字。
電腦做運算,數值皆離散。我們只能處理離散數字。
初次建立隨機函數,對應方式是隨機的;每次使用隨機函數,對應方式是固定的。
如果對應方式每次都是隨機的,那麼其實就是隨機數了。
Hash Function
Hash Function
「雜湊函數」。限制輸出範圍的函數。
雜湊函數有著形形色色的變種:限寬、均勻、保距、量化、混亂、單向、編碼。大家視情況需要,混用多個變種。
hash是一種菜式:肉、馬鈴薯、蔬菜,剁碎攪拌成為餡泥,然後烤炸。hash具有諸多意涵:均勻隨機、範圍壓縮、型態變化。
1. hash function
限寬。限制輸出範圍。簡易方式是mod運算。
用途是縮減數字範圍。
2. uniform hash function
均勻。輸出數字使用機率均等。簡易方式是mod最大公因數。
用途是均勻分散儲存。知名應用是hash table。
3. isometric mapping / locality-sensitive hashing
保距。所有數對,變換前的差異,大致等於變換後的差異。簡易方式是線性變換。
同樣道理,還可以發明保長、保角、保秩、保序等變種。
用途是以雜湊值估計相似度。
4. quantization / projection
量化。刪除數字的細節,降低精確度。簡易方式是floor運算。
用途是簡化數字。知名演算法是PCA、KNN。
5. random hash function
混亂。輸出是固定的隨機數。簡易方式是以輸入數字生成隨機數、隨機排列。
6. one-way hash function
單向。難以從輸出推算輸入。簡易方式是餘數連乘、三角函數。
用途是密碼、摘要、簽章,讓外人難以偽造變換前的原始資料。知名演算法如SHA-2、MD5。
請見本站文件「Encryption」。
7. coding / indexing
編碼。輸入不是數字,而是其他元件,例如字串。簡易方式是先化作多項式、再化作數字。
用途是建立索引表,知名演算法如murmur、xxHash。
請見本站文件「String」。