spiral matrix

spiral matrix란 다음과 같은 행렬이다.

 0  1  2  3  4
15 16 17 18  5
14 23 24 19  6
13 22 21 20  7
12 11 10  9  8

1. 가로 세로 길이의 제한은 없다. 같을 필요가 없다.
2. 0이 왼쪽 위가 아니라 네 귀 어디나 올 수 있다.
3. 회전방향도 시계/반시계 모두 가능하다.
4. 시작점(가장 작은 숫자)이 바깥(involute)이 아니라 중심이어도 된다. 이러면 중심에서 밖으로 그린다(evolute)

• 가장 작은 숫자가 왼쪽 위 귀에 오는 것을 기본형이라고 한다면, 0이 다른 귀에 오는 형태도 기본형에서 쉽게 변형 가능하다. 그냥 회전.
• evolute도 involute로부터 쉽게 얻는다. 위의 \(5 \times 5\)의 경우, 24에서 각 셀의 값을 뺀것으로 셀을 채우면 된다. new = max - old
• 1로 시작하는것도 기본형으로부터 쉽게 얻는다. 그냥 모든 셀에 대해 +1 
• 방향을 바꾸는 것도 기본형으로부터 가능하다. 예를들어 \(5 \times 6\) 반시계를 얻고 싶으면 \(6 \times5\) 기본형(=시계방향)을 가지고 xy대칭시키면 된다.

결국 문제는 임의의 사이즈의 기본형을 어떻게 얻느냐이다.

가장 쉬운 구현은 직관적으로 그대로 구현하는 것이다. (이하의 모든 소스는 내 github에서 다운받을 수 있다.) http://rosettacode.org/wiki/Spiral_matrix에 다양한 언어들의 해법이 있는데 대부분 이런식으로 구현한 것이다.

두번째 해법은 Joey Tuttle이라는 사람의 아이디어를 이용한 해법이다. 위 페이지의 여러 구현중 J의 구현을 보면 http://www.jsoftware.com/papers/play132.htm 페이지로 링크가 있고 거기 설명이 잘 되어있다. 해당 페이지의 설명대로 구해도 되고, 정확히 같은 원리지만 좀 더 직관적이고 구현이 쉬운 방법은 다음과 같다. 일단 \(3\times 4\)를 예로 들면, 진행방향이 오른쪽이면 +1, 아랫줄이면 +4, 왼쪽이면 -1, 위쪽이면 -4이다. column width(=stride size)가 4이기 때문이다.

0  1  2  3
4  5  6  7
8  9 10 11
규칙없이 0부터 차례대로 적은 것이다. 이 행렬을 그려야 하는 순서대로 짚어나가면서 숫자를 적으면

0, 1, 2, 3, 7, 11, 10, 9, 8, 4, 5, 6 이 된다.

계차수열을 구하면,

1, 1, 1, 4, 4, -1, -1, -1, -4, 1, 1

이것이 규칙이다.
같은 사이즈의 행렬에 우리가 따라가야 하는 경로대로 위 숫자들을 넣으면 더 잘 보인다.

 * →  1 →  1 → 1
               ↓
-4 →  1 →  1   4
 ↑             ↓
-1 ← -1 ← -1 ← 4
square matrix의 경우를 고려하면 규칙이 더 쉽게 보인다. 

예를들어 \(3\times 3\)이라면 1, 1, 3, 3, -1, -1, -3, 1 일 것이다. 이것을 거꾸로 하면 1, -3, -1, -1, 3, 3, 1, 1
부호는 교차되면서 1과 stride size가 교대된다. 가로가 길거나 세로가 더 긴경우도 쉽게 알 수 있다.

보면 알겠지만 evolute가 더 구현하기는 쉽다. 그걸 뒤집으면 involute가 되고. 여튼 involute를 바로 구하는 것도 그리 어려운 일은 아니어서 구현된 코드도 그렇게 만들어졌다.

이제 1과 stride, 부호를 적당히 섞은 수열만 가지면 0, 1, 2, 3, 7, 11, 10, 9, 8, 4, 5, 6 을 그냥 얻을 수 있다. 실제로 네모에 그려보지 않고서.

이제부터가 핵심인데 이 수열을 inverse permutation한다.

그러면 0, 1, 2, 3, 9, 10, 11, 4, 8, 7, 6, 5

넷씩 끊어 적으면,

0  1  2  3
9 10 11  4
8  7  6  5
답을 얻는다.

inverse permutation이란게 position정보를 겉으로 드러내는 것이라 어찌보면 당연한 과정인데, 또 다시 생각해보면 그리 녹록한 직관력은 아니다. 凡夫는 그저 감탄할 뿐. 구현도 매우 쉽다. 다만, 구현을 해보면 중간 단계를 거쳐야 하기 때문에 메모리 소모가 많다. 최소 두배의 메모리가 필요하다. 구현된 코드는 최적화처리가 전혀 되어있지 않아서 세배 가까운 메모리가 필요하다. 내 랩탑은 메모리가 16G인데 \(30000 \times 30000\) 도 겨우 소화할 수 있었다.

마지막 방법은 일반항을 구해서 row, column값으로 바로바로 해당 cell의 값을 얻는 방법이다. 이 방법은 주변값을 이용하지 않는다. 다시말해, 어떤 위치에 있든 \( O(1) \)이다. 이렇게만 써놓으면 가장 속도가 빨라야 할것 같지만 (상수값 로드가 커서 = \( kO(n) \)이라 하면 \( k \)가 커서) 워낙 계산량이 좀 있기도 하고, 각 cell이 \( O(1) \)이니까 총 계산은 \( O(n) \)인데, 위 Joey의 방법도 \( O(n) \)이라 어떻게 구현하고 어떤 architecture를 쓰는지가 중요해진다.(심지어 첫번째 방법도 \( O(n) \)이다. 첫번째, 두번째 방법 모두 array의 각 cell에 접근하는 실제적인 문제때문에 \( O(n \log n) \)일것 같은데 이것도 확인해보지는 않았다) 하지만 정말 강력한 두가지 장점이 다른 모든 방법을 압도하는데, 일단 메모리를 쓰지 않는다. 다른 셀의 도움을 받지 않으므로 메모리에 뭔가를 저장해둘 필요가 없다. 그리고 다른 셀에 의존하지 않는다는 점은 더더욱 강력한 무기를 사용가능하게 만든다. 병렬화. 자원이 충분하다면 다른 방법들은 비교조차 안될 것이다. 일반항을 얻는 과정은 크게 어렵지 않으니 코드를 참고하면 된다. 기본 아이디어는, 밖에서부터 몇겹을 벗겨 나가야 해당 셀이 나오는지와, 해당 셀이 가장 바깥에 있을 때 몇번째로 그려지는가를 계산해 내는 것이다. 정확히 몇번째 셀인지만 알면 된다. 어차피 order자체가 그 cell의 값이니까.

speed test결과는 신뢰할수가 없는게, 리눅스박스에서 했을 때와 랩탑(OSX, xcode)에서 했을 때 결과가 많이 달랐다. g++버전도 서로 달랐다. 일단 랩탑에서 xcode profiler로 돌려보니 Joey가 가장 빨랐고 그보다 두배 약간 못되는 시간에 마지막 방법(일반항 구하는방법)도 solution을 냈다. 사람이 그리듯 일일이 그려보는 첫번째 방법은 Joey의 열배정도 느렸다. 리눅스에서는 일반항으로 구하는 방법이 압도적으로 빨랐는데 최적화옵션(-O4)이 알아서 병렬화한것 아닌가 의심이 가지만 확인해보지는 않았다.

메모리 allocation문제로 Joey가 그릴 수 있는 사이즈가 제일 작았고 가장 쉬운 첫번째 방법으로는 16기가 메모리로 대략 25억개 셀까지 가능했다. 이 경우에도 1분 미만이 소요되었다. 일반항 방법으로는 bignum을 썼다면 무한까지도 했을 것이다.

3차원의 경우도 비슷할 것으로 예상한다. 우리가 실패(reel)를 감는 방법을 응용해서 3차원에서도 spiral을 정의할 수 있다.

type 1 error, type 2 error

위키피디아에 보면 null hypothesis가 일단 대상이다. null hypothesis란 뭔가 효과가 없다는 가정을 말하는 것 같은데 영어가 짧아서 확신을 못하겠다. 예문으로 “이 식이요법은 사람들의 체중에 영향을 미치지 못한다”가 나와있다. 여기보면 더 쉽게 나와있는데 보통 ‘no difference’를 뜻한다.  예로, ‘A집단과 B집단이 아무 차이가 없다’가 null hypothesis다. H_1은 alternative hypothesis라고 한다.

이 null hypothesis의 진리값이 참일수도 있고 거짓일 수도 있는데, 진리값이 참일 경우 테스트가 참이라고 판별하면 True다. 지금 우리가 관심있는 부분은 False고. 곧, False positive, False negative 둘을 구분하는 것이 핵심이라고 할 수 있다. null hypothesis가 거짓인데도 테스트가 참이라고 하면 false positive, 참인데도 테스트가 거짓이라고 하면 false negative되겠다.

type 1 에러는 false positive다. 그러니까 null hypothesis가 거짓임에도 참이라고 한 케이스.
type 2 에러는 false negative.

궁금한것은, null hypothesis가 아닌 hypothesis에 대해서는 error의 type이 반대인가 하는 점. 말하자면, 위에서 든 예문이 만약에 “이 식이요법은 효과가 있다”라면, null hypothesis가 아닌데, 그러면 type 1 에러는 false negative가 되어야 하는가 하는 점이다. negation을 생각해보면, 그러니까 “이 식이요법은 영향이 없지 않다”라고 놓고 생각해보면, ‘없다’임에도 형식적으로는 그것이 positive라고 볼 수도 있을 것 같다. 그러면 모든 에러에 대해 type1,2를 false positive, negative로 정의할 수 있을 것이다. 하지만 이렇게 되면 대상이 null hypothesis일 이유가 없지 않나?
face detection논문에 보니 type1을 FRR, type2를 FAR로 해두었다.
무슨말이냐면,
FRR(false rejection rate) = type 1 error = 얼굴을 포함하지만 검출 실패
FAR(false acceptance rate) = type 2 error = 얼굴이 없지만 있다고 함
이렇게 해두었다. FRR은 false negative같은데 type 1 error라고 해둔것.
null hypothesis가 아니기 때문일까?(‘이 이미지에는 얼굴이 있다.’) 그럼 위에 적은것처럼 null이냐 아니냐가 type 1, 2를 가르는 걸까. 아님 논문이 틀린걸까. 아님 내가 전체적으로 이해를 못하고 있는건가.
당분간은 positive/negative보다 명제 자체(null이든 아니든 참인 진리값)에 대한 부정이면 type 1 error, 반대면 type 2 error로 이해하기로 한다. 모호한점 투성이다.
논문에서는 ‘얼굴이 없다’를 null hypothesis로 잡은 것이다. 이 때 positive라면 얼굴이 없는 것이고 negative라면 얼굴이 있는 것. (보통 ‘있다’는 positive와 연결되기 때문에 헷갈렸다.) 따라서 false positive (type 1 error)라면 얼굴이 있는 사진에서 없는것을 뜻하고, false negative 라면 얼굴이 없는 사진에서 있다고 한 것이다.

얼핏 생각해도 그렇고, 여타 일반적인 논문의 주장이 null hypothesis인 경우는 거의 없을 것이라 negation을 취해서 일부러 null hypothesis를 만드는 모양인데, 그렇다면 negation이 complement가 아닐 때는 type 1,2 error를 말하기 힘들어진다. 위의 경우는 있다/없다 이므로 조건을 만족하는 경우.

그리고 정의(definition)에 따라 null hypothesis일 때만 type 1,2 error를 말하기로 하면 위에서 한 질문(‘null hypothesis가 아닐 때는 어떻게 하나’)은 의미 없는 질문이다.