今天先出一道題目，感受一下AI入門試題的style：
下面這個被汙損的二維碼中，存儲的信息是：
有結題思路了麼？別著急，考試才剛剛開始。。
▌思路清奇的筆試題？
2018 年，創新工場AI工程院舉辦的 DeeCamp 人工智慧訓練營打算培養 300 名大學生。這是 DeeCamp 的第二期。報名異常踴躍，全球近 7000 名學生申請。
6 月 8 日和 9 日兩天，報名的同學接受了在線筆試。筆試還沒結束就出現了各種熱鬧事兒。比如，有的同學想通過運行考題中的代碼來尋找答案，沒想到，簡單的幾行代碼很快耗盡了電腦資源，有的電腦竟直接崩潰！筆試結束，微信群裡熱鬧非常。同學們興致勃勃地討論筆試題目。有的題目，大家討論了幾小時還熱情不減。有同學連連感嘆，這題目真是思路清奇！
什麼樣的在線筆試題，才能讓電腦崩潰，才能給人留下思路清奇的印象呢？
為了讓幫助參試同學更好地做答，同時供對AI感興趣的同學學習， 創新工場AI工程院副院長王詠剛在本文寫下了DeeCamp 在線筆試的設計思路。
▌設計 AI 入門級開卷筆試題的挑戰
設計在線筆試題，本來就難。設計 DeeCamp 的在線筆試題，尤其有挑戰。
在線筆試本身就是半開卷的性質。想要所有同學都嚴格遵守閉卷規定，極難。好多公司為了防止所謂在線筆試「作弊」，嘗試過各種好玩的招數，比如要求開著攝像頭答題，其實大多是掩耳盜鈴。真正好的在線筆試題，應該是即便開卷，答題者也需要動腦筋思考的題目。
記得以前 Google 使用的在線筆試題，大多是偏重算法的題目，可以看做是簡化版的 ACM。這的確是一種設計開卷筆試題的思路，因為很多經典算法問題，都可以被包裝到一個很具體的場景中。學生考試時，即便用搜尋引擎去查找這個具體場景，只要以前沒考過類似的題目，就很難搜到正確答案。最起碼，學生需要有一定的算法知識，能夠將遇到的問題抽象成特定的算法模式，然後再去搜索對應的解決方案。
但是，回到 DeeCamp，如果按照簡化版 ACM 的思路，就不能滿足要求了。因為 DeeCamp 希望招聘的學生標準與 Google 要招聘的學生標準有很大不同。Google 是一家公司，想招進來的是最聰明的、編程能力和算法能力最強的學生。DeeCamp 是一個訓練營，本來就是以培訓為目的，當然不能把入門考試的要求設得太高。
DeeCamp 想招進來的是這樣的學生：聰明、知識面廣、動手能力強、有不錯的數學和編程基礎，了解機器學習特別是深度學習的基本概念。因為 DeeCamp 強調AI人才培養，入門考試當然不會要求每個學生都能熟練掌握 CNN、RNN 之類的網絡細節，或者特別擅長解決算法難題。
也就是說，我們創新工場 AI 工程院這個命題小組，要設計的是一套 AI 入門級的開卷筆試題，無論是數學、編程、算法還是 AI，都只適合考察最基本的知識技能，而不適合強調題目的專深。同時，這套題還需要在題目的趣味性、靈活度等方面下功夫，最好有一些平常很少見到的新場景，以考察同學們在解決新問題時的實戰技能。更重要的，這些題目需要在學生開卷答題的情況下，還能有足夠的區分度。
各種要求的疊加下，並沒有完美的解決方案。既不能完美防作弊，也沒法在難度、知識點、趣味性等方面達到完美均衡。我們這個命題小組只是盡力而為。
https://challenger.ai
▌如何考察基本概念？
考察基本概念的題目都是送分題，但送分也不能太直接、太坦白。也就是說，對那些沒學好基本概念的同學，開卷考試時，好歹也要讓他們在搜尋引擎裡費些周折，不能太直接查到答案。比如下面這道原題：
下面有關計算機基本原理的說法中，正確的一項是：
(A) 堆棧（stack）在內存中總是由高地址向低地址方向增長的。(B) 發生函數調用時，函數的參數總是通過壓入堆棧（stack）的方式來傳遞的。(C) 在 64 位計算機上，Python3 代碼中的 int 類型可以表示的最大數值是 2^64-1。(D) 在任何計算機上，Python3 代碼中的 float 類型都沒有辦法直接表示 [0,1] 區間內的所有實數。
每個選項，都涉及計算機基本原理或程式語言的某種基本知識。如果沒學好計算機原理，或沒掌握程序設計的一些本質問題，即便開卷，大概也很難搞清楚該如何用搜尋引擎快速查找答案吧。
另外，既然是開卷，選項（C）和選項（D）就沒有迴避 Python3 這樣的具體程式語言的具體版本。因為即便不懂 Python 編程，也至少能搜索到，Python3 裡面的整數類型取值範圍是什麼。或者，對於選項（D），只要從程式語言的本質出發，明白計算機裡的浮點類型只是一種用離散方式近似表達實數區間的方法，就可以知道，Python 裡的 float 是不可能涵蓋 [0,1] 區間內的所有實數的。
類似的，有關深度學習基本概念和基本框架的選擇題是這個樣子的：
有關深度神經網絡的訓練（Training）和推斷（Inference），以下說法中不正確的是：(A) 將數據分組部署在不同 GPU 上進行訓練能提高深度神經網絡的訓練速度。(B) TensorFlow 使用 GPU 訓練好的模型，在執行推斷任務時，也必須在 GPU 上運行。(C) 將模型中的浮點數精度降低，例如使用 float16 代替 float32，可以壓縮訓練好的模型的大小。(D) GPU 所配置的顯存的大小，對於在該 GPU 上訓練的深度神經網絡的複雜度、訓練數據的批次規模等，都是一個無法忽視的影響因素。
總結起來，這次筆試裡的基本概念題，大概涵蓋了以下幾個方面的基本知識：
1、基本數學知識，比如函數和矩陣運算。
2、計算機原理和編程基礎知識，比如堆棧、數據類型。
3、機器學習的基礎知識，比如 Precision 和 Recall。
4、深度學習的基礎知識，比如表示學習的概念。
5、TensorFlow 的基本概念，比如 Variable 和 placeholder 的區別。
補充一下，有同學問到，概念題裡，有一個有關 TensorFlow 的題目，提到了 TensorFlow 的符號執行（Symbolic Execution）和計算圖優化（Computational Graph Optimization），相關的參考資料到底在那裡？
其實，TensorFlow 白皮書裡，「5.1 Common Subexpression Elimination」就是關於計算圖優化的一個舉例說明。有關符號執行對於計算圖優化的作用，MXnet 文檔裡有一篇特別淺顯的講解：Programming Models for Deep Learning。其中對流行的框架做了一個歸類：「Examples of imperative style deep learning libraries include Torch, Chainer and Minerva. While the examples of symbolic style deep learning libraries include Theano, CGT and Tensorflow.」
▌如何考察 AI 相關的數學知識？
比如，卷積是深度學習常用的數學知識，一些熟悉 CNN 的同學可能沒有仔細想過卷積的數學含義到底是什麼？卷積在 CNN 中常以二維數學形式出現，那麼，卷積的N維表達式是什麼？一維卷積又是如何計算的？CNN 中的卷積，和語音信號處理中的卷積，數字圖像處理中的卷積，是如何聯繫在一起的？
知乎有一個很好的問題，「如何通俗易懂地解釋卷積？」這個問題下面，有好幾個特別有趣的答案，大家可以參考。
www.zhihu.com/question/22298352
當然，實際筆試題裡，關於卷積的問題特別簡單：
一維離散卷積的定義是 給定一維數組 a = [1, 2, 3], v = [4, 5, 6]，它們的離散卷積結果是？
熟悉卷積計算的同學，可以很快寫出答案。因為是開卷，就算搞不清這麼簡單的公式，如果能想起來手頭有很多現成的工具可用，比如用 numpy 的卷積計算函數實際算一下
numpy.convolve(a, v)
這種願意學習、勤於動手的學生也很不錯！
類似的，真題中，還有一些結合機器學習或深度學習的場景，但其實只是做一個數學運算的題目，比如這一題：
給定詞典 [a, b, c, d, e]，基於這個五單詞詞典的三個文檔（document）內容如下：
DocA: [a, b, b, d, d]DocB: [b, b, b, e, e, e, d]DocC: [d, d, b, b, e]
如果使用 bag-of-words model 將每個文檔表示成五維的向量，例如，DocA 可以被表示為 {a:1, b:2, c:0, d:2, e:0}。基於這三個五維向量，計算兩兩之間的餘弦相似性（Cosine similarity），最相似的兩個向量是？
這個題目，對很多沒有太多自然語言處理（NLP）經驗的同學來說，最難的主要是理解題目中bag-of-words model、Cosine similarity 之類的基本概念。但因為是開卷，學習能力強的同學應該能快速查到這些概念的基本定義，然後根據 Cosine similarity 的公式，寫幾行代碼，算出結果。善於偷懶的同學，其實也不難查到，像 sklearn.metrics.pairwise 包中的 cosine_similarity 函數，其實都是可以直接拿過來用的。
▌到底是什麼題讓電腦崩潰？
一般開卷在線筆試，是很難設計那種根據代碼寫出運行結果的題目的，因為參加考試的同學只要在電腦上運行一遍程序，就知道結果了。
我們命題組偏偏不信邪，設計出了幾道編程和數學結合的題目，不僅給出代碼，還無法通過直接執行得到答案。
比如說，其中一道題是這樣的：
假設可以不考慮計算機運行資源（如內存）的限制，以下 python3 代碼的預期運行結果是：
importmathdefsieve(size):sieve=[True]*sizesieve[0]=Falsesieve[1]=Falseforiinrange(2,int(math.sqrt(size))+1):k=i*2whilek<size:sieve[k]=Falsek+=ireturnsum(1forxinsieveifx)print(sieve(10000000000))在正常配置的計算機裡，這個題目裡的代碼是很難跑出結果的。這也是為什麼題目描述裡會強調「假設可以不考慮計算機運行資源（如內存）的限制」的原因。不相信這一點的同學當然會去嘗試運行這段代碼，但結果麼，多半是內存異常，或者持續運行無響應。最糟糕的，電腦甚至會直接崩潰。實際考試時，同學報告了好幾個崩潰案例；我猜，主要是在 Windows 系統中吧（笑臉）。
所以，遇到這種題是不能硬來的。做題的學生還是要回過頭來，讀代碼，理解代碼的含義。
這個代碼的函數名sieve其實暗示了代碼的功用，Sieve of Eratosthenes，這是用篩法計算質數個數的一個經典方法。當然，不知道篩法這個詞也不重要，重要的是要從代碼邏輯裡，讀懂最關鍵的幾行其實是在把所有非質數都篩掉。就算讀起來費勁，那麼，至少能想到，把最後一行改成比較小的輸入數字，比如 10，比如 100，比如 1000，運行一下試試吧。
這段代碼的功能很明顯：求 10,000,000,000 以內質數的個數。至於 10,000,000,000 以內質數的個數到底有多少，這個容易，搜索一下不就知道了？當然了，數學不好，或者不善於信息檢索的同學，這個搜索估計也要費不少時間。
這種根據代碼寫運行結果，又可以開卷考試的命題思路，其實還有不少。比如實際考題裡的另一個例子，是在用類似蒙特卡洛方法的思路，讓計算機不斷生成隨機數，然後去暴力統計隨機坐標落在平面上不同圖形區域的計數比例，以逼近圖形區域的面積或面積佔比。真題如下：
下面的 python3 函數，如果輸入的參數 n 非常大，函數的返回值會趨近於以下哪一個值（選項中的值用 Python 表達式來表示）？
importrandomdeffoo(n):random.seed()c1=0c2=0foriinrange(n):x=random.random()y=random.random()r1=x*x+y*yr2=(1-x)*(1-x)+(1-y)*(1-y)ifr1<=1andr2<=1:c1+=1else:c2+=1returnc1/c2(A) 4 / 3(B) (math.pi - 2) / (4 - math.pi)(C) math.e ** (6 / 21)(D) math.tan(53 / 180 * math.pi)
這個題目，要計算面積比值的圖形區域極其簡單，只要搞懂了代碼的基本思路，就不難把這個問題轉化成一個毫無壓力的初中幾何題了。
▌算法題都不算難
這套卷子中，算法題的難度不大，但形式上會追求新穎，以便考察學生應對新問題的能力。比如下面這樣的題目：
有一個畫圖用的函數庫，提供三個 API 接口：
set_color(color) #設置畫筆顏色。初始畫筆顏色為黑色。move_to(x, y) # 移動畫筆到給定的坐標。初始坐標為(0,0)。line_to(x, y) # 在畫筆的當前位置到給定的終點坐標之間畫一條線段。已知每調用 set_color 函數一次，要支付 3 元；每調用 move_to 函數一次，要支付 2 元；調用 line_to 函數免費。請問，要從初始狀態開始，用這個函數庫畫出下圖，最少支付多少錢就可以完成？（圖中，左側紅綠藍三條線段相互連接，右側紅綠藍三條線段相互分離）
這個問題當然可以抽象成一個變形的最短路徑問題，但顯然沒有那麼複雜。思路縝密、清晰的同學在頭腦中設計一條最佳路徑，其實也不算困難。如果只在腦子裡，或者只用紙筆想不清楚，那麼，選擇直接編程解決的方案也很容易。因為搜索空間不大，編程可以輕易窮舉六條線段全排列的所有可能性，從裡面找到最小的 cost 即可。
▌有趣的圖靈獎得主問題
實際筆試中，一道大題是這麼設計的（篇幅原因，下面題目中的字符串不完整，不能用於實際解題，只是一個示意）：
有一張圖靈獎得主的肖像照片，被一個學生用簡單的異或加密方法，編碼成了如下這樣的字符串：
MG4rZiJpImkvaixpLGwrbjRxN3MxdzN3M3s……（篇幅原因，此處省略若干字符）
已知肖像照片是 64x64 像素的 0~255 級灰度圖片，內存中用 raw bitmap 方式，每個像素用一個字節存儲。對肖像照片的原始數據，學生使用的加密代碼片段如下（Python3 代碼，代碼中的 key 值是未知的加密密鑰）：
_KEY_LEN = 2bitmap = PIL.Image.open(image_path).tobytes()encrypted = []for index, byte in enumerate(bitmap): encrypted.append(byte ^ key[index % _KEY_LEN])return base64.standard_b64encode(bytes(encrypted))
請問：這張被加密的照片，是以下哪位圖靈獎得主的肖像？(A) Marvin Minsky(B) John L. Hennessy(C) Donald E. Knuth(D) Raj Reddy(E) John McCarthy(F) Edsger W. Dijkstra(G) John Hopcroft(H) Alan Kay
這題目很有趣，但不難。需要的只是學生比較靈活的頭腦，和比較多的動手經驗。機靈的人可能只寫幾行代碼，就可以猜到結果。
首先，異或加密是一種幼兒園級別的加密形式，即便不知道秘鑰，也不存在太多破解難度。學過密碼學的同學，肯定特別清楚這一點。但沒學過密碼學的同學，在這裡也沒有太多劣勢。只要不是被問題本身嚇到，只要敢於或勤於動手做實驗，總能很容易找到線索。
這題目完全不需要對異或加密的規律有任何深刻的認識。2 個字節長的秘鑰，一共有 65536 種組合。其實，根本不需要嘗試那麼多。只要先猜著用一兩千種候選秘鑰來解碼圖片，同學們就不難發現，很多解碼後的圖像已經處於「半可讀」狀態了。
「半可讀」的圖像可以送進 Google 圖片搜索或類似工具裡找答案，也可以和選項列出的八位圖靈獎得主的維基百科照片進行人工比對。
也就是說，題目本身並沒有真正要求去破解秘鑰，而是著重考察學生在遇到這樣的全新問題時的邏輯思維能力，靈活利用手頭各種工具的能力，以及勇於嘗試的能力。
假如真的要破解秘鑰（對異或加密來說，更準確的說法是，找到包含原始秘鑰在內的一組近似秘鑰），恢復出原始圖片，其實也不是很難。一種可行的思路是寫一個基於信號特徵的分類器，將那些經過異或操作擾動的噪音圖像和原始圖像區分開。因為秘鑰長度是 2 字節，用錯秘鑰時，解碼後的圖像裡大多都有明顯的縱向條紋，這顯然是分類器可以借用的一個強特徵。
從出題角度看，這個題的另一種變化形式是拋棄幼兒園級別的異或加密，而改用專業的對稱加密算法來加密原始圖像。當然，這時是需要限定候選秘鑰的數量級的。這個情況下，錯誤的候選秘鑰得到的輸出，生成「半可讀」圖像的機率就大大減小了。當我們只能用暴力窮舉的方法來找到包含清晰人臉的圖像時，有的同學就會想到一個更有趣的解法：找一個人臉識別的API來，利用人臉識別功能，看哪個候選秘鑰解碼出來的圖像裡包含一張可識別的人臉。
▌莫爾斯電碼問題
莫爾斯電碼（Morse Code）因為是個經典的算法問題，本來不想過多介紹，但不斷有同學問到，就多說幾句吧。
原題是這樣的：
一個粗心的發報員在發送莫爾斯電碼（Morse Code）的時候，忘記在發送字母和單詞之間停頓，結果收報系統收到的是下面這樣的一個沒有分隔符的點（.）劃（-）的序列（請忽略換行符）。
.-.-....-.-...--.-...-....--...-.-...-.--.------..-...-..-.-.---...-..-..---..-......--..-.--.-...-.--......-.........-..-.----.-.....-....--.-.-.--.-..---..-......-...-..-.--.-.----......-.--.-----..-------.-.-..---.-.-.--..-.-...............--...--....--..-....-.-----.....-...-------.-......-.........-..-..--.-....-...--....-.--.-.....--..-.....--..-.---.--...-.-.-..-.-.....---.-.-.-.----....-..-.....--..----......-...-.--.-...--.....--.....-.......-....---..-..--...-------.--....---..---.....-.-.-....-.-...--..-....---..--.--...-.-.-..-.-.....---.-.-.-.----....-..-.....--..----.
已知這份報文的原始內容是一部著名英文小說的片段，請問，這部小說的作者是：(A) H. G. Wells(B) J. K. Rowling(C) Isaac Asimov(D) Lewis Carroll(E) Jack London(F) Stephen King(G) J. R. R. Tolkien(H) Edgar Rice Burroughs
Google 搜索 「morse code without spaces」，有非常多不同方式的講解，比如比較經典的，用動態規劃思路的解法。而且，網上還可以找到實際可以用來解碼的原始碼。考試時如果會搜索，幾乎是不用自己編程序的。
當然，如果不想這麼麻煩的話，還可以試著用手工窮舉方式，解碼前面 4~5 個英文字符，這個複雜度是可以接受的，因為原文的第一個字母是 「A」，所以，前面 4~5 個字符最早出現的一組候選項裡，很快就可以見到 「Alice」 這樣醒目的單詞——然後，如果同學們有好的閱讀習慣，直接就可以猜到那本小說是——《愛麗絲漫遊奇境》。
▌小結
DeeCamp 的筆試題其實都不太難。設計這些題目時，有趣、有區分度、覆蓋的知識面廣、能考察學生的靈活度和解決新問題的能力，這些都是我們最重要的考慮因素。
所有題目中，最有趣、筆試後被議論最多的，可能是這個有關二維碼的問題：
下面這個被汙損的二維碼中，存儲的信息是：
這個題目，其實主要是看學生在新問題面前，有沒有一個比較符合邏輯的思考過程：
為什麼二維碼在汙損之後，很多時候還是能被識別出來？
題目裡給出的二維碼，為什麼微信的掃碼器識別不出來？
既然是開卷，學生完全可以去搜索二維碼的冗餘設計。然後，學生基本會知道，其實二維碼中間的小黑點部分，擁有大量的冗餘，一般程度的變形和汙損是不影響識別的，最影響識別的是三個大方框，因為它們起定位作用。了解了這樣的知識，學生只要打開畫板，把缺失最厲害的那個大方框補齊整，就可以微信掃碼看結果了。
正如 DeeCamp 訓練營本身一貫強調有趣、有用、貼近實戰一樣，DeeCamp 的在線筆試題在命題時，追求的也是這樣一種思路（當然，命題組水平有限，差錯或考慮不周的地方在所難免，還請大家多提批評意見）。
祝 DeeCamp 學員開心、進步！