実行時自動チューニングのための逐次実験計画～分散が共通な２つの正規分布の場合～

全文

(1)2006−HPC−108（3） 2006／10／5. 社団法人情報処理学会研究報告 IPSJ SIG Technical Report. ታⴕᤨ⥄േ࠴ࡘ࡯࠾ࡦࠣߩߚ߼ߩㅙᰴታ㛎⸘↹ 㨪ಽᢔ߇౒ㅢߥ㧞ߟߩᱜⷙಽᏓߩ႐ว㨪㗇. ↰. ␞. ੳ†. ᧄⓂߢߪታⴕᤨ⥄േ࠴ࡘ࡯࠾ࡦࠣߩߚ߼ߩㅙᰴታ㛎⸘↹ࠍขࠅ਄ߍࠆ㧚߭ߣߟߩ⸘▚ࠍታⴕߔࠆ 2 ߟߩታⵝ߇ሽ࿷ߒ㧘ታⴕᤨ㑆ߪᱜⷙಽᏓߢ㧘ಽᢔߪᧂ⍮ߛ߇౒ㅢߢ޽ࠆߣ઒ቯߔࠆ㧚ਈ߃ࠄࠇߚ᦭㒢 ߩ࿁ᢙ➅ࠅ㄰ߒ๭߮಴ߐࠇࠆ߽ߩߣߒߡ㧘๭߮಴ߒߩ৻ㇱࠍᕈ⢻⹏ଔߦ↪޿ࠆߎߣߢ㧘ో૕ߩታⴕᤨ 㑆ࠍᦨዊߦߒߚ޿㧚ߎߩ໧㗴ߪ Bandit Problem ߣߒߡ⍮ࠄࠇߡ߅ࠅ㧘ࡌࠗ࠭⛔⸘ߦၮߠߊᦨㆡ⸃ ࠍᢙ୯⸘▚ߦࠃࠅ᳞߼ߚ㧚 ࡌࠗ࠭⛔⸘ߢߪ 4 ࿁⋡ߩ⹜ⴕߢߤߜࠄࠍㆬᛯߔߴ߈߆╵߃߇಴ߥ޿߇㧘ᐔဋᚲⷐᤨ㑆߇⍴޿߶߁ࠍ ㆬᛯߔࠆߩ߇ࠃ޿ࠄߒ޿ߎߣ߇㧘ታ㛎⊛ߦ␜ߐࠇߚ㧚߹ߚ㧘ઁߩ 2 ⒳㘃ߩᚻᴺߣߩᲧセߦࠃࠅ㧘ࡌࠗ ࠭⛔⸘ߦࠃࠆᚻᴺ߇ఝࠇߡ޿ࠆߎߣ߇␜ߐࠇߚ㧚. Sequential Experimental Design for Run-time Automatic Tuning – Two Normals of Common Variance – Reiji SUDA† Sequential design of experiments for run-time automatic performance tuning is discussed. Two implementations are assumed for one computation, whose execution times have normal distributions with common unknown variance. The total execution time of a given ﬁnite number of repeated calls is minimized, utilizing some calls for performance evaluation. This is known as Bandit Problem, and we obtain the optimum solution based on Bayesian model numerically. Bayesian model gives no solution for the fourth call, but experimental results were in favor of choosing the one of shorter average execution time. Bayesian solution was compared to two other solutions, and shown to be better than them.. ᜼ߍࠄࠇࠆ㧔⋥㊁ࠄߩႎ๔1) ߥߤࠍෳᾖ㧕㧚ߎࠇࠄߩ࠰ࡈ. 1. ߪ ߓ ߼ ߦ. ࠻࠙ࠚࠕߪ․ቯߩ࠰ࡈ࠻࠙ࠚࠕߦ⥄േ࠴ࡘ࡯࠾ࡦࠣᯏ᭴ࠍ. ⸘▚ᯏߣࡀ࠶࠻ࡢ࡯ࠢߩ⊒ዷߦࠃࠅ㧘ᖱႎࠍಣℂߒߚ. ታⵝߒߚ߽ߩߢ޽ࠆ߇㧘ߘߩ᭴▽ߦߪ㕖Ᏹߦᄢ߈ߥഭജ. ࠅ⊒ାߒߚࠅߔࠆਥ૕߇᳢↪ߩ⸘▚ᯏ߆ࠄ᭽‫ߥޘ‬ᖱႎᯏ. ߇ᔅⷐߢ޽ࠆ㧚ߎࠇߦኻߒ ᩿ࠄߩ ABCLibScript2),3). ེ߳ߣᐢ߇ߞߡ޿ࠆ㧚ߒ߆߽㧘ࠣ࡝࠶࠼㧘ࡕࡃࠗ࡞㧘࡙ࡆ. ߪ㧘ࡊࡠࠣ࡜ࡓ࠰࡯ࠬਛߦᜰ␜ⴕࠍᝌ౉ߔࠆߎߣߦࠃࠅ㧘. ࠠ࠲ࠬߥߤ㧘዁᧪ߦะߌߡߎߩ௑ะࠍߐࠄߦടㅦߐߖࠆ. ࠰ࡈ࠻࠙ࠚࠕߦ⥄േ࠴ࡘ࡯࠾ࡦࠣᯏ⢻ࠍઃടߔࠆߎߣ߇. ࠃ߁ߥ⎇ⓥ߇ᢙᄙߊዷ㐿ߐࠇߡ޿ࠆ㧚߹ߚ⚵ߺㄟߺࠪࠬ. ߢ߈ࠆࠪࠬ࠹ࡓߢ޽ࠆ㧚ᚒ‫ߦࠄߐࠍࠇߎߪޘ‬ㅴ߼㧘⥄േ. ࠹ࡓߥߤߢߪ㧘ಣℂߔࠆౝኈ߇ᰴ╙ߦ㜞ᐲߢⶄ㔀ߦߥߞ. ࠴ࡘ࡯࠾ࡦࠣࠍ᳢↪⊛ߥᛛⴚߣߒߡ⏕┙ߔࠆߎߣࠍ⋡ᜰ. ߡ߈ߡ߅ࠅ㧘᳢↪⊛ߥ࠰ࡈ࠻࠙ࠚࠕߩㆡ↪ߩᔅⷐᕈ߇㜞. ߒ㧘⎇ⓥࠍⴕߞߡ޿ࠆ4),5) 㧚ᧄⓂߢߪႎ๔ 4) ߦᒁ߈⛯޿. ߹ߞߡ޿ࠆ㧚ߒ߆ߒ㧘⸘▚ᯏࠕ࡯ࠠ࠹ࠢ࠴ࡖߦ߅ߌࠆ㜞. ߡ㧘ታⴕᤨ⥄േ࠴ࡘ࡯࠾ࡦࠣߩߚ߼ߦᔅⷐߣߥࠆㅙᰴታ. ਗ೉ൻ㧘ࡔࡕ࡝߿ਗ೉ᕈߩ㜞㓏ጀൻߥߤߦࠃࠅ㧘⸘▚ᯏ. 㛎⸘↹ߩ໧㗴ࠍขࠅ਄ߍࠆ㧚. ߇ᧄ᧪ᜬߟಣℂ⢻ജࠍㆡಾߦᒁ߈಴ߔ࠰ࡈ࠻࠙ࠚࠕࠍ᭴. 1.1 ໧ 㗴 ⸳ ቯ. ▽ߔࠆߎߣߪ޿ࠃ޿ࠃ㔍ߒߊߥߞߡ޿ࠆ㧚ᄙ᭽ߥࡂ࡯࠼. ޽ࠆࡊࡠࠣ࡜ࡓ߇㧘࡜ࠗࡉ࡜࡝࡞࡯࠴ࡦߩࠃ߁ߥࠨࡉ. ࠙ࠚࠕⅣႺߣᄙ᭽ߥ೑↪ⅣႺߦ߅޿ߡ㧘৻ቯߩ᳓Ḱߩಣℂ. ࡞࡯࠴ࡦࠍ➅ࠅ㄰ߒ๭߮಴ߔ႐วࠍ⠨߃ࠆ㧚ᔅⷐߣߐࠇ. ᕈ⢻ࠍ㆐ᚑߔࠆߚ߼ߦߪ㧘࠰ࡈ࠻࠙ࠚࠕ߇ߎࠇࠄߩⅣႺ. ࠆ⸘▚ࠍታ⃻ߔࠆ࡞࡯࠴ࡦ߇ⶄᢙ޽ࠆ߇㧘ߘߩ޿ߕࠇ߇. ߦㆡᔕߔࠆࠃ߁ߥ૗ࠄ߆ߩᯏ᭴ࠍ஻߃ߥߌࠇ߫ߥࠄߥ޿㧚. 㜞ᕈ⢻ߢ޽ࠆ߆߇੐೨ߦߪಽ߆ߞߡ޿ߥ޿႐ว㧘෻ᓳߐࠇ. ૶↪ߔࠆࡂ࡯࠼࠙ࠚࠕߦㆡᔕߔࠆᯏ᭴ࠍ஻߃ߚ࠰ࡈ࠻. ࠆ๭߮಴ߒߩ৻ㇱࠍᕈ⢻⹏ଔߩߚ߼ߩታ㛎ߦ↪޿ߡ㧘ᕈ. ࠙ࠚࠕߣߒߡᚑഞߒߚ߽ߩߦ㧘PHiPAC ߿ ATLAS ߥߤ. ⢻ߩࠃ޿࡞࡯࠴ࡦࠍតߔߣ޿߁ߎߣ߇⠨߃ࠄࠇࠆ㧚ߎߩ. ࠍߪߓ߼ߣߔࠆ⥄േ࠴ࡘ࡯࠾ࡦࠣᯏ⢻ઃ߈࡜ࠗࡉ࡜࡝߇. ߣ߈㧘ᄙᢙߩታ㛎ࠍⴕ߃߫⏕ታߥᕈ⢻Ყセ߇ⴕ߃ࠆ߇㧘ᕈ ⢻ߩᖡ޿࡞࡯࠴ࡦ߽ᄙߊ๭߮಴ߐࠇߡߒ߹߁㧚ߒ߆ߒዋ. † ᧲੩ᄢቇ ᖱႎℂᎿቇ♽⎇ⓥ⑼ Grad. Schl. of Information Science and Technology, the University of Tokyo. ᢙߩታ㛎ߢߪᕈ⢻⹏ଔ߇ਇචಽߢ㧘ᕈ⢻ߩࠃ޿࡞࡯࠴ࡦ ࠍㆬ߮ߘߎߥ߁ෂ㒾ᕈ߇޽ࠆ㧚ߘߎߢ㧘⹏ଔߢᓧࠄࠇࠆᖱ. −13−.

(2) ႎ㊂ߣ⹏ଔߩߚ߼ߩࠦࠬ࠻ߩ㑆ߦ࠻࡟࡯࠼ࠝࡈ߇↢ߓࠆ㧚. x1 , x2 , · · · , xn ߇ᓧࠄࠇ㧘Y ࠍ m ࿁ㆬᛯߒߡታⴕᤨ㑆. ੹࿁ߩ໧㗴⸳ቯࠍౕ૕⊛ߦ⺑᣿ߔࠆ㧚หߓౝኈߩ⸘▚. y1 , y2 , · · · , ym ߇ᓧࠄࠇߡ޿ࠆߣߔࠆ㧚޿߹ᱜⷙಽᏓࠍ઒. ࠍታ⃻ߔࠆ࡞࡯࠴ࡦߪ X, Y ߩ 2 ߟߣߔࠆ㧚ฦ࡞࡯࠴ࡦ. ቯߒߡ޿ࠆ߆ࠄߎࠇࠄߩ⚿ว⏕₸ኒᐲߪ. μ. ߩᚲⷐᤨ㑆ߪ੕޿ߦ⁛┙ߥᱜⷙಽᏓߣߒ㧘X ߩᚲⷐᤨ㑆 ߪ N(. 2. ), Y ߩᚲⷐᤨ㑆ߪ N(. 2. ) ߩࠃ߁ߦ㧘ಽ. f (xi , yj |. 1,. 2, . 2. $. )=. ¶n+m. 1. X, Y ਔᣇࠍ޽ࠊߖߚ࡞࡯࠴ࡦߩ๭߮಴ߒ࿁ᢙ M ߪ᦭. 2$ 2 ¶ P (xi 1 ) + (yj 2 )2 × exp 2 2 P P ߣߥࠆ㧚ߎߎߢ x ¯ = xi /n, y¯ = yj /m ߅ࠃ߮. 㒢ߩᢛᢙߢ㧘M ߪᣢ⍮ߢ޽ࠆߣߔࠆ㧚╙ i ࿁⋡ߩ๭߮. V =. 1,. 2,. ᢔ߇╬ߒ޿߽ߩߣ઒ቯߔࠆ㧚ߎߎߢ㧘X ߩᐔဋᚲⷐᤨ㑆 1,. Y ߩᐔဋᚲⷐᤨ㑆. 2,. ౒ㅢߩಽᢔ 2 ߪᧂ⍮ߣߔࠆ㧚. μ P. ಴ߒߦ߅޿ߡߪ㧘+ (i) = 1 ߢ޽ࠇ߫ X ࠍ㧘+ (i) = 2 ߢ. P. (xi x ¯)2 +. $(. ޽ࠇ߫ Y ࠍㆬᛯߔࠆ㧚ߎߩࠃ߁ߦ࡞࡯࠴ࡦߩㆬᛯࠍ⴫ߔ. 2, . 1,. 2. P. (yj y¯)2 ߣ߅ߊߣ. |xi , yj ). f (xi , yj |. 㑐ᢙ + (i) ࠍᚢ⇛ߣ๭߱߇㧘+ (i) ߪ╙ i 1 ࿁⋡߹ߢߩ. 2. 1,. 2 n+m+2 2. ( ). ๭߮಴ߒߦ߅ߌࠆㆬᛯߣᚲⷐᤨ㑆ߦଐሽߒߡࠃ޿㧔ታ㛎. μ. 2, . 2. )$(. ³. exp . (¯ x 1) × exp 2 2 /n. ⸘↹߇ߘࠇ߹ߢߩታ㛎⚿ᨐߦଐሽߔࠆߚ߼ㅙᰴታ㛎⸘↹. (sequential design) ߣ๭߫ࠇࠆ㧕㧚╙ i 1 ࿁⋡߹ߢߩ. 2. 2, . 1,. ´ V. ¶2. 2. 2. ). μ. (¯ y 2 )2 exp 2 2 /n. ¶. ᚲⷐᤨ㑆ߪ⏕₸⊛ߦᄌേߔࠆߩߢ㧘╙ i ࿁⋡ߩㆬᛯ + (i). ߣߥࠆ㧚ߎࠇߪ㧘V / 2 ߩ๟ㄝ੐ᓟಽᏓ߇⥄↱ᐲ n+m2. ߽⏕₸⊛ߥ᜼േࠍ␜ߔߎߣߦߥࠆ㧚╙ i ࿁⋡ߩ๭߮಴ߒ. ߩ 2 ಽᏓ㧘 2 ߇ਈ߃ࠄࠇߚߣ߈ߩ. 1. ߩ੐ᓟಽᏓ߇ᐔ. ߦ߅ߌࠆᚲⷐᤨ㑆ࠍ z(+ (i)) ߣߔࠆߣ㧘⋡⊛㑐ᢙߪว⸘. ဋx ¯, ಽᢔ 2 /n ߩᱜⷙಽᏓ㧘หߓߊ. 2. ߩ੐ᓟಽᏓ߇ᐔ. ᚲⷐᤨ㑆ߩᦼᓙ୯. ဋ y¯, ಽᢔ 2 /m ߩᱜⷙಽᏓߦ㧘ߘࠇߙࠇߥࠆߎߣࠍ␜. Ã. T =E. M X. !. ߒߡ޿ࠆ㧚. z(+ (i)). ߎߩ੐ᓟಽᏓߩ߽ߣߢ㧘ᰴߩ⹜ⴕߩ⚿ᨐߩಽᏓࠍ⠨߃. i=1. ࠆ㧚ᰴߩㆬᛯ߇ X ߢ޽ߞߚߣߔࠆߣ㧘୯ x ߩಽᏓߪᱜ. ߢ޽ࠅ㧘ߎࠇࠍᦨዊߦߔࠆࠃ߁ߥᚢ⇛ + ࠍ᳿߼ࠆߎߣ߇. ⷙಽᏓࠍ઒ቯߒߡ޿ࠆ߆ࠄ. ⸃߈ߚ޿໧㗴ߢ޽ࠆ㧚 ਄ㅀߩ໧㗴ߪ Bandit Problem. 6). f (x, ߣ๭߫ࠇࠆ߽ߩߩ. 2, . 1,. ×$. 1. 2. ) = $(. μ. 2 2 , |xi , yj ) 2 1) 2 2. 1,. (x. ¶. ⷗ߪࡌ࡞࠿ࠗ⹜ⴕ㧔⚿ᨐ߇ᚑഞ߆ᄬᢌߩ޿ߕࠇ߆㧕ߩ߽. exp 2$ 2 ߣߥࠆ㧚᰼ߒ޿ߩߪ x ߩಽᏓߛߌߛ߆ࠄ㧘. ߩ߇߶ߣࠎߤߢ㧘ታⴕᤨ⥄േ࠴ࡘ࡯࠾ࡦࠣߦߪ૶߃ߥ޿㧚. 㑐ߒߡⓍಽߒߡ㧘x ߦߟ޿ߡߩ๟ㄝಽᏓࠍ᳞߼ࠆ㧚ߘߩ. ੹࿁ᚒ‫ߪޘ‬ᣢ⍮ߩ⸃ᴺߢ޽ࠆࡌࠗ࠭⛔⸘ߦࠃࠆᦨㆡ⸃ࠍ. ⚿ᨐ N = n + m ߣߒߡ. ৻଀ߣߥߞߡ޿ࠆ㧚ߒ߆ߒ bandit problem ߩᣢሽߩ⍮. μ. ᱜⷙಽᏓߦኻߒߡᢙ୯⸘▚ߢ᳞߼ࠆߎߣߣߒߚ㧚. f (x) . 2. ࡌࠗ࠭⛔⸘ߦࠃࠆᦨㆡ⸃ ࡌࠗ࠭⛔⸘ߦ߅޿ߡߪ㧘⏕₸ࡄ࡜ࡔ࠲ ߇޽ࠆ⏕₸ኒ ᐲ $() ߦᓥߞߡ޿ࠆߣᗐቯߔࠆ㧚᷹ⷰ୯ x ߩ⏕₸ኒᐲ ߪࡄ࡜ࡔ࠲ ߦଐሽߒߡ f (x|) ߩࠃ߁ߥᒻߣߥࠆ㧚ߎ ߎߢ᧦ઙߟ߈ኒᐲߦ㑐ߔࠆࡌࠗ࠭ߩቯℂ. $(|x) =. f (x|)$() P r(x). ¯ )2 n (x x 1+ n+1 V. 1,. 2,. 2 ߦ. ¶(N 1)/2. ߣߥࠆ㧚ߎࠇߪ. xx ¯ n p n + 1 V /(N 2) ߇⥄↱ᐲ N 2 ߩ t ಽᏓ ((N 1)/2) x) = fˆN 2 (ˆ ((N 2)/2) x ˆ=. μ. ¶(N 1)/2. ࠇߡ޿ߚ $() ߪ੐೨⏕₸ኒᐲߣ๭߫ࠇࠆ㧚੐ᓟ⏕₸ኒ. x ˆ2 1 1+ ×p N 2 $(N 2) ߦᓥ߁ߎߣࠍ␜ߒߡ޿ࠆ㧚 ⷐߔࠆߦᰴߩ x ߪ⏕₸ಽᏓ fˆN 2 (ˆ x) ߦᓥ߁ߣℂ⸃ߔࠇ. ᐲߪ㧘੐೨⏕₸ኒᐲ $() ߦ᷹ⷰ࠺࡯࠲ x ߩᖱႎࠍട߃. ߫චಽߢ޽ࠆ߇㧘޿ߊߟ߆ᵈᗧ߇ᔅⷐߢ޽ࠆ㧚߹ߕ㧘ᱜⷙ. ࠆߎߣߦࠃࠅ㧘᷹ⷰ࠺࡯࠲ࠍࠃࠅࠃߊ⺑᣿ߔࠆࡄ࡜ࡔ࠲. ಽᏓࠍ઒ቯߒߚߩߦ x ߪᱜⷙಽᏓߦᓥࠊߥ޿߇㧘ߎࠇߪ. ߩಽᏓࠍᓧߚ߽ߩߣ⠨߃ࠆߎߣ߇ߢ߈ࠆ㧚. ߎߎߢ⼏⺰ࠍߒߡ޿ߡ߽ᆎ߹ࠄߥ޿໧㗴ࠄߒ޿㧚ಽᏓߩᒻ. 2.1 ࡌࠗ࠭⛔⸘ߦࠃࠆ⏕₸ಽᏓߩផቯ. ߪᱜⷙಽᏓߩࠃ߁ߥ㊒㏹ဳߢ޽ࠅ㧘N ߇ᄢ߈ߊߥࠆߣᕆ. ࠍ↪޿ࠆߣ㧘᷹ⷰ࠺࡯࠲ x ߆ࠄ㧘⏕₸ࡄ࡜ࡔ࠲ ߦ㑐ߔ ࠆᣂߒ޿⏕₸ኒᐲ $(|x) ߇ᓧࠄࠇࠆ㧚ߎߩᣂߒ޿⏕₸ኒ ᐲ $(|x) ߪ੐ᓟ⏕₸ኒᐲߣ๭߫ࠇ㧘ߘࠇߦኻߒߡ઒ቯߐ. ੐೨⏕₸ኒᐲߣߒߡ㧘ᧄⓂߢߪᱜⷙಽᏓߦኻߔࠆᮡḰ. $(. 1,. 2, . 2. ㅦߦᱜⷙಽᏓߦㄭߠߊߩߢ㧘ࠃ޿ߣߒࠃ߁㧚߹ߚ㧘N = 3 ߩߣ߈㧘ߟ߹ࠅ 4 ࿁⋡ߩ⹜ⴕߩ೨ߦߪ㧘⥄↱ᐲ 1 ߩ t ಽ. ⊛ߥήᖱႎ੐೨ಽᏓ㧔Ṽὼ੐೨ಽᏓߣ߽޿߁㧕ߢ޽ࠆ. ) = 2. Ꮣ㧘ߔߥࠊߜ Cauchy ಽᏓߣߥࠅ㧘᦭㒢ߩᐔဋ୯ࠍᜬߚ. ࠍ↪޿ࠆ㧚⹜ⴕߦ߅޿ߡ X ࠍ n ࿁ㆬᛯߒߡታⴕᤨ㑆. ߥ޿㧚ߎߩߚ߼㧘ࡌࠗ࠭⛔⸘ߢߪ 4 ࿁⋡ߩ⹜ⴕߢߤ߁ߒ. −14−.

(3) ߚࠄࠃ޿߆㧘૗ߩᜰ㊎߽ᓧࠄࠇߥ޿㧚ߎࠇߦኻߒᓟㅀߩ. ˆ (n,m) (&) W 1. ¡. ࠃ߁ߦ㧘ታ㛎⊛ߦߪ 4 ࿁⋡ߦᐔဋᚲⷐᤨ㑆߇⍴߆ߞߚ߶ ߁ࠍㆬᛯߔࠆߩ߇ࠃ޿ࠃ߁ߢ޽ࠆ㧚ߥ߅㧘ᦨೋߩ 2 ࿁߹. ˆ (n,m) (&) & W 2. ¡. ߢߪ૗ߩᖱႎ߽ߥ޿ߩߢ㧘X ߣ Y ࠍߘࠇߙࠇ 1 ࿁ߕߟ. ¢. ˆ (n,m+1) (&2 ), W ˆ (n,m+1) (&2 )} = E '2 min{W 1 2. ታⴕߔࠆߩ߇ᦨㆡߢ޽ࠅ㧘3 ࿁⋡ߢߪ߹ߛಽᢔߩᖱႎ߇ ᓧࠄࠇߡ޿ߥ޿ߩߢ㧘X ߣ Y ߩㅦ߆ߞߚᣇࠍ߽߁৻ᐲታ. ¢. ˆ (n+1,m) (&1 ), W ˆ (n+1,m) (&1 )} = E '1 min{W 1 2. ߣߥࠆ㧚ߎߎߢ. ⴕߔࠆߩ߇ᦨㆡߢ޽ࠆ㧚. '1 =. 2.2 ࡌࠗ࠭⛔⸘ߦࠃࠆᦨㆡᚢ⇛. V0 = V. r. x ˆ2 + N 2 N 1. ࡌࠗ࠭⛔⸘ߦࠃࠆᦨㆡᚢ⇛ߪ㧘޿ࠊࠁࠆേ⊛⸘↹ᴺߢ ⹜ⴕߩߚ߼ߦᖱႎࠍ㓸߼ࠆᗧ๧ߪ߹ߞߚߊߥ޿߆ࠄ㧘ߘ. r. 0. ᳞߼ࠆ㧚߹ߕ㧘ᦨᓟߩ⹜ⴕ㧔M ࿁⋡㧕ߢߪ㧘ߘࠇએ㒠ߩ. &1 =. y¯ x ¯ = V0. x ˆ. & p. N 1 r N 2. n(n + 1). ߇᣿ࠄ߆ߦᦨㆡߢ޽ࠆ㧚ߔߥࠊߜ㧘ᦨᓟߩ⹜ⴕߦ߅ߌࠆ. x ˆ2 N 2 ߢ޽ࠅ㧘'2 ߣ &2 ߪ x ˆ ߣ n ߩߣߎࠈߦ yˆ ߣ m ࠍߘࠇߙ. ᚲⷐᤨ㑆ߩᦼᓙ୯ߪ min{¯ x, y¯} ߣߥࠆ㧚. ࠇઍ౉ߒߚ߽ߩߣߥࠆ㧚. ࠇ߹ߢߩ⹜ⴕߢߩᐔဋታⴕᤨ㑆߇⍴޿߶߁ࠍㆬᛯߔࠆߩ. 1+. ᰴߦ㧘ᦨᓟ߆ࠄ 2 ࿁⋡㧔M 1 ࿁⋡㧕ߩ⹜ⴕߦߟ޿ߡ. ˆ (n,m) , W ˆ (n,m) ߪ ߎߩࠃ߁ߦ㧘n, m ࠍ࿕ቯߔࠇ߫ W 1 2. ⠨߃ࠆ㧚ߎߎߢ߽ߒ X ࠍㆬᛯߒߡ㧘M 1 ࿁⋡ߩᚲⷐ. & ࠍࡄ࡜ࡔ࠲ߣߔࠆ৻ᄌᢙ㑐ᢙߣߥࠆ㧚ߘߎߢ㧘ߎࠇࠄ. ᤨ㑆߇ x ߣߥࠆߣߔࠆ㧚M 2 ࿁⋡߹ߢߦ X ߇ n ࿁ㆬ. ߩ㑐ᢙࠍ㧘ᢙ୯⊛ߦ⸘▚ߒߚ୯߆ࠄ㧘඙ಽ⊛ᄙ㗄ᑼߢㄭ. ᛯߐࠇߡ޿ߡ㧘ߘߩᐔဋᚲⷐᤨ㑆ࠍ x ¯ ߣߔࠆߣ㧘ᣂߚߦ. ૃߔࠆߎߣߣߒߚ㧚ㆡᒰߥࠨࡦࡊ࡞ὐ߆ࠄࠬ࠲࡯࠻ߒߡ㧘. ¯0 ߪ ᓧࠄࠇࠆᐔဋᚲⷐᤨ㑆 x. ฦ඙㑆ߩਛᄩߢߩ⛘ኻ⺋Ꮕ߇ 1010 એ਄ߢ޽ࠇ߫ࠨࡦࡊ. n¯ x+x n+1. ࡞ὐࠍჇടߐߖࠆߎߣߦࠃࠅ㧘ㆡᔕ⊛ߦㄭૃࠍⴕߞߚ㧚ࠨ. x ¯0 =. ࡦࡊ࡞ὐߩᢙߪ㧘10 ᰴߩᄙ㗄ᑼࠍ↪޿ࠆߣ 50 ߆ࠄ 100 0. ߣߥࠆ㧚M ࿁⋡ߩ⹜ⴕߩᚲⷐᤨ㑆ߪ min{¯ x , y¯} ߢ޽ߞ. ⒟ᐲߢᓧࠄࠇࠆߎߣ߇ᄙ޿㧚. ߚ߆ࠄ㧘M 1 ࿁⋡ߦ X ࠍㆬᛯߒߚ႐วߩ㧘ᦨᓟߩ 2. X ߣ Y ߩ┙႐ࠍ౉ࠇᦧ߃ࠆߎߣߦࠃࠅ㧘. ࿁ߩว⸘ᚲⷐᤨ㑆ߩᦼᓙ୯ߪ. ˆ (n,m) (&) = W ˆ (m,n) (&) (M N )& W 1 2. W1 = E(x + min{¯ x0 , y¯}). ˆ (n,m) ߣ ߣ޿߁ኻ⒓ᕈ߇ᓧࠄࠇࠆ㧚ߎࠇߦၮߠ߈㧘W 1 (m,n) ˆ W ࠍࡍࠕߦߒߡ⸘▚㊂ࠍඨᷫߐߖࠆ㧚߹ߚ㧘&

(4). ߢ⴫ߐࠇࠆ㧚M 1 ࿁⋡ߦ Y ࠍㆬࠎߛ႐ว߽ห᭽ߦ 0. W2 = E(y + min{¯ x, y¯ }). 2. ߣߥࠆ߆ࠄ㧘M 1 ࿁⋡ߩㆬᛯߣߒߡߪ W1 W2 ߥࠄ. ˆ (n,m) (&)

(5) 0 ߅ࠃ߮ W ˆ (m,n) (&) &

(6) 0 ߣ ߦ߅޿ߡ W 1 2. X ࠍ㧘ߘ߁ߢߥߌࠇ߫ Y ࠍㆬᛯߔࠆߩ߇ࠃ޿㧘ߣ޿߁ߎ. ߥࠆߎߣ߇ࠊ߆ࠆߩߢ㧘ᖱႎ⪭ߜࠍᦨዊ㒢ߦߔࠆߚ߼ታ ˆ (n,m) (&) ߣ W ˆ (m,n) (&) & ࠍ & > 0 ߦኻߒ⸘ 㓙ߦߪ W. ߣߦߥࠆ㧚. 1. ห᭽ߦ X ࠍ n ࿁㧘Y ࠍ m ࿁ታⴕߒߚᓟߩ n + m + 1 ࿁⋡ߩㆬᛯߪ㧘 (n,m). W1. (n,m) W2. ³. (n+1,m). = E x + min{W1. ³. =E y+. (n+1,m). , W2. ´. 2. ˆ1 ߪ ᦼᓙ୯ߩ⸘▚ߪⓍಽߢ޽ࠅ㧘଀߃߫ W. }. Z. ´. ˆ 1 (&1 (ˆ ˆ 2 (&1 (ˆ '(ˆ x) min{W x)), W x))}fˆN 2 (ˆ x)dˆ x. (n,m+1) (n,m+1) min{W1 , W2 }. . ࠍ⸘▚ߒ㧘W1 ߣ W2 ߩᄢዊᲧセߢ X ߆ Y ߩ޿ߕࠇ߆ ࠍㆬᛯߔࠆߣ޿߁ߎߣߦߥࠆ㧚. 2.3 ᦨㆡᚢ⇛ߩᢙ୯⸘▚ ߐߡ㧘਄⸥ߦࠃࠅ W1 ߣ W2 ࠍ⸘▚ߔࠇ߫ࠃ޿ߎߣ߇ (n,m). ಽ߆ߞߚ߇㧘W1. (n+1,m) W2. (n+1,m). ߪx ¯, y¯, V , n, m, ߅ࠃ߮ W1. ,. ߦଐሽߒߡ޿ࠆ㧚ߎߎߢ. r. V , N 2 ߣ߅߈㧘ߐࠄߦ V =. &=. ⴫ߔߎߣ߇ߢ߈ࠆ㧚ౕ૕⊛ߦߪ. ˆ 2 (&2 ) ߩᄢዊߪᲧセ⊛න⚐ߢ㧘W ˆ 1 (&S ) = W ˆ 2 (&S ) ߣ ߣW ˆ ߥࠆࠃ߁ߥ &S ߇ሽ࿷ߒ㧘&1 > &S ߢߪ W1 ߇㧘&1 < &S ˆ 2 ߇ㆬᛯߐࠇࠆ㧔ߎߩᕈ⾰ߪ⸃ᨆ⊛ߦߪᧂ⏕⹺ߛ ߢߪ W x) = &S ߣߥࠆ x ˆ ߢಽഀߐࠇࠆ㧚 ᓥߞߡⓍಽ㗔ၞߪ &1 (ˆ ࿑ 1 ߪ &1 ߦߟ޿ߡ㧘ㆡᒰߦㆬࠎߛ N = 10 ߣ n = 4 ߦ. ˆ ߩ㑐ᢙߣߒߡࡊࡠ࠶࠻ߒߚ߽ߩߢ޽ࠆ㧚&1 ߪ ߅޿ߡ x. (M N )¯ x V (n,m) (M N )¯ x ˆ (n,m) = W2 W 2 V ˆ (n,m) ߪ &, n, m, W ˆ (n+1,m) , W ˆ (n+1,m) ߢ ߣߔࠆߣ㧘W 1 1 2 ˆ (n,m) = W 1. ߣߥࠆ㧚ߎߎߢ min ߇฽߹ࠇࠆߩߢ㧘ߤߜࠄ߇ㆬ߫ࠇࠆ߆ ˆ 1 (&1 ) ߦᔕߓߡⓍಽ㗔ၞࠍಽഀߒߥߌࠇ߫ߥࠄߥ޿㧚ᐘ޿ W. ߇㧘⋥ᗵ⊛ߦߪ᣿ࠄ߆㧕㧚. y¯ x ¯ V. (n,m) W1. 2. ˆ (n,m) ߽ ▚࡮ㄭૃߒߡ޿ࠆ㧚ߥ߅㧘ዋߒ⸘▚ࠍߔࠆߣ W 1 (n,m) ˆ W & ߽ㅪ⛯ߢන⺞Ⴧടߥ㑐ᢙߢ޽ࠆߎߣ߇ಽ߆ࠆ㧚. & = 0 ߢߪන⺞ᷫዋߥ㑐ᢙߢ޽ࠆ߇㧘& > 0 ߢߪ x ˆ<0 ߢᭂᄢ୯㧘& < 0 ߢߪ x ˆ > 0 ߢᭂዊ୯ࠍขࠅ㧘x ˆ

(7) ± ߢߪ & ߦࠃࠄߥ޿৻ቯ୯ߦㄭߠߊ㧚. ˆ

(8) ࿑ 1 ߩ႐ว㧘x ߢߩᭂ㒢୯߇ . p. p. ߢߩᭂ㒢୯߇. p. 63/40 ߣߥߞߡ޿ࠆ㧚ߘߎߢߎߩ႐ว. −15−. 9/20, x ˆ

(9). 9/20 ߢ㧘& = 1 ߩ႐วߩᭂᄢ୯߇.

(10) ㄭૃࠍ᭴▽ߔߴ߈ߢ޽ࠈ߁߇㧘M ߇ᄢ߈ߊߥࠆߣਇㅪ⛯. ࿑1 x ˆ ߣ &1 ߣߩ㑐ଥ (N = 10, n = 4). ὐߩᢙ߇㕖Ᏹߦᄙߊߥߞߡߒ߹߁㧚 ˆ 1 (&), W ˆ 2 (&) ߩࡄ࡜ࡔ࠲ & ߩ▸࿐ߪታᢙ ߹ߚ㧘㑐ᢙ W ో૕ࠍขࠅᓧࠆ㧚ߒ߆ߒ޽߹ࠅ & ߇ᄢ߈ߊߥࠆߣ㧘ਣ߼ ⺋Ꮕߩߖ޿߆㧘㑐ᢙߩㅪ⛯ᕈ߇ᖡߊߥߞߡߒ߹ߞߚ㧚ߘ ߎߢ੹࿁ߪ ±1000 ࠃࠅᄖߪⓍಽߒߥ޿ߎߣߦߒߡ޿ࠆ㧚 ᰴߩ⸘▚ߢዋߒᄖ஥߹ߢᔅⷐߦߥߞߡߒ߹߁ߩߢ㧘ߘߩ ㇱಽߪ‫⵬ޟ‬ᄖ‫ࠆ޿ߡߞߥߣޠ‬㧚 ߘ߽ߘ߽ߩ t ಽᏓߩኒᐲ㑐ᢙߩ⸘▚ߪ N ߇ᄢ߈޿ߣ ᖱႎ⪭ߜࠍ⿠ߎߒߡߒ߹߁㧔੹࿁⸘▚ߒߚ▸࿐ߢߪ߹ߛ ໧㗴ߢߪߥ޿㧕ߒ㧘ᢙ୯Ⓧಽߩ቟ቯᕈ߽߹ߛᬌ⸛ߩ૛࿾ ߇޽ࠆࠃ߁ߦᕁࠊࠇࠆ㧚. (1) (2). &S . p. p. 9/20 < &S <. p. . p. &S . p. ⴫ 1 ߪ㧘ᢙ୯⸘▚ߩ⚿ᨐᓧࠄࠇߚᦨㆡᚢ⇛ࠍ␜ߒߡ޿ ࠆ㧚ߎࠇࠄߪ 2.3 ▵ߩ &S ߦ⋧ᒰߒ㧘ฦ n, m ߦ߅޿ߡ㧘. p. 9/20 < &S 9/20 ߢ޽ࠇ߫㧘 ߆ࠄ޽ ˆ 1 ߩ▸࿐㧘ᱷࠅ ˆ2 ߹ߢ߇ W ࠆߣߎࠈ߹ߢ߇ W. ߩ▸࿐ߣߥࠆ㧚. (4). 3.1 ᓧࠄࠇߚᚢ⇛. 63/40 ߢ޽ࠇ߫㧘ᭂᄢ୯ߩઃㄭ ˆ 1 ߇ㆬᛯߐࠇ㧘ߘߩ ߩ᦭㒢ߩ▸࿐ߩߺߦ߅޿ߡ W ˆ 2 ߇ㆬᛯߐࠇࠆ㧚 ਔ஥ߩ 2 ߟߩඨή㒢㗔ၞߢ W. (3). 3. ⚿ᨐߣߘߩ⹏ଔ. ˆ 2 ߇ㆬᛯߐࠇࠆ㧚 63/40 ߢ޽ࠇ߫㧘Ᏹߦ W. ˆ 1 ߇ㆬᛯߐࠇࠆ㧚 9/20 ߢ޽ࠇ߫㧘Ᏹߦ W. &= p. y¯ x ¯. V /(N 2) ߇⴫ߦ␜ߒߚᢙࠃࠅ߽ᄢ߈ߌࠇ߫ X ࠍㆬᛯߒ㧘ߘ߁ߢߥ ߌࠇ߫ Y ࠍㆬᛯߔࠆߎߣࠍᗧ๧ߔࠆ㧚ߒߚ߇ߞߡ㧘ߎߩ. & < 0 ߩ႐วߦߪᭂዊ୯ߦኻߒߡ (2) ߦ㘃ૃߒߚ႐ว߇. ୯߇ 0 ߩ႐วߦߪනߦߘࠇ߹ߢߩᐔဋታⴕᤨ㑆߇ㅦ޿߶. ⊒↢ߔࠆߩߢ㧘Ⓧಽ▸࿐ߩಽഀߪోㇱߢ 5 ㅢࠅ޽ࠆߎߣ. ߁ࠍㆬᛯߔࠆ㧚೨ㅀߩㅢࠅ a ߪ 0 ߇ㆡᒰߢ޽ࠅ㧘b ߪࡌ. ߦߥࠆ㧚. ࠗ࠭⛔⸘ߢߪ᳿߼ࠄࠇߥ޿߇㧘ታ㛎⊛ߦߪ 0 ߢࠃ޿㧚ᧄ. ᦼᓙ୯ߩ⸘▚ߪή㒢㗔ၞߢߩⓍಽߣߥࠆ߇㧘ⵍⓍಽ㑐. ᧪ߪฝਅᣇะߦ߽߁৻Ბ㧔ᦨᓟߩ 1 ࿁ߦኻᔕߔࠆ㧕޽ࠆ. ᢙ߇඙ಽ⊛ᄙ㗄ᑼߣߥߞߡ޿ࠆߩߢ㧘ฦ඙ಽߦኻᔕߔࠆ. ߴ߈ߢ㧘ߘߎߪߔߴߡ 0 ߇౉ࠆ㧚X ߣ Y ߦ㑐ߔࠆኻ⒓. 㗔ၞߏߣߦⓍಽࠍಽഀߒߚ㧔ߎࠇߦࠃࠅⓍಽߩࡊࡠࠣ࡜. ᕈ߆ࠄ㧘⴫ߪ෻ኻ⒓ߣߥࠆ㧚⴫ߪ M = 10 ߩ႐วߢ޽ࠆ. ࡒࡦࠣߪᢙච୚ᄢᄌߦߥࠆ㧕㧚ඨή㒢㗔ၞߩⓍಽߪ DE. ߇㧘M ߦࠃߞߡ⴫ߩ୯ߪหߓ n, m ߢ߽⋧ᒰߦ㆑߁㧚. ౏ᑼ㧔ᢥ₂ 7) ߩ (11.21) ᑼ㧕ߦࠃߞߡ޿ࠆ㧚᦭㒢㗔ၞߢ ⴫ 1 ࡌࠗ࠭⛔⸘ߦࠃࠆᦨㆡᚢ⇛ (M = 10). ߽㕖Ᏹߦᐢ޿႐ว߇޽ࠅ㧘Gauss ౏ᑼߥߤߢߪ߁߹ߊ෼ ᧤ߒߥ޿ߩߢ㧘Ᏹᓸಽᣇ⒟ᑼߩೋᦼ୯໧㗴ߩㆡᔕೞߺࠍ ↪޿ࠆߎߣߦߒ㧘Verner ߩ 6 ᰴ౏ᑼ㧔ᢥ₂ 8) ߩ Table. 5.4㧕ࠍ↪޿ߚ㧚Ⓧಽߩ♖ᐲߪ⋧ኻ♖ᐲߢ 1012 ߹ߚߪ⛘ ኻ♖ᐲߢ 1016 ߦ⸳ቯߒߚ㧚 ߎߎߢ⸘▚㊂ߦߟ޿ߡࠦࡔࡦ࠻ߒߚ޿߇㧘਄⸥ߩㅢࠅ ㆡᔕ⊛ߥ㑐ᢙㄭૃߣᢙ୯Ⓧಽࠍ↪޿ߡ޿ࠆߚ߼㧘ᓧࠄࠇ. m\n 1 2 3 4 5 6 7. 1 a -b -0.67 -0.54 -0.46 -0.36 -0.22. 2 b 0.00 -0.15 -0.18 -0.16 -0.11. 3 0.67 0.15 0.00 -0.05 -0.05. 4 0.54 0.18 0.05 0.00. 5 0.46 0.16 0.05. 6 0.36 0.11. 7 0.22. ࠆ㑐ᢙߩᕈ⾰ߦࠃߞߡ⸘▚㊂߇⋧ᒰߦ⇣ߥߞߡߒ߹߁㧚⹤ ࠍ߁ࠎߣ◲නߦߒߡ㧘ߎࠇࠄߩ⸘▚㊂߇৻ቯߢ޽ࠆߣߔ ࠆߣ㧘Ⓧಽ࡮㑐ᢙㄭૃࠍታⴕߔࠆ࿁ᢙ O(M 2 ) ߇⸘▚㊂. Ყセߩߚ߼ߦ㧘ᢥ₂ 4) ߢ⪺⠪߇⊒⴫ߒߚᚻᴺࠍหߓ. ߣ޿߁ߎߣߦߥࠆ㧚ታ㓙ߦߪ Pentium M 2.0GHz ߩࡑ. ᒻᑼߢ⴫␜ߒߡߺࠆߣ⴫ 2 ߩࠃ߁ߦߥࠆ㧚ߎߩᚻᴺߢ. ࠪࡦߢ M = 10 ߩ⸘▚ߪ⚂ 3 ಽߢᷣ߻߇㧘M = 50 ߢ. ߪᚢ⇛ߪ max{n, m} ߩߺߢ᳿߹ࠆࠃ߁ߦߥߞߡ߅ࠅ㧘. ߪ⚂ 80 ಽ߆߆ߞߡ޿ࠆ㧚. max{n, m} M/6 ߣߥࠆ⴫ߩ▸࿐ߪẋㄭ⸃ᨆߦࠃࠅߔ ߴߡ 0 ߣߥࠆߎߣ߇ಽ߆ߞߡ޿ࠆ㧚. 2.4 ᱷߞߡ޿ࠆ⺖㗴. (n,m). ਄⸥ߩ⴫ࠍ &S. એ਄ߩࠃ߁ߥᣇᴺߦࠃࠅ㧘৻ᔕߩᢙ୯⸘▚߇น⢻ߣߥߞ. ߦᩰ⚊ߒߚߣߔࠆߣ㧘਄⸥ߩᚢ⇛ߦ. ၮߠߊታⴕᤨ⥄േ࠴ࡘ࡯࠾ࡦࠣߩࡊࡠࠣ࡜ࡓߪ⴫ 3 ߩࠃ. ߚ㧚ߒ߆ߒ޿ߊߟ߆໧㗴߇ᱷߞߡ޿ࠆ㧚 ˆ 1, W ˆ 2 ߪ㧔㜞㓏㧕ᓸಽ߇ਇㅪ⛯ߥὐ߇ሽ ߹ߕ㧘㑐ᢙ W. ߁ߦߥࠆ㧚ߎߎߢ㑐ᢙ ExecX(), ExecY () ߪㆬᛯ⢇ X,. ࿷ߔࠆ㧚਄⸥ߩㆡᔕ⊛ㄭૃࠍⴕ߁ߣ㧘ߎߩࠃ߁ߥਇㅪ⛯. Y ߩታⴕߢ㧘ᚲⷐᤨ㑆ࠍ㄰ߔߣߔࠆ㧚. ὐߩ߹ࠊࠅߢߪ㕖Ᏹߦᄙߊߩࠨࡦࡊ࡞ὐ㧔200 ⒟ᐲ㧕߇. 3.2 ᓧࠄࠇߚᚢ⇛ߦࠃࠆᚲⷐᤨ㑆ߩᲧセ. ขࠄࠇࠆ߇㧘৻ᔕⷐ᳞♖ᐲࠍḩߚߔㄭૃ߇ᓧࠄࠇࠆࠃ߁. ਄ㅀߩ 2 ߟߩᚢ⇛ࠍ↪޿ߚߣ߈ߩᚲⷐᤨ㑆ߩᲧセࠍ࿑. ߢ޽ࠆ㧚ਇㅪ⛯ߥὐߢ㗔ၞࠍಾߞߡ㧘ߘࠇߙࠇߩ㗔ၞߢ. 2 ߦ␜ߔ㧚࿑ߩ❑ゲߪ Y ߩ⹜ⴕ࿁ᢙߩᐔဋ୯ࠍࡕࡦ࠹ࠞ. −16−.

(11) m\n 1 2 3 4 5 6 7. ⴫ 1 0.00 -0.62 -0.62 -0.62 -0.62 -0.62 -0.62. 2 ᢥ₂ 2 0.62 0.00 0.00 0.00 0.00 0.00. 4) ߦࠃࠆᚢ⇛ (M = 10) 3 4 5 6 0.62 0.62 0.62 0.62 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00. ࿑ 2 Y ߩ⹜ⴕ࿁ᢙߣ &0 ߩ㑐ଥ (M = 10). 7 0.62. x = ExecX(); //1 ࿁⋡ y = ExecY (); //2 ࿁⋡ n = m = 1; if (y > x) { z = ExecX(); //3 ࿁⋡ v = (x z)2 /2; x = (x + z)/2; n = 2; } else { z = ExecY (); //3 ࿁⋡ v = (y z)2 /2; y = (y + z)/2; m = 2; }. ߢ޽ࠆ㧚ߎࠇߪᗧᄖߥ⚿ᨐߛ߇㧘࠯ࡠᚢ⇛ߪᕈ⢻Ꮕ &0 ߇ ᄢ߈޿ߣߎࠈߢ᦭೑ߥߩߪਇᕁ⼏ߢߪߥ޿ߩߢ㧘ℂ⸃ߢ ߈ߥ޿⚿ᨐߢߪߥ޿㧚 ࿑ 3 Y ߩ⹜ⴕ࿁ᢙߣ &0 ߩ㑐ଥ (M = 24). while (n + m < M ) //n + m + 1 ࿁⋡ (n,m). if (y x > &S. p. v/(N 2)) {. z = ExecX(); v+ = (x z)2 n/(n + 1); x = (nx + z)/(n + 1); n = n + 1; } else { z = ExecY (); v+ = (y z)2 m/(m + 1); y = (my + z)/(m + 1); m = m + 1; } ⴫ 3 ታⴕᤨ⥄േ࠴ࡘ࡯࠾ࡦࠣߩࡊࡠࠣ࡜ࡓࠬࠠ࡯ࡑ ࿑ 4 Y ߩ⹜ⴕ࿁ᢙߣ &0 ߩ㑐ଥ (M = 50). ࡞ࡠᴺߦࠃࠅ⹏ଔߒߚ߽ߩ㧘ᮮゲߪ & ߩ‫⌀ޟ‬୯‫ࠆ޽ߢޠ‬. &0 =. 2. 2. 1. ߢ޽ࠆ㧚࿑ߢߪ &0 ߇ᱜߩ▸࿐ࠍ␜ߒߡ޿ࠆߩߢ㧘Y ߩ ⹜ⴕ࿁ᢙߪዋߥ޿߶ߤࠃ޿㧚߹ߚ㧘࿑ߦߪ฽߹ࠇߥ޿߇㧘. &0 = 0 ߢߪᒰὼ M/2 = 5 ߦߥࠆ㧚ࡌࠗ࠭⛔⸘ߦࠃࠆ ᚢ⇛ߩ⚿ᨐߪ Bayes10, ᢥ₂ 4) ߩᚢ⇛ߩ⚿ᨐߪ Suda10 ߣߒߡ␜ߒߡ޽ࠆ㧚ߐࠄߦ㧘⴫ߩߔߴߡࠍ 0 ߣߒߚ႐ว 㧔ߔߥࠊߜ㧘ߘࠇ߹ߢߩᐔဋታⴕᤨ㑆ߩ⍴޿߶߁ࠍㆬᛯߔ ࠆᚢ⇛㧦એਅ ࠯ࡠᚢ⇛ߣ๭߱㧕ࠍ Zero10 ߣߒߡട߃ߚ㧚 ߘࠇߙࠇߩᚢ⇛ߪ㕖Ᏹߦᄢ߈ߊ⇣ߥࠆߦ߽㑐ࠊࠄߕ㧘⚿ ᨐߪࠣ࡜ࡈߢߪ඙೎߇ߟ߆ߥ޿߶ߤࠃߊૃߡ߅ࠅ㧘ᢙ୯ ⊛ߦ߽ 0.01 ߩࠝ࡯࠳࡯ߢߒ߆㆑ࠊߥ޿㧚. M = 50 ߩ࿑ 4 ࠍ⷗ࠆߣ㧘࠯ࡠᚢ⇛ߪ &0 ߇ዊߐ޿ߣ. ߒ߆ߒ࿑ 3 ߦ⷗ࠆࠃ߁ߦ㧘M = 24 ߢߪߪߞ߈ࠅߣࡌ ࠗ࠭⛔⸘ߩ߶߁߇ࠃ޿ߎߣ߇ಽ߆ࠆ㧚ߎߩࠨࠗ࠭ߢߪ &0. ߎࠈߢઁߩ 2 ᚻᴺߦᲧߴߡᄢ߈ߊഠࠆߎߣ߇᣿⊕ߢ޽ࠆ㧚. ߇ᄢ߈޿ߣߎࠈߢ㧘ᢥ₂ 4) ߩᚢ⇛ߪ ࠯ࡠᚢ⇛ࠃࠅ߽ᖡߊ. ᢥ₂ 4) ߩᚢ⇛ߪ &0 ߇ዊߐ޿ߣߎࠈ㧘ᄢ߈޿ߣߎࠈߢߪ. ߥߞߡ޿ࠆ㧚ታߪࡌࠗ࠭⛔⸘ߦࠃࠆᚢ⇛ߢ޽ࠆ Bayes24. ࡌࠗ࠭⛔⸘ߦࠃࠆᚢ⇛ߦㄭߠߊ߇㧘&0 1 ޽ߚࠅ߆ࠄ. ߽ &0 2.4 ߢߪ ࠯ࡠᚢ⇛ࠃࠅ߽ߏߊࠊߕ߆ߥ߇ࠄᖡߊ. ߒ߫ࠄߊߪ᳓ࠍ޽ߌࠄࠇߡ޿ࠆ㧚ߒ߆ߒ㧘ࡌࠗ࠭⛔⸘ߢ. ߥࠆ㧚ߒ߆߽㧘M = 10 ߢ߽ M = 50㧔࿑ 4㧕ߢ߽ห᭽. M = 50 ߩᦨㆡᚢ⇛ࠍ⸘▚ߔࠆߩߦ 1 ᤨ㑆એ਄߆߆ࠆߩ. −17−.

(12) ߦኻߒߡ㧘ᢥ₂ 4) ߩᚢ⇛ߪ৻⍍ߢ⸘▚߇⚳ࠊࠆߩߢ㧘ᔕ. 4. ߅ ࠊ ࠅ ߦ. ↪ߩ႐㕙ߦࠃߞߡߪᢥ₂ 4) ߩᚻᴺ߇ᦸ߹ߒ޿႐ว߽ߢߡ. ᧄⓂߢߪ㧘ᚲⷐᤨ㑆߇౒ㅢߥಽᢔࠍ߽ߟᱜⷙಽᏓߦᓥ. ߊࠆน⢻ᕈ߇޽ࠆ㧚 ⴫ 1 ߢ␜ߒߚࡌࠗ࠭⛔⸘ߦࠃࠆᚢ⇛ (M = 10) ߦ߅޿. ߁ 2 ߟߩታⵝࠍታⴕᤨߦㆬᛯߔࠆㅙᰴታ㛎⸘↹ߦߟ޿ߡ㧘. ߡ㧘b ߩߣߎࠈߦ⴫ 2 ߦ␜ߒߚᢥ₂ 4) ߩᚢ⇛ߩ୯ߢ޽ࠆ. ࡌࠗ࠭⛔⸘ߦၮߠߊᦨㆡᚢ⇛ߩᢙ୯⸘▚ߣ㧘ߘߩࡕࡦ࠹. 0.62 ࠍ౉ࠇߡߺࠆߣ㧘ᦨᄢߢ 0.025 ࿁߶ߤ Y ߩ⹜ⴕ࿁ᢙ. ࠞ࡞ࡠᴺߦࠃࠆ⹏ଔࠍⴕߞߚ㧚ߘߩ⚿ᨐ㧘ᢥ₂ 4) ߢ⪺⠪. ߇Ⴧടߔࠆ㧚⴫ 1 ߩ 1 ⴕ⋡ߩ୯ߩ௑ะࠍ⷗ࠆߣ b = 0.62. ߇ឭ᩺ߒߚᚻᴺ߿㧘ᐔဋታⴕᤨ㑆߇ㅦ޿߶߁ࠍන⚐ߦㆬ. ߪ߻ߒࠈዊߐߔ߉ࠆࠃ߁ߦ⷗߃ࠆߣߎࠈ߆ࠄߔࠆߣ㧘ߎ. ᛯߔࠆ ࠯ࡠᚢ⇛ߦᲧߴ㧘ࡌࠗ࠭⛔⸘ߦၮߠߊᚢ⇛߇ఝࠇ. ࠇߪᗧᄖߥ⚿ᨐߢ޽ࠆ㧚ߒ߆ߒ㧘ࠊߕ߆ 2 ࿁ߩ⹜ⴕ߆ࠄ. ߡ޿ࠆߎߣ߇ࠊ߆ߞߚ㧚߹ߚ㧘ᐔဋ 1 ߩࡐࠕ࠰ࡦಽᏓߦ. ಽᢔࠍផቯߔࠆߎߣߦߪήℂ߇޽ࠆߩߢ㧘⚻㛎⊛ߦㆃ޿. ߎࠇࠄߩᚢ⇛ࠍㆡ↪ߒߚߣߎࠈ㧘ᱜⷙಽᏓࠃࠅ߽߿߿ᕈ. ᣇࠍㆬᛯߔࠆߎߣߦวℂ⊛ߥℂ↱߇ߥ޿ߣ߽⠨߃ࠄࠇࠆ㧚. ⢻߇ૐਅߔࠆ߽ߩߩ㧘௑ะߣߒߡߪᱜⷙಽᏓߩ႐วߣห. ߔࠆߣ㧘b = 0 ߪᱜᒰߥㆬᛯ߆߽ߒࠇߥ޿㧚. ᭽ߥ߽ߩ߇ᓧࠄࠇߚ㧚. 3.3 ᱜⷙಽᏓએᄖߩ႐ว߳ߩㆡ↪. ࡌࠗ࠭⛔⸘ߦၮߠߊᚢ⇛ߪ੹࿁ߩ⹏ଔߢߪఝࠇߚ⚿ᨐ ࠍዉ޿ߚ߇㧘ઁߦ߽ minimax ᚢ⇛6) ߥߤ߇⍮ࠄࠇߡ߅. ᦨᓟߦ㧘਄ㅀߩࠃ߁ߦᱜⷙಽᏓࠍ઒ቯߒߡᓧࠄࠇߚᚢ. ࠅ㧘ߐࠄߦᲧセ⎇ⓥߩ૛࿾߇޽ࠆ㧚߹ߚᢙ୯⸘▚ߩᚻᴺ. ⇛ࠍߘߩ߹߹↪޿ߡ㧘ᚲⷐᤨ㑆߇ࡐࠕ࠰ࡦಽᏓ x. P r(x = k) =. x!. e. ߦ߽ታⵝߦ߽ᡷ⦟ߩ૛࿾߇޽ࠆ㧚ߒ߆ߒขࠅ਄ߍߚ໧㗴. k ߪ㕖⽶ᢛᢙ. ߇߭ߣߟߛߌߥߩߢ㧘੹ᓟߪ⇣ߥࠆ໧㗴⸳ቯߩ႐วߦߟ. 㧔 = 1 ߣߒߚ㧕ߦᓥ߁႐วߦߟ޿ߡ㧘ห᭽ߦࡕࡦ࠹ࠞ࡞. ޿ߡ⠨ኤࠍㅴ߼ࠆᔅⷐ߇޽ࠆ㧚. ࡠᴺߢ⹏ଔߒߚ⚿ᨐࠍ࿑ 5 ߦ␜ߔ㧚ห࿑ߦߪ㧘ᱜⷙಽᏓ. ⻢. ߩ႐วߩࡌࠗ࠭⛔⸘ߦࠃࠆᚢ⇛ߩ⚿ᨐ߇ Bayes24 ߣߒߡ ૬⸥ߐࠇߡ߅ࠅ㧘ࡐࠕ࠰ࡦಽᏓߦࠃࠆ⚿ᨐߪಠ଀ߦ P- ࠍ. ㄉ. ┻᧛ᓆㅢ㧘ጊᧄ᦭૞㧘⋥㊁ஜ㧘੹᧛ବᐘ㧘 ᩿ቁᵗߩ. ߟߌߡ␜ߒߡ޿ࠆ㧚. ฦ᳁߆ࠄ޿ߚߛ߈߹ߒߚ⾆㊀ߥࠦࡔࡦ࠻ߦᗵ⻢⥌ߒ߹ߔ㧚 ᧄ⎇ⓥߩ৻ㇱߪᢥㇱ⑼ቇ⋭ߩ⑼ቇ⎇ⓥ⾌‫ޟ‬ᖱႎ῜⊒ᤨ. ࿑ 5 ࡐࠕ࠰ࡦಽᏓߩ႐วߩᕈ⢻⹏ଔ (M = 24,. ઍߩࡠࡃࠬ࠻ߥ⥄േ࠴ࡘ࡯࠾ࡦࠣ࠰ࡈ࠻࠙ࠚࠕߦะߌߚ. = 1.0). ᢙℂ⊛ၮ⋚ᛛⴚߩ⎇ⓥ‫․(ޠ‬ቯ㗔ၞ⎇ⓥ 18049014) ߦࠃ ࠅⴕࠊࠇߡ޿߹ߔ㧚. ෳ. ࡐࠕ࠰ࡦಽᏓߪ㕖⽶ᢛᢙ୯ࠍขࠆ㔌ᢔ⊛ߥಽᏓߢ㧘Ꮐ ฝኻ⒓ߢ߽ߥ޿㧚੹࿁ㆬࠎߛ. = 1 ߢߪ 0 ߣ 1 ࠍขࠆ. ⏕₸߇ߣ߽ߦ 1/e ߢ㧘ߘࠇએ਄ߩ୯ࠍขࠆ⏕₸ߪᕆㅦߦ. 0 ߦㄭߠߊ㧚ࠃߞߡ㧘ᱜⷙಽᏓߣߪ⋧ᒰߦ⇣ߥࠆಽᏓߢ ޽ࠆ㧚ߒ߆ߒ࿑ߦࠃࠇ߫㧘Y ߩ⹜ⴕ࿁ᢙ߇߿߿Ⴧടߔࠆ ߽ߩߩ㧘ో૕⊛ߥ௑ะߪᚲⷐᤨ㑆ಽᏓ߇ࡐࠕ࠰ࡦಽᏓߢ ߽޽߹ࠅᄌൻ߇ߥ޿ߎߣ߇⺒ߺขࠇࠆ㧚ߥ߅㧘& ߇ᢛᢙ ߩߣ߈ߦ․ߦ ࠯ࡠᚢ⇛߇․⇣ߥ᜼േࠍ␜ߒߡ޿ࠆ߇㧘ߎ ࠇߪࡐࠕ࠰ࡦಽᏓ߇ขࠆ୯߇ᢛᢙߢ޽ࠆߚ߼ߣᕁࠊࠇࠆ㧚 ੹࿁ߪᱜⷙಽᏓࠍ઒ቯߒߚᚢ⇛ࠍࡐࠕ࠰ࡦಽᏓߦㆡ↪ ߒߚ߇㧘੹ᓟߪࡐࠕ࠰ࡦಽᏓࠍ઒ቯߒߚᚢ⇛ߣᱜⷙಽᏓ ࠍ઒ቯߒߚᚢ⇛ߣߩᲧセࠍⴕߥ߁ᔅⷐ߇޽ࠆ㧚. ⠨ ᢥ. ₂. 1) ⋥㊁ஜ㧘ⁿ⽴శ␽㧘ᧁ┙ᢘਯ㧦ⴕ೉⸘▚ߦ߅ߌࠆ⥄ േ࠴ࡘ࡯࠾ࡦࠣ⎇ⓥേะߦߟ޿ߡ㧘ᖱႎಣℂቇળ⎇ ⓥႎ๔ 2006-HPC-107, pp. 181—186 (2006). 2) Katagiri, T., Kise, K., Honda, H. and Yuba, T.: ABCLibScript: a directive to support speciﬁcation of an auto-tuning facility for numerical software, Parallel Computing, Vol. 32, No. 1, pp. 92—112 (2006). 3) ᩿ቁᵗ㧦࠰ࡈ࠻࠙ࠚࠕ⥄േ࠴ࡘ࡯࠾ࡦࠣ㧘ᘢᢥ␠ (2004). 4) 㗇↰␞ੳ㧦ታⴕᤨ⥄േ࠴ࡘ࡯࠾ࡦࠣߩߚ߼ߩㅙᰴታ 㛎⸘↹ߩ৻ᚻᴺ㧘ᣣᧄᔕ↪ᢙℂቇળⅣἑᚭౝᔕ↪ᢙℂ ⎇ⓥㇱળ ╙ 10 ࿁ࠪࡦࡐࠫ࠙ࡓ⻠Ṷ੍Ⓜ㓸, pp. 39—44 (2006). 5) ዊ⼱๺ᱜ㧘㗇↰␞ੳ㧦᳢↪⊛ߥ࠰ࡈ࠻࠙ࠚࠕ⥄േ ࠴ࡘ࡯࠾ࡦࠣᯏ᭴ߩߚ߼ߩታ㛎⸘↹ᴺߩᔕ↪ߩᬌ⸛㧘 ᖱႎಣℂቇળ⎇ⓥႎ๔ 2006-HPC-107, pp. 193—198 (2006). 6) Berry, D. A., and Fristedt, B.: Bandit Problem, Chapman and Hall (1985). 7) ᧖ේᱜ㘌㧘ቶ↰৻㓶㧦ᢙ୯⸘▚ᴺߩᢙℂ㧘ጤᵄᦠᐫ (1994). 8) Hairer, E., Nørsett, S.P., and Wanner, G.: Solving Ordinary Di&erential Equations I (Second Revised Edition), Springer (2000).. −18−.

(13)

実行時自動チューニングのための逐次実験計画 ～分散が共通な２つの正規分布の場合～

実行時自動チューニングのための逐次実験計画～分散が共通な２つの正規分布の場合～