📜 [專欄新文章] Unirep介紹: 使用ZKP的評價系統
✍️ Ya-Wen Jeng
📥 歡迎投稿: https://medium.com/taipei-ethereum-meetup #徵技術分享文 #使用心得 #教學文 #medium
Unirep是什麼? 怎麼用?
Photo by Raphael Lovaski on Unsplash
UniRep 是一個使用零知識證明(Zero-knowledge Proof)而達到具有隱私保障的評價 (reputation) 系統。使用者有權利享有多個暫時性的身份,但又同時能提出證明,讓其他人可以驗證評價是否符合自己宣稱的數量。此外,使用者也無法拒絕接收對自己不利的評價。
想像一個情境:如果Alice是Airbnb的使用者,Alice常常透過Airbnb租房,且Alice曾經獲得獲得許多Airbnb房東的好評;有一天Alice想透過Booking.com訂房,http://xn--alicebooking-kt4so6lvyab96x7trhi5b54x.com/,所以在Booking.com上沒有任何評價,萬一Booking.com的房東不想把房子租給來路不明的客人,那Alice要如何向Booking.com的房東證明她其實都是用Airbnb租房,且獲得許多好評?
Alice雖然可以透過截圖或公開自己的資訊向Booking.com的房東證明自己擁有這些好評,但這樣Alice的隱私或許會被洩漏,例如Alice不想讓Booking.com的房東知道自己去過哪些地方、住過哪些民宿;或者Alice有可能偽造截圖,或者偽造評價,那Booking.com的房東要如何相信Alice所提供的證明文件是真的來自Airbnb的房東?除此之外有沒有更彈性的方式,Alice可以選擇性地向Booking.com的房東證明,自己至少有10個好評,但不透露自己總共有多少好評?
Photo by Andrea Davis on Unsplash
使用Unirep協定就可以解決這個問題。UniRep 取名自 Universal Reputation,希望透過區塊鏈上智能合約的可互用性 (interoperable,指智能合約容易被多方呼叫且容易透過智能合約與對方互動),讓不管是Airbnb的房東、Booking.com的房東或是Alice都能很容易地透過Unirep的智能合約與對方互動,且透過零知識證明的方式,讓Alice的評價具有隱私的保障,Alice不用明確地向Booking.com的房東說這些評價是怎麼獲得、是什麼時候獲得,也可以彈性的證明自己至少有多少好評,或者最多有多少差評。
密碼學
Unirep主要用到的密碼學方法有
雜湊函數 hash:若有一個雜湊函數 f(x) = y 則由x可以很輕易的用f算出y,但從y推回x是幾乎不可能的,且要找到兩個不同的x對應到相同的y也是幾乎不可能的(沒有碰撞問題)。
零知識證明 zero-knowledge proof:可以將複雜的運算邏輯轉成容易驗證且具有隱私保障的驗證問題,使用者只要將變數輸入,這個零知識證明的演算法就會產生對應的證明且計算出對應的結果,使用者只要將此證明和運算結果輸入驗證的程序中,其他人就能驗證使用者是不是提出正確的證明,若驗證成功,則驗證者就能相信提出證明者高機率擁有正確的知識,也就是在計算證明時的輸入變數。
ZKP Proof System
ZKP Verification System
Semaphore:semaphore 是設計為可以用零知識證明驗證的身份認證系統。Unirep 中用來產生私鑰 (identity) 和公鑰的 hash 值(identity commitment),讓使用者不必公開 identity 仍能透過零知識證明驗證其公私鑰的對應性。
雜湊樹 Merkle trees:Unirep 中大量運用雜湊樹的方式確保評價紀錄,而其中用到的雜湊樹又分兩種:Incremental merkle tree 和 Sparse merkle tree
Incremental merkle tree: 從 index 0 開始依序插入雜湊樹中的樹葉。為了使 ZKP 的 circuit 大小固定, Unirep 中使用固定高度的 Incremental merkle tree。
Sparse merkle tree: 在特定的 index i 插入樹葉
Incremental merkle tree and sparse merkle tree
UniRep中用到的名詞定義
Epoch
指一段特定的時間,例如7天
UniRep 的 Epoch 從 1 開始計算,7天過後Epoch數加一,即 Epoch 變為 2
Epoch Key
每個使用者在每個 Epoch 都能產生 n 把 Epoch key,用來收取評價 epoch_key = hash (id, epoch, nonce)
id: 這裡指用 semaphore 產生的 identity
epoch: 表示這是在第幾個 epoch 產生的 epoch key
nonce: 若 Unirep 規定使用者能在一個 epoch 產生 5 把 epoch key,則使用者可以選從 0 到 4 為此 nonce
因為雜湊函數的性質,算出來的 epoch key 很難推回原本的 id, epoch, nonce, 所以看到 epoch key 並不能推回使用者是誰。
以Alice為例,當Alice住完Airbnb,房東會透過 epoch key 給予 Alice 評價,但房東無法知道 Alice 在同個 epoch 的其他 epoch key 是哪一把,也無法知道 Alice 在別的 epoch 獲得的評價,除非 Alice 在這個 epoch 重複使用同一把 epoch key 收取評價。
User 使用者
用 semaphore 產生 identity 並使用此 identity 註冊的使用者
使用者是接收評價、證明評價、或是花費評價的人,用 epoch key 跟其他人互動,因為 epoch key 會隨著 epoch 增加而改變,所以對使用者來說每個 epoch 能產生的 epoch key 都不同,具有保護隱私的效果。
在上面的例子中使用者指的是 Alice, Bob, Airbnb 的房東, Booking.com的房東
Attester 證人
用 Ethereum address 或 smart contract address 註冊的用戶
是會被使用者記錄下來的評價給予者
Unirep 會給這些 address 一個 attester ID,而這個 attester ID 不會隨著 epoch 增加而改變,使用者可以知道這個評價是來自哪一個 attester。
在上面的例子中指的是 Airbnb 跟 Booking.com,因為 attester ID 不變,所以使用者可以證明這些評價是來自於 Airbnb 或是 Booking.com
User State Tree (UST)
是一 Sparse merkle tree
每個使用者都有自己的 User State Tree,其中樹葉表示所收到的評價的hash值,而葉子的 index 表示 attester ID,UST 樹葉的定義為
USTLeaf = hash(posRep, negRep, graffiti)
例如 Airbnb 的 ID 是1,Booking.com 的 ID 是 3,那 Alice 的 User State Tree 中 index 為 1 的地方會有自己在 Airbnb 獲得的總評價的 hash 值,而 index 為三的地方則為空的評價。另一個使用者 Bob 的 User State Tree 亦同,在 index 為 1 的地方會有自己在 Airbnb 獲得的評價,在 index 為 3 的地方會有自己在 Booking.com的評價。
Global State Tree (GST)
是一固定樹高的 Incremental merkle tree
Global State Tree 的葉子到樹根都是公開的資訊,當有使用者註冊或者更新 User State Tree 時會在 Global State Tree 裡新增一個新的樹葉,GST 樹葉的定義為:
GSTLeaf = hash(id, USTRoot)
先送出的樹葉先插入到較前面的 index,之後的樹葉依序插入 GST 中。
以 Alice的例子來說,當 Alice跟 Bob註冊 Unirep時,都會產生一個 GST的樹葉,更新 GST的樹根,若 Alice先註冊,則 Alice的 index會較 Bob前面。注意,這邊的 Airbnb 和 Booking.com 等 attester 並不是用這棵 Global State Tree註冊。
Epoch Tree
是一個 Sparse merkle tree
Epoch Tree 跟 Global State Tree 一樣從葉子到樹根都是公開的資訊,Epoch Tree 中樹葉的 index 為 epoch key,而樹葉的值為該 epoch key 的 sealed hash chain
每個 epoch key 都有一個 hash chain,hash chain 的定義為
hashedReputation = hash(attestIdx, attesterID, posRep, negRep, graffiti)hashChain[epochKey] = hash(hashedReputation, hashChain[epochKey])
此 hash chain 是為了防止使用者漏收了哪一筆評價,如果使用者少收了其中一筆評價,則 hash chain 的結果會完全不同。最後驗證時如果其中一個 epoch key 的 hash chain 改變,會造成 epoch tree 樹根跟原本的 epoch tree 的樹根不同。
而 Sealed hash chain 是在每個 epoch 結束後,Unirep 智能合約會再將這條 hash chain 再 hash 一次
sealedHashChain[epochKey] = hash(1, hashChain[epochKey]) isEpochKeyHashChainSealed[epochKey] = true
需要再把這條 hash chain 封起來的用意是,避免這把 epoch key 過了這個 epoch 之後再繼續接收評價,所以 epoch tree 會用這個 epoch key 最後的 sealed hash chain 去計算樹根。
Nullifier
中文翻譯為註銷符,當我們要防止一件事情重複發生時,就可以使用這個 Nullifier
Unirep 中使用到 Epoch key nullifier:此 nullifier 是用來限制使用者不能在不同的 epoch 使用重複的 epoch key 去收取評價,也不能被其他使用者使用;此外也可以用來檢視使用者是否重複執行 UST 的更新
Nullifier 也用 hash 計算,但多使用一個 domain 變數,避免與 epoch key 產生相同的 nullifier 而洩露自己擁有的 epoch key,也可以用不同的 domain 產生不同用途的 nullifier
epochKeyNullifier = hash(EPOCH_KEY_DOMAIN, id, epoch, nonce)
Epoch Transition
一個 epoch 結束過後,要透過 epoch transition 的步驟,更新 Unirep 及使用者的狀態
其中要做的事包含將智能合約上的 epoch 數加一,還有將所有 epoch key 的 hash chain 封起來
接著使用者就可以執行 User State Transition 更新自己的 UST
User State Transition
到下一個 epoch 後,使用者可以透過自己的 identity,找出自己在前一個 epoch 所有的 epoch key,並根據每把 epoch key 收到的評價更新到自己的 UST,最後計算出最新的評價狀態,產生一個 GST的樹葉,插入 GST 中 (如同註冊時一樣)。
使用者之後如果要花費評價或者產生下一個 epoch 的 epoch key 時,因為必須確認自己的 UST 在當前的 epoch,所以需要經過 User State Transition 確保自己有一個 GST 的樹葉在 GST 中。
Unirep 協定
有了 Unirep 的名詞定義後,接著介紹 Unirep 是如何運作的。
註冊
Unirep 的 user 和 attester 的註冊方式不同:
User signup and attester signup in Unirep
User
User 透過 semaphore 產生 identity 和 identity commitment,identity 就如同私鑰,identity commitment 就如同公鑰
將 identity commitment 和預設的 UST 樹根經由 hash 計算得 GST 的一個樹葉
若使用者要證明自己在某個 epoch 有註冊或者有更新自己的 UST,則證明自己是 GST 的某一個樹葉,利用零知識證明的方法,輸入 identity、UST 樹根,還有 merkle tree 中要計算 hash 值的相鄰節點,則最後可得到一個 GST 的 root,其他人可以驗證這個 GST 的 root 是否符合這顆公開的 GST。
Attester
Attester 則是用自己的錢包,或者用智能合約的地址註冊,呼叫 attester sign up 的 function 後,Unirep 會指定一個 attester ID 給這個地址,往後 attester 用相同錢包或合約地址給予評價時,Unirep 會檢查此地址是否被註冊,若有註冊則可以給予 epoch key 評價。
以 Alice 和 Bob 為例,Alice、Bob、Airbnb的房東、Booking.com的房東會產生 identity 並且透過 Unirep 合約用 user 的註冊方式獲得一個 GST 的樹葉代表自己;
而 Airbnb 和 Booking.com 會透過 attester 的註冊方式,使用特定的錢包地址或是撰寫智能合約呼叫 Unirep 的 attester sign up function。
當然 Alice 或 Bob 如果想用自己的錢包註冊為 attester 也是可以,這時合約就會紀錄 Alice 和 Bob 的錢包地址,並給予一個新的 attester ID。
給予評價
在 Unirep 中評價的接收者是 epoch key,接著介紹 user 和 attester 是如何互動。
How an attester gives reputation to an epoch key
Alice 在 Unirep 註冊過後,就可以產生 epoch key 接收評價
epochKey = hash(identity, epoch, nonce)
但 Airbnb 的房東看到這把 epoch key,要如何知道 Alice 確實是 Unirep 的合法使用者,且 epoch key 的 是合法的,例如 nonce 小於 5,或者 epoch 是當前的 epoch?
如果 Alice 直接提供 epoch 和 nonce,別人沒有 identity 也無法計算此 epoch key,更不用說如果 Alice 提供 identity 會造成 Alice 完全沒有隱私可言,所有人都可以計算出 Alice 收過哪些評價。
因此我們用一個零知識證明,證明此 epoch key 是合法的。細節請參考 epoch key proof,主要是證明使用者有一個合法的 GST 樹葉在 GST 中,並且 epoch 和 nonce 也都符合。
房東得到 Alice 提供的 epoch key 和 epoch key 的證明,並且透過 Unirep 的合約驗證通過之後,就可以給予評價。
獲得空投評價、使用者可以給予評價的限制可以由各個應用自行定義,例如 Airbnb 可以決定空投 30 個正評給使用者, Booking.com 可以決定空投 20 個正評給使用者。
另外,為了確認房東也是合法的使用者,也為了防止房東重複花費 (double spending) 自己的評價點數,Unirep 上的應用也可以用 reputation nullifier 及其 proof 去證明使用者合法使用自己的評價。
例如,此 reputation nullifier 可以用下列計算方式取得:
reputationNullifier = hash(REPUTATION_DOMAIN, id, epoch, nonce)
當 reputation nullifier 及 proof 產生後,就會與房東要給的評價一起發送到 Airbnb 的智能合約上,智能合約會驗證 proof 是否合法,nullifier 是否有被發送過,若檢查都通過的話則 Unirep 會紀錄此評價給 epoch key,並將 hash chain 更新。
接收評價
使用者即使可以證明自己擁有哪一把 epoch key 並且大家都知道這把 epoch key 有多少評價,但這有可能造成使用者故意忽略其他把 epoch key 中對自己不好的評價,因此 Unirep 限制使用者只能在每個 epoch 結束,每把 epoch key 都封起來之後,才能用 User State Transition 更新自己的評價。
User State Transition in Unirep
這裏也是用 User State Transition Proof 去保證使用者是根據正確的方式計算出最新的 UST,且用 epoch tree 限制使用者必須處理每一把 epoch key 的結果。
亦即,需要等到 epoch 結束後,Alice 才能透過 User State Transition 獲得 Airbnb 房東的評價,更新自己的使用者狀態。
證明評價
當使用者通過 User State Transition 之後會有最新的 UST 狀態,此時 Alice 就可以透過 reputation proof 向 Booking.com 她有來自 Airbnb 的評價,在reputation proof 中檢查使用者是否有其宣稱的 UST (例如總共有多少好評、多少差評來自哪一個 attester ID),並且此 UST 的狀態儲存在當前 epoch 的 GST 中。
在生成 reputation proof 時,即使 Alice 總共有 100 個好評,但 Alice 仍可以產生「至少有10個好評」的證明,Booking.com 的房東若驗證成功,則只能知道 Alice 宣稱的「至少有 10 個好評」而不能知道 Alice 總共有 100 個好評。
常見問題
Alice 能不能給 Airbnb 的房東評價? Alice 能不能給 Bob 評價?
可以。
Airbnb 的房東和 Bob 也都能產生 epoch key,因此如果 Alice 有兩者的 epoch key 及合法的 proof 則可以給予評價。此時 Alice 可以選擇透過 Airbnb、Booking.com、或甚至自己的 Ethereum account 當作證人給予評價 (也必須選擇一個證人)。
Alice 可以透過 Unirep 給 Airbnb 評價嗎?
如果 Airbnb 也透過 Unirep 註冊為使用者,並且產生 epoch key 的話就可以。但如果 Airbnb 只註冊為證人的話不行。
Alice 可以證明評價來自哪一個 Airbnb 房東嗎?
如果 Airbnb 的房東沒有註冊為證人,則 Alice 不能證明評價來自哪個房東。
若 Airbnb 的房東用自己的 Ethereum account 註冊為證人,則 Alice 只能證明評價來自這個 Ethereum account,但無法知道這個 account 是一個 Airbnb 的房東。
從 Airbnb 獲得的評價可以在 Booking.com 花費嗎?
需看 Booking.com 的智能合約如何定義,但一般來說不行,因為 attester ID不同,但未來可能會開發各個應用程式之間的兌換評價功能。
如果遲遲不執行 User State Transition 會發生什麼事?會不會收不到之前的評價?
若 Alice 在第一個 epoch 註冊,並在第一個 epoch 產生 epoch key 接收評價,但 Alice 到第五個 epoch 才執行 User State Transition,那 Alice 會根據第一個 epoch 的 GST、epoch tree 執行 User State Transition,因此仍然可以在第五個 epoch 收到來自第一個 epoch 的評價;而在第二到第四個 epoch 因為 Alice 無法產生出合法的 epoch key proof,因此無法接收評價。
User State Transition 可以自動執行嗎?
不行。
只有使用者主動給出私鑰,即 semaphore 的 identity,才可以產生合法的 User State Transition proof,若將私鑰交給第三方幫忙執行可能會侵害使用者的隱私。
結論
Unirep 是一個具有隱私保障的評價系統,透過 ZKP 的保護使用者可以在匿名的情況下收取評價、給予評價、並且向他人證明自己的評價。Unirep 可以用於跨應用程式間的評價證明,可以在 A 應用程式中獲得評價,並向 B 應用程式證明在 A 應用程式中獲得多少評價。若想了解更多有關 Unirep ,可以參考 Github、文件或加入 telegram 群組討論。
本文感謝 CC, Nic, Kevin, Doris 協助審稿。
Unirep介紹: 使用ZKP的評價系統 was originally published in Taipei Ethereum Meetup on Medium, where people are continuing the conversation by highlighting and responding to this story.
👏 歡迎轉載分享鼓掌
同時也有891部Youtube影片,追蹤數超過4萬的網紅吳老師教學部落格,也在其Youtube影片中提到,東吳EXCEL VBA與資料庫雲端設計116第6次 上課內容: 01_重點回顧與格式化日期 02_用VBA設計格式化日期迴圈與邏輯判斷 03_VBA還原格式與插入空白列 04_VBA插入空白列與刪除空白列 05_VBA向上追蹤與WORD表格讀取到EXCEL 06_黑名單定義名稱與COUNTIF比對...
「一次函數定義」的推薦目錄:
一次函數定義 在 數學老師張旭 Facebook 的最讚貼文
【處處極限不存在的函數】
.
我記得自己剛升大一在學習微積分的時候,教授問了一個問題,「有沒有哪一種實變數實值函數是任何一點的極限都不存在的」,那時候我想了很久,總是想不出來到底要怎麼設計,才有辦法完成教授的要求。那時候我一直想不透的癥結點是,如果要在任意點的極限都不存在的話,那可能要先解決一個問題,那就是在設計了一個在某一點,例如說 a 點,極限不存在的函數以後,要如何改造這個函數,才有辦法讓 a 點「旁邊」的點其極限也不存在。
.
(接下來的內容,建議同學們可以拿支筆在紙上按照說明把函數畫出來)
.
舉例來說,如果我們設計了一個在 x = 0 這個點極限不存在的函數(例如設定這個函數在 x 小於 0 時其函數值均為 0;而當 x 大於 0 時其函數值均為 1),那麼要如何改造或調整這個函數,才有辦法讓這個函數在 x = 0 的「旁邊」的點其極限也不存在呢?針對這個例子而言,或許可以這樣做:先將這個函數在 x 大於 1 以後的函數值改成 0.5,那麼這個函數就會變成在 x = 0 和 x = 1 的時候極限都不存在,但因為 1 並非 0「旁邊」的數字,所以顯然還要再調整,於是我們再將 x 大於 0.5 以後的函數值都改成 0.5,那麼這個函數就會變成在 x = 0 和 x = 0.5 處其極限不存在,但同樣地,因為 0.5 並非 0「旁邊」的數字,所以我們繼續調整這個函數,下一步當然是將 x 大於 0.25 以後的函數值都改成 0.5,依此類推,再下一步就是將 x 大於 0.125 以後的函數值都改成 0.5,持續這樣的步驟,最終我們會得到一個當 x 小於 0 時其函數值為 0 而當 x 大於 0 其函數值為 0.5 的函數。這個函數當然仍然在 x = 0 的時候其極限不存在,但是原本在調整時的兩點極限不存在,卻因無限持續這樣的步驟,而變回了僅在 x = 0 極限不存在的狀態。這結果實在令人沮喪。
.
之所以會產生這樣的狀況,是因為持續了無限次將新增的極限不存在的點向 x = 0 處靠近的緣故。既然如此,那如果不要持續上面的步驟無限次呢?如果僅持續有限次的步驟,那麼在該次步驟的下一次,一定可以把 x = 0 右邊新增的極限不存在的點向 x = 0 再靠近一些,這個推論的結果就是,如果僅持續有限次上述的步驟,那麼就無法達成創造一個在 x = 0 的「旁邊」的極限不存在的點。結果,無論是有限次或無限次操作上述的步驟,最終都無法達成我們的目標。這真的真的非常令人沮喪,因為這意味著從一個點的極限不存在出發,去逐步改造出一個處處極限不存在的函數,方向很可能是錯誤的。
.
那麼,該怎麼辦呢?
.
面對這個問題,當時的我最終並沒有自己解出來,而是一個比過奧數的朋友在老師公布答案之前成功地解了出來,並告訴我他的想法。
.
他告訴我,既然從一個點的極限不存在開始是行不通的,那就一次就創造一大堆極限不存在的點吧!例如一開始的函數乾脆設定成這樣:當 x 介在 n 和 n + 1 之間且 n 為偶數時,將其函數值設定為 0,而其他地方則設定為 1。例如,當 x 介在 0 和 1 之間或介在 2 和 3 之間時,其函數值就是 0,而當 x 介在 1 和 2 之間或介在 99 和 100 之間時,其函數值就是 1。如此一來,我們就獲得了一個在每一個整數點其極限都不存在的函數。
.
以此為起點,比起我想的那個例子最初的樣子一次新增了無限多個極限不存在的點,似乎好像有了長遠的進步,但到此階段實際上並沒有解決我最一開始講的問題的癥結點,那就是如何在一個極限不存在的點的「旁邊」創造一個極限也不存在的點。
.
為了解決這個問題,我的朋友告訴我,下一步是在每一個「區間」裡進行調整。用例子來說明而剩下類推的話,大概是這樣操作:例如,在 0 和 1 之間,函數值原本都是 0,但接下來把這個區間切割成 10 等分,然後第 1、3、5、7、9 個區間(也就是在 x 介在 0 和 0.1、介在 0.2 和 0.3、介在 0.4 和 0.5、介在 0.6 和 0.7、介在 0.8 和 0.9 之間的這幾個區間),我們把函數值調整成 1,其餘的不動,那麼我們就可以得到一個,除了在所有整數點極限都不存在的函數以外,這個函數在 0.1、0.2、0.3、0.4、0.5、0.6、0.7、0.8、0.9 的極限也不存在。那如果是在原本函數值為 1 的區間,則在等分割成 10 個區間以後,將第 2、4、6、8、10 個區間的函數值調整成 0。若將上面這些動複製到其他區間的話,那麼在每一個整數區間(就是 n 到 n + 1 的區間)裡面,其十分位數的位置其極限都不存在。
.
接下來,再將函數值為 1 的區間等分割為 10 個區間,然後第 2、4、6、8、10 個區間其函數值都調整成 0,而函數值為 0 的區間一樣等分割為 10 個區間,但是是將第 1、3、5、7、9 個區間的函數值調整成 1,那麼,這個函數就變成了一個除了在所有整數點極限都不存在以外,但在每一個整數區間裡面其百分位數的位置極限都不存在的函數。
.
再接下來,繼續進行上面的動作,不斷地十等分分割之前產生的區間,並且適當地調整其函數值,使其在任一階段裡面都是前一個區間裡面的函數值是 0 且後一個區間裡面的函數值是 1 ,或前一個區間的函數值是 1 而後一個區間裡的函數值是 0 的狀態,持續無限次,最終就會得到一個在任一點其極限值都不存在的函數了。
.
要證明這個函數處處極限不存在有分簡單版和嚴格版,這邊我們先講簡單版,以後有機會再談嚴格版。對於這個函數而言,固定任何一點 a,其左極限只有兩種可能,0 或 1,但因為這個函數被分割地非常地密,而且連續幾個區間在任一階段裡面都是一下子 0 一下子 1 這樣變動,所以這個函數在 a 點的左極限不存在,因此這個函數在 a 點的極限並不存在。最後,因為 a 這個點是任意取的,所以我們可以說這個函數的極限值在任意點都不存在。
.
這個答案真的很猛,因為當時在班上只有我那位奧數的朋友給出了教授點頭的答案。
.
雖然當初他並沒有辦法清楚地講出左極限不存在的原因,也因為我們還沒學到極限的嚴格定義,所以沒辦法用嚴謹的敘述來證明這樣的函數確實處處極限不存在,但現在回想起來,那位奧數朋友還是很猛!因為他就好像那種天生的小說家一樣,信手拈來就寫出了一本傑出的小說,而我們凡人卻連寫一篇普通的文章都很成問題。
.
講到這裡,今天的故事似乎已經講完,但其實還沒,因為這樣聰明的人,並不會只出現我們班上甚至是這個時代而已。
.
關於「是否存在一個處處極限都不存在的函數」這個問題,其實在 19 世紀時,就有一位叫做 Dirichlet 的德國數學家,他所創造出來的一種函數(後來稱為 Dirichlet 函數),就是處處極限不存在的函數。這個函數的定義如下:當 x 為有理數時,其函數值是 1;當 x 不為有理數時,其函數值是 0。這樣的函數確實也處處極限不存在,也是我教授當時給同學們預設的答案。
.
在這邊我就不文字解釋為何 Dirichlet 函數處處極限不存在了,但我有拍一部影片來說明,如果你想繼續看下去,可以點開我貼在本篇文章留言處的這部影片,我有盡量簡單地解釋為何 Dirichlet 函數處處極限不存在。
.
雖然 Dirichlet 函數處處極限不存在,但其實當初 Dirichlet 所面對的問題,並非「是否存在處處極限不存在的函數」,而是「是否存在無法圖像化的函數」。在經過可能類似這篇文章最一開始的那些推敲以後,Dirichlet 創造了 Dirichlet 函數,而這個 Dirichlet 函數就是一個「客觀存在」但「無法圖像化」的函數。並且,除了無法圖像化以外,Dirichlet 函數在數學上也有著很重要的地位,因為他常常是一些直覺上無法察覺的現象的重要例子。例如我們直覺上都會認為只要函數有週期,那麼就會存在最小週期,但 Dirichlet 函數就是一個不具有最小週期的週期函數,因為任意有理數都是它的週期。
.
關於 Dirichlet 函數的性質我們就講到這邊,或許以後有機會可以專門寫一篇跟 Dirichlet 函數有關的文章,不過有很多性質都是需要具備更多數學知識以後才能介紹的,所以如果真的要寫的話,那可能就還要再等一陣子了。
.
最後,跟大家介紹一下我上面所提到的影片,那是我在 2020 年時所拍攝的一系列微積分教學影片的其中一集。該系列影片基本上有觀念講解、精選範例和補充教材,近期我會開始陸續上傳到這裡,但不是每一部影片都會寫文章來搭配,所以如果你想跟著我上傳的速度一部一部看,而且不漏掉系列裡每一部影片的話,可以關注我在西瓜視頻、騰訊視頻和優酷視頻的頻道;如果你想一次看完我全系列的影片的話,可以關注我在 YouTube、bilibili 或 Pornhub 上的頻道,上面已經上傳了張旭微積分全系列影片。另外這系列影片都有講義電子檔可以搭配使用,如果你想要取得該電子檔的話,請幫我按讚這篇文章和這個粉專、分享這篇文章,並幫我到我的臉書粉專評論處寫個評論,然後私訊我的臉書粉專,我的夥伴就會回覆你講義電子檔的連結。
.
感謝你的觀看,希望這篇文章對你有所幫助,有任何問題或想法也歡迎在下面留言告訴我。另外,本文章同步發佈於數學老師張旭的 YouTube 頻道社群、微博、今日頭條、Medium 和 HackMD,若你也有上面提到的那些帳號,歡迎按讚、分享和關注!
一次函數定義 在 台灣物聯網實驗室 IOT Labs Facebook 的最佳貼文
為了讓 AI 不斷打怪升級,DeepMind 打造「宇宙」
作者 雷鋒網 | 發布日期 2021 年 07 月 30 日 8:15 |
DeepMind 又給我們小驚喜。我們都知道,強化學習苦於類化能力差,經常只能針對單個任務從頭學習。
DeepMind之前開發的AlphaZero,儘管可以玩圍棋、西洋棋和日本將棋,但每種棋牌遊戲都只能從頭訓練。類化能力差也是AI一直被詬病為人工智障的一大原因。人類智慧的厲害之處,就在藉鑑之前經驗迅速適應新環境。
但類化能力不是一蹴而就,就像玩遊戲,也是先做簡單任務,逐步升級到複雜任務。《空洞騎士》(Hollow Knight)一開始只需要隨意走動揮刀砍怪,但噩夢級難度的「苦痛之路」關,沒有前面累積的技巧,只能玩寂寞。
多任務宇宙
DeepMind此次採用「課程學習」,讓智慧體於不斷擴展升級的開放世界學習。也就是說,AI新任務(訓練資料)是基於舊任務不斷生成。智慧體可盡情鍛鍊自己,簡單的如「靠近紫色立方體」,複雜點的如「靠近紫色立方體或將黃色球體放在紅色地板」,甚至和其他智慧體玩耍,如捉迷藏──「找到對方,且不要被對方發現」。
每個小遊戲存在世界小角落,千千萬萬個小角落拼成龐大的物理模擬世界,如下圖的幾何「地球」。總體來說這個世界的任務由三個要素構成,即任務=遊戲+世界+玩家,並根據三要素關係,決定任務的複雜度。
複雜度的判斷有四個維度:競爭性、平衡性、可選項、探索難度。
比如「搶方塊」遊戲,藍色智慧體需要把黃色方塊放到白色區域,紅色智慧體需要把黃色方塊放到藍色區域。這兩個目標矛盾,因此競爭性較強;同時雙方條件對等,平衡性比較高;因目標簡單,所以可選項少;DeepMind把探索難度評為中上,可能是因定位區域算較複雜的場景。
再如「球球喜歡和方塊一起玩」遊戲,藍色和紅色智慧體有共同目標,讓相同顏色的球體和方塊放在相近位置。
這時競爭性自然很低,平衡性毋庸置疑很高的;可選項比上面遊戲高很多;探索難度沒有定位區域,智慧體隨便把球體和方塊放哪都行,難度就變小了。
基於這四個維度,DeepMind打造超大規模「宇宙」任務空間,幾何「地球」也只是這宇宙的小角落,是四維任務空間的一點。DeepMind將「宇宙」命名為XLand,包含數十億個任務。
來看XLand的全貌,由一系列遊戲組成,每個遊戲在許多模擬世界進行,這些世界的拓樸和特徵平滑變化。
終生學習
數據有了,接下來得找到合適的算法。 DeepMind發現,目標注意代理(GOAT)可學習更通用的策略。
具體來說,智慧體輸入包括第一視角的RGB圖像、本體感覺以及目標。經過初步處理後,生成中間輸出,傳遞給GOAT模組,會根據智慧體目前目標處理中間輸出的特定部分,邏輯分析目標。
邏輯分析是指,每個遊戲可藉由一些方法,構建另一個遊戲,並限制策略的價值函數的最優值上限或下限。
DeepMind提出一個問題:對每個智慧體,什麼樣的任務是最好的?換句話說,打怪升級時,什麼樣的關卡設置才讓玩家順利升級為「真」高手,而不是一刀9999?
DeepMind的答案是,每個新任務都基於舊任務生成,「不會太難,也不會太容易」。其實恰好是讓人類學習時感覺「爽」的興奮點。
訓練開始時,太難或太容易的任務可能會鼓勵早期學習,但會導致訓練後期的學習飽和或停滯。不要求智慧體某任務非常優秀,而是鼓勵終身學習,即不斷適應新任務。所謂太難、太容易是較模糊的描述。需要量化方法,在新任務和舊任務之間彈性連接。
怎麼不讓智慧體做新任務時不適應而「暴死」?進化學習就提供很好的靈活性。總體來說,新任務和舊任務同時進行,且每個任務有多智慧體參與「競爭」。舊任務適應好的智慧體,會選拔到新任務繼續學習。
新任務中,舊任務的優秀智慧體權重、瞬間任務分佈、超參數都會複製,參與新一輪「競爭」。除了舊任務的優秀智慧體,還有很多新人參與,這就引進隨機性、創新性、靈活性,不用擔心「暴死」問題。
當然,因任務不斷生成、動態變化,一個任務可訓練不同長處的智慧體,並往不同方向演化(隨著智慧體相對性能和強健性進行)。最終每個智慧體都會形成擅長任務的集合,就像春秋戰國時期「百家爭鳴」。說打怪升級顯得格局小,簡直是模擬地球。
DeepMind表示,「這種組合學習系統的特性是,不最佳化有界性能指標,而是更新定義的通用能力範圍,這使智慧體開放式學習,僅受環境空間和智慧體的神經網路表達能力的限制。」
智慧初現
最終這複雜「宇宙」升級、進化、分流的智慧體長成了什麼優秀物種?DeepMind說,智慧體有很明顯的零樣本學習能力,比如使用工具、合圍、數數、合作+競爭等。
來看具體例子。首先智慧體學會臨機應變。目標有三個:
黑色金字塔放到黃色球體旁邊
紫色球體放到黃色金字塔旁邊
黑色金字塔放到橙色地板
AI一開始找到一個黑色金字塔,想拿到橙色地板(目標3),但搬運過程瞄見黃色球體,瞬間改變主意,「我可以實現目標1啦」,將黑色金字塔放到黃色球體旁邊。
第二個例子是,不會跳高,怎麼拿到高台上的紫色金字塔?智慧體需要想辦法突破障礙,取得高台上的紫色金字塔,高台周邊並沒有類似階梯、斜坡的路。
因不會跳高,所以智慧體「掀桌子」,把周邊幾塊豎起來的板子弄倒。然後一塊黑色石板剛好倒在高台邊,「等等,這不就是我要的階梯嗎?」這過程是否體現了慧體的智慧,還無法肯定,可能只是一時幸運。關鍵還是,要看統計數據。
經過5代訓練,智慧體在XLand的4千個獨立世界玩了約70萬個獨立遊戲,涉及340萬個獨立任務,最後一代每個智慧體都經歷2千億次訓練步驟。智慧體已能順利參與幾乎每個評估任務,除了少數即使人類也無法完成的任務。
DeepMind的研究,或許一定程度體現「密集學習」重要性。也就是說,不僅資料量要大,任務量也要大。這也使得智慧體在類化能力有很好表現,如資料顯示,只需對一些新複雜任務進行30分鐘集中訓練,智慧體就可快速適應,而從頭開始用強化學習訓練的智慧體根本無法學習這些任務。
往後我們也期待這「宇宙」更複雜和生機勃勃,AI經過不斷演化,不斷給我們帶來驚喜(細思極恐)的體驗。
資料來源:https://technews.tw/2021/07/30/deepmind_xland/
一次函數定義 在 吳老師教學部落格 Youtube 的精選貼文
東吳EXCEL VBA與資料庫雲端設計116第6次
上課內容:
01_重點回顧與格式化日期
02_用VBA設計格式化日期迴圈與邏輯判斷
03_VBA還原格式與插入空白列
04_VBA插入空白列與刪除空白列
05_VBA向上追蹤與WORD表格讀取到EXCEL
06_黑名單定義名稱與COUNTIF比對資料與篩選
07_黑名單改為VBA篩選與複製範圍
完整教學
http://goo.gl/aQTMFS
吳老師教學論壇
http://www.tqc.idv.tw/
教學論壇(之後課程會放論壇上課學員請自行加入):
https://groups.google.com/forum/?hl=zh-TW#!forum/excel-vba-116
懶人包:
EXCEL函數與VBA http://terry28853669.pixnet.net/blog/category/list/1384521
EXCEL VBA自動化教學 http://terry28853669.pixnet.net/blog/category/list/1384524
課程簡介
五大類函數與自訂函數
一、文字和資料函數
二、邏輯函數
三、日期和時間函數
四、數學和三角函數
五、檢視和參照函數
其他綜合範例
上課用書:
Excel VBA一點都不難:一鍵搞定所有報表
作者: Excel Home
出版社:博碩
出版日期:2013/06/26
定價:380元
超圖解 Excel VBA 基礎講座
作者: 亮亨/譯 出版社:旗標
出版日期:2006/05/15 定價:420元
日本Amazon網站同類書籍銷售No.1
吳老師 110/8/9
函數,東吳進修推廣部,自強基金會,程式設計,線上教學excel vba教學電子書,excel vba範例,vba語法,vba教學網站,vba教學講義,vba範例教學,excel vba教學視頻
![post-title](https://i.ytimg.com/vi/sJMqUilJDQ4/hqdefault.jpg)
一次函數定義 在 吳老師教學部落格 Youtube 的最讚貼文
東吳EXCEL VBA與資料庫雲端設計116第6次
上課內容:
01_重點回顧與格式化日期
02_用VBA設計格式化日期迴圈與邏輯判斷
03_VBA還原格式與插入空白列
04_VBA插入空白列與刪除空白列
05_VBA向上追蹤與WORD表格讀取到EXCEL
06_黑名單定義名稱與COUNTIF比對資料與篩選
07_黑名單改為VBA篩選與複製範圍
完整教學
http://goo.gl/aQTMFS
吳老師教學論壇
http://www.tqc.idv.tw/
教學論壇(之後課程會放論壇上課學員請自行加入):
https://groups.google.com/forum/?hl=zh-TW#!forum/excel-vba-116
懶人包:
EXCEL函數與VBA http://terry28853669.pixnet.net/blog/category/list/1384521
EXCEL VBA自動化教學 http://terry28853669.pixnet.net/blog/category/list/1384524
課程簡介
五大類函數與自訂函數
一、文字和資料函數
二、邏輯函數
三、日期和時間函數
四、數學和三角函數
五、檢視和參照函數
其他綜合範例
上課用書:
Excel VBA一點都不難:一鍵搞定所有報表
作者: Excel Home
出版社:博碩
出版日期:2013/06/26
定價:380元
超圖解 Excel VBA 基礎講座
作者: 亮亨/譯 出版社:旗標
出版日期:2006/05/15 定價:420元
日本Amazon網站同類書籍銷售No.1
吳老師 110/8/9
函數,東吳進修推廣部,自強基金會,程式設計,線上教學excel vba教學電子書,excel vba範例,vba語法,vba教學網站,vba教學講義,vba範例教學,excel vba教學視頻
![post-title](https://i.ytimg.com/vi/aFO7q5igYzk/hqdefault.jpg)
一次函數定義 在 吳老師教學部落格 Youtube 的最佳解答
東吳EXCEL VBA與資料庫雲端設計116第6次
上課內容:
01_重點回顧與格式化日期
02_用VBA設計格式化日期迴圈與邏輯判斷
03_VBA還原格式與插入空白列
04_VBA插入空白列與刪除空白列
05_VBA向上追蹤與WORD表格讀取到EXCEL
06_黑名單定義名稱與COUNTIF比對資料與篩選
07_黑名單改為VBA篩選與複製範圍
完整教學
http://goo.gl/aQTMFS
吳老師教學論壇
http://www.tqc.idv.tw/
教學論壇(之後課程會放論壇上課學員請自行加入):
https://groups.google.com/forum/?hl=zh-TW#!forum/excel-vba-116
懶人包:
EXCEL函數與VBA http://terry28853669.pixnet.net/blog/category/list/1384521
EXCEL VBA自動化教學 http://terry28853669.pixnet.net/blog/category/list/1384524
課程簡介
五大類函數與自訂函數
一、文字和資料函數
二、邏輯函數
三、日期和時間函數
四、數學和三角函數
五、檢視和參照函數
其他綜合範例
上課用書:
Excel VBA一點都不難:一鍵搞定所有報表
作者: Excel Home
出版社:博碩
出版日期:2013/06/26
定價:380元
超圖解 Excel VBA 基礎講座
作者: 亮亨/譯 出版社:旗標
出版日期:2006/05/15 定價:420元
日本Amazon網站同類書籍銷售No.1
吳老師 110/8/9
函數,東吳進修推廣部,自強基金會,程式設計,線上教學excel vba教學電子書,excel vba範例,vba語法,vba教學網站,vba教學講義,vba範例教學,excel vba教學視頻
![post-title](https://i.ytimg.com/vi/TucB5NiQe8M/hqdefault.jpg)
一次函數定義 在 15.一次函數 - YouTube 的推薦與評價
![影片讀取中](/images/youtube.png)
7年級數學|一次弄懂一元一次式的觀念&題型 · Dance Academy · 九下數學~ch1二次函數 · 10 一次函数 中考数学复习初中数学 · 🔯最新課綱🔯 九下數學~ 一次函數 ... ... <看更多>
一次函數定義 在 【觀念】常數函數與一次函數 - YouTube 的推薦與評價
【觀念】常數函數與 一次函數. 均一教育平台Junyi Academy ... 7.2K views 1 year ago 【均一x 酷課雲】【八年級數學】函數 … Show more. Show more. ... <看更多>