二分法

二分法的思路是每次排除一半樣本的試錯方法拱烁，把樣本一分為二（A和B），那么目標(biāo)值不在A就在B里噩翠，不斷縮小范圍戏自。

就像在玩一個猜價格的游戲，通過告訴你猜高了還是低了伤锚，你總能猜到正確價格一樣擅笔，設(shè)計好一個計算差值的函數(shù)能大體上判斷出你下一輪嘗試的值應(yīng)該在前一半還是后一半，總能迭代到足夠接近的結(jié)果屯援。

對于求平方根來說剂娄，我們沒什么過多的設(shè)計，直接對中值取平方玄呛，高了就取小的一半阅懦，低了就取大的一半，實測小的數(shù)字是沒問題的徘铝，這里僅僅用來演示思路耳胎。

import math

def binary_sqrt(n):
    epsilon = 1e-10         # quit flag
    start = 0
    end = n
    mid = start + (end - start) / 2
    diff = mid ** 2 - n
    while abs(diff) >= epsilon:
        # 值過大則嘗試小的一半，否則就嘗試大的一半惕它，修改邊界值即可
        if diff > 0:
            end = mid
        else:
            start = mid
        mid = start + (end - start) / 2
        diff = mid ** 2 - n
    return mid

for i in range(1,11):
    print(f'estimated:\t{binary_sqrt(i)}, \t sqrt({i}): \t {math.sqrt(i)}')

output:

estimated:  0.9999999999708962,      sqrt(1):    1.0
estimated:  1.4142135623842478,      sqrt(2):    1.4142135623730951
estimated:  1.7320508075645193,      sqrt(3):    1.7320508075688772
estimated:  2.0000000000000000,      sqrt(4):    2.0
estimated:  2.2360679775010794,      sqrt(5):    2.23606797749979
estimated:  2.4494897427794060,      sqrt(6):    2.449489742783178
estimated:  2.6457513110653963,      sqrt(7):    2.6457513110645907
estimated:  2.8284271247393917,      sqrt(8):    2.8284271247461903
estimated:  2.9999999999890860,      sqrt(9):    3.0
estimated:  3.1622776601579970,      sqrt(10):   3.1622776601683795

牛頓法

我就算不畫圖也能把這事說清楚怕午。

牛頓法用的是斜率的思想，對淹魄，選一個足夠接近目標(biāo)值()的點()郁惜，計算其切線與X軸的交點(），這個交點往往比更接近甲锡，數(shù)次迭代后肯定越來越接近目標(biāo)值兆蕉。

1. 問題轉(zhuǎn)化成一個求函數(shù)上任一點()的切線與X軸的交點()的問題(我們假設(shè)n+1在n的左邊羽戒，即向左來逼近)
2. 令，則
3. 展開:
4. 
5. 至此虎韵，我們用推出了一個離更近的點：
6. 如此往復(fù)則可以推出足夠精度的解易稠。

而求任意正整數(shù)的平方根，

1. 函數(shù)就變成了 包蓝，
2. 那么我們有:
3. 
4. 都有了驶社，就能代入上面得到的公式：了
5. 得到

現(xiàn)在可以寫代碼了，不斷去迭代测萎，求下一個:

def newton_sqrt(n):
    x_n = n / 2
    epsilon = 1e-10             # quit flag
    
    f_x = lambda a : a**2 - n   # f(x)=x^2 - a
    df_x = lambda a : 2*a       # derivative of f(x)
    x_next = lambda a : a - f_x(a) / df_x(a)
    
    while abs(x_n ** 2 - n) > epsilon:
        x_n = x_next(x_n)
    return x_n

for i in range(1, 10):
    print(f'sqrt({i})\t{newton_sqrt(i)}')

output

sqrt(1) 1.000000000000001
sqrt(2) 1.4142135623746899
sqrt(3) 1.7320508075688772
sqrt(4) 2.0
sqrt(5) 2.23606797749979
sqrt(6) 2.4494897427831788
sqrt(7) 2.6457513110646933
sqrt(8) 2.8284271247493797
sqrt(9) 3.0

梯度下降法

梯度下降法的數(shù)學(xué)原理是)的gradient（）就是其最陡爬升方向（steepest ascent）亡电。

可以拿這個當(dāng)成結(jié)論，也可以去感性認(rèn)識硅瞧，而要去證明的話逊抡，網(wǎng)上有數(shù)不清的教程，在花書(《Deep Learning深度學(xué)習(xí)》)和可汗學(xué)院里零酪，都是用的directional derivate來解釋（證明）的冒嫡，即”自定義方向上的瞬時變化率“，也是我認(rèn)為在如果有多變量微積分的基礎(chǔ)下四苇，比較容易讓人接受且簡單直白的解釋：

image.png

• 
• 就是指的任意方向孝凌，如果是x, y等方向，那就是普通的偏導(dǎo)了月腋。
• 顯然上式當(dāng)時擁有最大值蟀架，即指向的是的方向，那就是梯度的方向了
• 所以梯度方向就是爬升最陡峭的方向

在一元方程里榆骚，”梯度“就是過某點的斜率（slope)片拍，或者說函數(shù)的導(dǎo)數(shù)（derivative）。

我們要到局部最小值妓肢，顯然就應(yīng)該向相向的方向走捌省。并且由于越接近目標(biāo)值（谷底），斜率越小碉钠，所以即使我們選擇一個固定的步長（learning rate）纲缓，也是會有一個越來越小的步進(jìn)值去逼近極值，而無需刻意去調(diào)整步長喊废。

以上是思路祝高，只是要注意它上去的，而是精心設(shè)計的loss污筷，或者說diff工闺、error函數(shù)。

其實它跟前面的二分法很類似，就是不斷指導(dǎo)里應(yīng)該在哪個區(qū)間里去嘗試下一個x值陆蟆，再來結(jié)果與真值的差異（而牛頓法則是直接朝著直值去逼近雷厂，并不是在“嘗試“）。

二分法里我隨便設(shè)計了一個判斷l(xiāng)oss的函數(shù)（即中值的平方減真值）遍搞，而梯度下降里不能那么隨便了罗侯，它需要是一個連續(xù)的函數(shù)（即可微分）器腋，還要至少擁有局部極小值：

我們令表示不同的x取值下與目標(biāo)值的差的平方（損失函數(shù)loss）溪猿，既然是一個簡單二次函數(shù)，就能求極值纫塌，且它的最小值意味著當(dāng)x值為該值時估算原函數(shù)的誤差最小诊县，有：

(1/2的作用僅僅是為了取導(dǎo)數(shù)時消除常數(shù)項，簡化計算)

這時可以寫代碼了

def gradient_sqrt(n):
    x       = n / 2       # first try
    lr      = 0.01        # learning rate
    epsilon = 1e-10       # quit flag
    
    f_x     = lambda a : a**2
    df_dx   = lambda a : 2*a
    delta_y = lambda a : f_x(a) -n
    e_x     = lambda a : delta_y(a)**2 * 0.5     # funcon of loss
    de_dx   = lambda a : delta_y(a) * df_dx(a)   # derivative of loss
    delta_x = lambda a : de_dx(a) * lr
    
    count   = 0
    while abs(x**2 - n) > epsilon:
        count += 1
        x = x - delta_x(x)
    return x, count

for i in range(1, 10):
    print(f'sqrt({i}): {gradient_sqrt(i)}次')

output

sqrt(1): (0.9999999999519603, 593)次
sqrt(2): (1.4142135623377403, 285)次
sqrt(3): (1.7320508075423036, 181)次
sqrt(4): (2.0, 0)次
sqrt(5): (2.236067977522142, 103)次
sqrt(6): (2.449489742798969, 87)次
sqrt(7): (2.645751311082885, 73)次
sqrt(8): (2.828427124761154, 63)次
sqrt(9): (3.00000000001166, 55)次

Bonus

梯度下降解二次方程

• 求解方程：的根

def gradient_f(n):
    x1, x2  = 1, 1        # first try
    lr      = 0.01        # learning rate
    epsilon = 1e-4        # quit flag
    
    f_x     = lambda x1, x2 : (x1-3)**2 + (x2+4)**2
    dfx1    = lambda x : 2 * (x - 3)
    dfx2    = lambda x : 2 * (x + 4)
    delta_y = lambda x1, x2 : f_x(x1, x2) - n
    e_x     = lambda x1, x2 : delta_y(x1, x2)**2 * 0.5     # cost function
    dedx1   = lambda x1, x2 : delta_y(x1, x2) * dfx1(x1)   # partial derivative of loss \
    dedx2   = lambda x1, x2 : delta_y(x1, x2) * dfx2(x2)   # with Chain Rule
    delt_x1 = lambda x1, x2 : dedx1(x1, x2) * lr
    delt_x2 = lambda x1, x2 : dedx2(x1, x2) * lr
    
    count   = 0
    while abs(f_x(x1, x2) - n) > epsilon:
        count += 1
        x1 -= delt_x1(x1, x2)
        x2 -= delt_x2(x1, x2)
    return x1, x2, count

a, b, c = gradient_f(0)
print(f'''
a \t= {a}
b \t= 措左 
f(a, b) = {(a-3)**2 + (b+4)**2}
count \t= {c}''')

output

a   = 2.9967765158140387
b   = -3.9905337923806563 
f(a, b) = 9.999993698966316e-05
count   = 249990

之所以做兩個練習(xí)依痊， 就是因為第一個是故意把過程寫得非常詳細(xì)，如果直接套公式的話怎披，而不是把每一步推導(dǎo)都寫成代碼胸嘁，可以簡單很多（其實就是最后一步的結(jié)果）:

梯度下降解反三角函數(shù)

• 求解arcsin(x)，在和的值

即估算兩個x值凉逛，令和
這次不推導(dǎo)了性宏，套一次公式吧

import math

def arcsin(n):
    x       = 1           # first try
    lr      = 0.1        # learning rate
    epsilon = 1e-8        # quit flag
    
    f_x     = lambda x : math.sin(x)
    delta_y = lambda x : f_x(x) - n
    delta_x = lambda x : delta_y(x) * math.cos(x) * lr
    
    while abs(f_x(x) - n) > epsilon:
        x -= delta_x(x)
        
    return math.degrees(x)

print(f'''sin({arcsin(0.5)}) ≈ 0.5
sin({arcsin(math.sqrt(3)/2)}) ≈ sqrt(3)/2
''')

output

sin(30.000000638736502) ≈ 0.5
sin(59.999998857570986) ≈ sqrt(3)/2