๋…๊ธ€์›๋ฌธ๋งํฌ


๋จธ์‹ ๋Ÿฌ๋‹ ์ž…๋ฌธ ๊ธ€ ๋„ˆ๋ฌด ์ข‹์•˜์Šต๋‹ˆ๋‹ค!ย ๊ธ€์“ด์ด ๋ถ„๊ป˜ ๊ฐ์‚ฌํ•˜๊ณ ์š”.

ํ˜น์‹œ ์ˆ˜์‹ ๋•Œ๋ฌธ์— ์ดํ•ด๊ฐ€ ์•ˆ ๋œ๋‹ค ์‹ถ์€ ๋ถ„๋“ค์„ ์œ„ํ•ด ์ˆ˜์‹ ํ•ด์„ค์„ ํ•ด๋ณด๋„๋ก ํ•˜๊ฒ ์Šต๋‹ˆ๋‹ค.


์›๊ธ€๊ณผ ๊ฐ™์ด ๋ณด๊ธฐ๋ฅผ ๊ถŒํ•ฉ๋‹ˆ๋‹ค๋งŒ ๋ชจ๋ฐ”์ผ์ด๋ผ๋ฉด ๋ญ... ์–ด์ฉ” ์ˆ˜ ์—†์ฃ .

์•„, ๊ณ 1 ์ˆ˜์ค€ ์ง‘ํ•ฉ ๊ธฐํ˜ธ๋“ค์€ ์•„์‹œ์ฃ ? ๊ทธ๊ฑด ๋”ฐ๋กœ ์„ค๋ช… ์•ˆํ•ฉ๋‹ˆ๋‹ค~

๋จผ์ € ์ด๊ฑด, '๊ตต์€ x' (ํฐ X ๋ง๊ณ )์— x1, x2๋ผ๋Š” ๋‘ ๊ฐ€์ง€ ์ •๋ณด๋ฅผ ์ €์žฅํ•ด๋‘๋Š” ๊ฐœ๋…์œผ๋กœ ์ดํ•ดํ•˜์‹œ๋ฉด ํŽธํ•ฉ๋‹ˆ๋‹ค.

๊ทธ๋Ÿฌ๋ฉด ๋งจ ์•ž์˜ ํฐ X๋Š” ๋ญ๋ƒ? ๊ฐ€๋Šฅํ•œ '๊ตต์€ x'๋“ค์„ ๋ชจ์กฐ๋ฆฌ ๋ชจ์•„๋‘” ๊ฒƒ์ž…๋‹ˆ๋‹ค!ย 

'๊ตต์€ x'๋Š” ์–ด๋–ค ๊ธ€ ํ•˜๋‚˜, ํฐ X๋Š” ์šฐ๋ฆฌ๊ฐ€ ํ˜„์žฌ ์•Œ๊ณ  ์žˆ๋Š” ๋ชจ๋“  ๊ธ€๋“ค์„ ๋ชจ์•„๋†“์€ ์ง‘ํ•ฉ์„ย ์˜๋ฏธํ•œ๋‹ค๊ณ  ์ƒ๊ฐํ•˜์‹œ๋ฉด ๋˜๊ฒ ๋„ค์š”.

๋ฌผ๋ก  ์—„๋ฐ€ํ•˜๊ฒŒ๋Š” ๊ทธ ๊ธ€์˜ ์œ ๋™IP, ์ œ๋ชฉ์ด๋ผ๋Š” ๋‘ ๊ฐ€์ง€ ํŠน์„ฑ์„ ์˜๋ฏธํ•ฉ๋‹ˆ๋‹ค.

๋„˜์–ด๊ฐ€์ฃ . ์—ฌ๊ธฐ์„œ ์˜ˆ๋ฅผ ๋“ค์–ด์„œ (x1, y1)์—์„œ, x1์ด '๊ตต์€ x'์ฃ ? ์œ ๋™ IP๊ฐ€ ์•„๋‹™๋‹ˆ๋‹ค!ย 

์ฆ‰, ์—ฌ๋Ÿฌ ๊ฐœ์˜ '๊ตต์€ x'๊ฐ€ ์žˆ๋Š”๋ฐ, x1์€ ๊ตต์€ x ์ค‘ ์ฒซ๋ฒˆ์งธ, ์ฆ‰ ์ฒซ๋ฒˆ์งธ ๊ธ€. x2๋Š” ๋‘๋ฒˆ์งธ ๊ธ€... ์ด๋Ÿฐ ์‹์œผ๋กœ ์ดํ•ดํ•˜๋ฉด ํŽธํ•ฉ๋‹ˆ๋‹ค.

๊ทธ๋Ÿฌ๋‹ˆ๊นŒ (x1, y1)=((x1,x2),y1). ๋Œ€์ถฉย ์ด๋Ÿฐ ๊ฐœ๋…์ด๋‹ค ์ •๋„.

๊ทธ๋ฆฌ๊ณ  ์ด์ œ๋Š” (x1, y1)์ด ํ•˜๋‚˜์˜ ๊ธ€(์ •ํ™•ํžˆ๋Š”, ๊ทธ ๊ธ€์˜ ์„ธ ๊ฐ€์ง€ ํŠน์„ฑ. ์œ ๋™IP, ์ œ๋ชฉ, ๋ถ„ํƒ•๊ธ€์ธ์ง€ ์ •๋ณด๊ธ€์ธ์ง€)์„ ์˜๋ฏธํ•ฉ๋‹ˆ๋‹ค.ย 

S๋Š” ๊ทธ๋Ÿฐ ๊ธ€๋“ค, ์šฐ๋ฆฌ๊ฐ€ ๊ฐ€์ง„ ์ž๋ฃŒ๋“ค์„ ๋ชจ์•„๋†“์€ ๋„์„œ๊ด€ ๊ฐœ๋…์ด๊ณ ์š”.


์•„, X ๊ณฑํ•˜๊ธฐ Y๋ผ๋Š” ๊ฒŒ ์˜ค๋ฅธ์ชฝ์— ๋ณด์ด์‹ค ๊ฒ๋‹ˆ๋‹ค. ๊ฑฐ๊ธฐ์„œ ๊ณฑํ•˜๊ธฐ๋Š” ๋ฐ์นด๋ฅดํŠธ๊ณฑ์ด๋ผ๊ณ  ํ•˜๋Š”๋ฐ,

์˜ˆ๋ฅผ ๋“ค์–ด์„œ ์ง‘ํ•ฉ A={1,2}, B={1,3,4}๊ฐ€ย ์žˆ์œผ๋ฉด,

A ๋ฐ์นด๋ฅดํŠธ๊ณฑ B๋Š” {(1,1), (1,3), (1,4), (2,1), (2,3), (2,4)}์ž…๋‹ˆ๋‹ค. ํ•˜๋‚˜์”ฉ ๊ณจ๋ผ์„œ ๋ฌถ์–ด๋†“๋Š” ๊ฐœ๋…์ด๋ผ๊ณ  ๋ณด์‹œ๋ฉด ๋ฉ๋‹ˆ๋‹ค.


h๋ผ๋Š” ํ•จ์ˆ˜๋Š” x์˜ ๋‘ ๊ฐ€์ง€ ํŠน์„ฑ(์œ ๋™IP, ์ œ๋ชฉ)์„ ์ž…๋ ฅํ•ด์ฃผ๋ฉด, y(๋ถ„ํƒ•๊ธ€์ธ๊ฐ€, ์ •๋ณด๊ธ€์ธ๊ฐ€?)๋ฅผ ์ถœ๋ ฅํ•ด์ฃผ๋Š” ํ•จ์ˆ˜์ž…๋‹ˆ๋‹ค.

์•„๋ž˜์˜ f๋ผ๋Š” ํ•จ์ˆ˜๋Š” '์ •๋‹ต'์ด๊ณ , h๋Š” ์šฐ๋ฆฌ๊ฐ€ ์„ธ์šด ๊ฐ€์„ค์ด๋‹ค, ๊ทธ๋Ÿฌ๋‹ˆ๊นŒ ํ‹€๋ฆด ์ˆ˜๋„ ์žˆ์Šต๋‹ˆ๋‹ค.

def๋Š” ์ •์˜๋ฅผ ์˜๋ฏธํ•ฉ๋‹ˆ๋‹ค. ์ €๊ฑธ ๊ทธ๋ƒฅ ์ค„ ์„ธ ๊ฐœ ๊ธ‹๋Š” ๊ฑธ๋กœ ์“ฐ๊ธฐ๋„ ํ•˜๋Š”๋ฐ, ๊ทธ๋Ÿฌ๋‹ˆ๊นŒ L์ด๋ผ๋Š” ํ•จ์ˆ˜๋ฅผ ์˜ค๋ฅธ์ชฝ์— ์žˆ๋Š” ์ˆ˜์‹๊ณผ ๊ฐ™์ด ์ •์˜ํ•˜๊ฒ ๋‹ค๋Š” ๋œป์ž…๋‹ˆ๋‹ค.

P(h(x)=/f(x))๋Š” ์ž„์˜์˜ ๊ตต์€ x๋ฅผ ์ž…๋ ฅํ–ˆ์„ ๋•Œ(์ฆ‰, ์–ด๋–ค ๊ธ€์„ ๋ฐ์ดํ„ฐ๋กœ ๋„ฃ์—ˆ์„ ๋•Œ), ๊ฐ€์„ค์— ๋”ฐ๋ฅธ ๋‹ต๊ณผ, ์ •๋‹ต์ด ๋‹ค๋ฅธ ํ™•๋ฅ ์„ ์˜๋ฏธํ•ฉ๋‹ˆ๋‹ค.

D๋‹ˆ f๋‹ˆ S๋‹ˆ ์•„๋ž˜์ฒจ์ž๋“ค์ด ์—ฌ๋Ÿฟ ์žˆ๋Š”๋ฐ, D๋ผ๋Š” ํ™•๋ฅ ๋ถ„ํฌ ํ•˜์—์„œ ๋ฐ์ดํ„ฐ๋ฅผ ์ถ”์ถœํ•ด์„œ... ์–ด์ฉŒ๊ณ ์ €์ฉŒ๊ณ . ๊ทธ๋ƒฅ ์•Œ๋ฉด ์ข‹๊ธด ํ•œ๋ฐ ๋ณ„ ์‹ ๊ฒฝ ์•ˆ ์“ฐ์…”๋„ ๋ฉ๋‹ˆ๋‹ค.

๊ทผ๋ฐ ์šฐ๋ฆฌ๊ฐ€ ์ •๋‹ต์„ ๊ตฌํ•˜๋ ค๊ณ  h๋ผ๋Š” ๊ฐ€์„ค์„ ์„ธ์šด ๊ฑด๋ฐ, ์ •๋‹ต์ธ f๋ฅผ ์–ด๋–ป๊ฒŒ ์•Œ๊ณ  h๋ž‘ ๊ฐ™์€์ง€ ๋‹ค๋ฅธ์ง€ ๋น„๊ต๋ฅผ ํ•ฉ๋‹ˆ๊นŒ?

๊ทธ๋ž˜์„œ ์‹์€ ์ด๋ ‡๊ฒŒ ์ˆ˜์ •๋ฉ๋‹ˆ๋‹ค. ์ฆ‰, m๊ฐœ์˜ ๊ธ€์ด ์žˆ๋Š”๋ฐ, ๊ทธ ๊ธ€์„ ๋ชจ๋‘ h๋ผ๋Š” ๊ฐ€์„ค์— ์ž…๋ ฅํ•ด๋ด…๋‹ˆ๋‹ค.

์—ฌ๊ธฐ์„œ ๋ถ„์ž๋Š” ํ‹€๋ฆฐ ๊ฒƒ์˜ ๊ฐœ์ˆ˜๋ฅผ ์˜๋ฏธํ•ฉ๋‹ˆ๋‹ค. (ํ‹€๋ฆฐ ๊ฒƒ ์ˆ˜)/(์ „์ฒด ๊ธ€ ์ˆ˜)๊ฐ€ ๋ญก๋‹ˆ๊นŒ? ์˜ค๋‹ต๋ฅ ์ด์ฃ .

์ด๋ ‡๊ฒŒ ์—ฌ์ฐจ์ €์ฐจํ•ด์„œ, S๋ผ๋Š” ๋ฐ์ดํ„ฐ๋ฅผ ์–ด๋–ป๊ฒŒ ์ž˜ ๋ถ„์„ํ•ด์„œ,ย ์˜ค๋‹ต๋ฅ ์ด ์ตœ์†Œ๊ฐ€ ๋˜๋Š” ๊ฐ€์„ค h๋ฅผ ์ฐพ์Šต๋‹ˆ๋‹ค.ย 

argmin์€ '์ตœ์†Œ๋กœ ๋งŒ๋“ค์–ด์ฃผ๋Š”'. ์ฆ‰ ์˜ค๋‹ต๋ฅ ์„ ์ตœ์†Œ๋กœ ๋งŒ๋“ค์–ด์ฃผ๋Š” ๊ฐ€์„ค h๋ฅผ ์ฐพ์œผ๋ผ ์ด ๋ง์ž…๋‹ˆ๋‹ค.

์ด๊ฑด 'S์— ํฌํ•จ๋˜์–ด ์žˆ๋Š” ๊ฑฐ๋ฉด yi๋ฅผ, ํฌํ•จ๋˜์–ด ์žˆ์ง€ ์•Š์€ ์ƒˆ๋กœ์šด ์ž๋ฃŒ๋ฉด '์ •๋ณด๊ธ€'์„ ์ถ”์ถœํ•ด๋ผ!'

๊ทผ๋ฐ S์— ํฌํ•จ๋˜์–ด ์žˆ์œผ๋ฉด ์ด๋ฏธ ์šฐ๋ฆฌ๊ฐ€ ์ •๋‹ต์„ ์•„๋Š” ๊ฑฐ๋‹ˆ๊นŒ ์ •๋‹ต์ด ๋‚˜์˜ค๋Š” ๊ฒŒ ๋‹น์—ฐํ•˜๊ณ ...

์• ์ดˆ์— ์šฐ๋ฆฌ๋Š” S์— ํฌํ•จ๋˜์–ด ์žˆ์ง€ ์•Š์€ ์ž๋ฃŒ๋ฅผ ๋ณด๊ณ , ๊ทธ๊ฒŒ ์ •๋ณด๊ธ€์ธ์ง€ ๋ถ„ํƒ•๊ธ€์ธ์ง€ ์ถ”๋ก ํ•˜๊ธฐ ์œ„ํ•ด h๋ผ๋Š” ๊ฐ€์„ค์„ ์“ฐ๋Š” ๊ฒ๋‹ˆ๋‹ค.

๊ทผ๋ฐ ๊ทธ๋Ÿฐ ๊ฑธ ์‹น ๋‹ค ์ •๋ณด๊ธ€๋กœ ํŒ์ •ํ•ด๋ฒ„๋ฆฌ๋ฉด? ์ผ์ผ์ด ๋“ค์–ด๊ฐ€์„œ ํ™•์ธํ•ด๋ณด๋ผ๋Š” ์†Œ๋ฆฌ์ฃ .

...๊ทธ๊ฑด ๋‚˜๋„ ํ•˜๊ฒ ๋‹ค.


์ด์ƒ์ž…๋‹ˆ๋‹ค.