https://www.coursera.org/learn/data-driven-astronomy
--------------------------------------------------------
Week 2: Big data makes things slow
제2주차: 자료가 방대해지면 뭘하든 느려진다.
- How to work out the time complexity of algorithms
복잡한 계산을 빠르게 수행하는 방법
- Exploring the black holes at the centers of massive galaxies
거대 은하의 중심부 블랙 홀 찾기
--------------------------------------------------------
1강: 방대한 자료는 일을 더디게 만든다
Lesson 1: Big Data makes things slow / 한글자막
--------------------------------------------------------
2강: 초거대 블랙홀과 활동성 은하 핵(AGN)
Lesson 2: Supermassive Black Hole / 한글자막
--------------------------------------------------------
3강: 교차정합(cross-matching) 알고리즘에 대하여
Lesson 3: What is cross-matching ? / 한글자막
--------------------------------------------------------
4강: 실행 시간 복잡도 평가
Lesson 4: Evaluating Time Complexity / 한글자막
--------------------------------------------------------
5강: 더욱 빠른 알고리즘
Lesson 5: A (much) faster algorithm / 한글자막 / 영문자막[강의대본]
[00:06] 이번주 강좌를 시작 하면서 전파 대역에서 관측한 은하 목록을 광학 대역으로 관측한 은하의 목록에 맞춰(정합)보았다. 이렇게 맞춰진 두 은하는 실제로 동일한 것이다. 느슨한 교차정합(naive cross-matching) 알고리즘을 컴퓨터 프로그램(파이썬 사용)으로 구현해 봤다. 몇가지 개선을 시도해 봤지만 결과를 얻기까지 매우 느리다는 문제를 발견하게 됐다.
우리가 만든 교차정합에 어떤 문제가 있는지 알고있다. 이는 나뿐만 아니라 대부분 천문학자들이 항상 부디치는 문제이므로 누군가 이에 대한 고민을 해봤을 것이고 해결책을 찾아 놨을 것이라고 추측할 수 있다. 그리고 확실히 그 해결책이 있다. 파이썬의 astropy 모듈(라이브러리)은 교차정합 함수를 가지고 있는데 엄청나게 쉽게 각거리를 계산하고 두 관측목록의 교차정합을 수행한다.
[00:47] 어떻게 이렇게 빠르게 할 수 있을까? 전에 astropy 모듈을 사용하여 교차정합을 해본적이 있는데 백만개의 항목을 수록한 두 목록의 교차정합에 단 25초밖에 걸리지 않았다. 우와! 우리 프로그램으로는 24일에서 개선 해다고 해봐야 12일이 걸릴일은 단 25초에 해내다니 놀랍다. astropy 에는 이 일을 해내기 위해 어떤 신통한 마법이라도 있는 것일까?
[01:12] 그 해답은 k-d 트리(나무모양의 가지치기 구조)라고 하는 자료구조에 있다. k-d 트리는 k-dimensional tree 의 약자인데 점들을 공간에 재귀적(자기참조, recursive) 구조로 표현한다.
* 컴퓨터를 비롯해 기계가 제일 잘하는 일이 '반복'이다. 정의만 잘 해주면 덧셈뺄셈을 하든, 로그와 삼각함수를 계산하든 반복해야 할 일의 난이도에 불평도 없다! 일을 반복시키는 방법으로 구간 또는 조건을 정해놓은 '단순반복(for-repeat, while-repeat)'과 좀더 지능적인 '재귀적 반복(recursive loop)'이 있다. 함수 내에서 자기 자신을 호출 하는 방식으로 이뤄진다(recursive function call). '단순반복'에 의한 변화량이 선형적 이라면 '재귀적 반복'은 기하급수적인 변화를 뛰어넘는다. 이 강의에서 보게될 트리 탐색, 프랙탈(Fractal)이 대표적인 재귀적 반복의 예다.
[01:23] K는 차원의 수를 나타내는 것으로 우리가 사용했던 공간의 좌표계에서는 적경(RA,right ascension)와 적위(DEC, declination)의 2차원이었다. K-d 트리를 구성하기 위해 공간을 매번 중간값(median)을 기준으로 재귀적으로 분할 한다. 예를 들어보자.
[01:39] 이 기하학적으로는 2차원인 공간을 x-차원(축)의 중심에 가까운 점, 여기에서는 A를 기준으로 양분한다.
* K-d 트리에서 각 분할을 차원이라 한다. 이 분할을 지칭하는 차원은 수리 기하학에서 말하는 물리적 차원이 아닌 개념적의미다. 그리고 아직 몇개로 분할할지 정해지지 않았다.
[01:42] 처음 양분한 기준인 점 A를 트리의 뿌리(root)가 된다. 이어서 A를 기준으로 양분된 평면 중 왼편을 y-축(차원)에서 분할한다. y-축 중앙에서 가장 가까운 점 E를 중심점(median)으로 삼는다. 이렇게 x 와 y 축을 번갈아가며 중심점을 찾고 더이상 왼편으로 분할한 공간에 점이 없을 때까지 분할해 나간다. 왼 평면이 끝나면 이어 오른 평면, 윗 평면이 끝나면 아랫 평면으로 분할을 계속하여 그 이력을 가지친 나무 모양으로 만들어 놓는다.
[02:10] 이제 나무가 완성 되었으므로 이를 활용할 차례다. 빠르게 이웃하는 점을 탐색하는 방법이다.
* 자신의 위치에서 동일한 행동을 반복하는 행위를 재귀적 반복(recursive)이라고 한다.
일반적인 반복(repeat)은 횟수(loop count)가 정해져 있지만 재귀적 반복은 횟수가 정형화 되어 있지 않다. 정형화 되어 있지 않은(분포빈도는 물론 갯수조차 알려져 있지 않음) 실험이나 관측 자료를 검색할 때 재귀적 알고리즘이 유리하다.
[02:16] 점 T에 은하가 있다 하고 이와 가장 가까운 점을 탐색해보자. 먼저 뿌리 마디(node) A와 거리를 계산한다. 탐색을 시작하는 시점에서 점 A는 T와 가장 가까운 셈이다.
[02:26] X-축 상으로 T는 A보다 작으므로 A 에서 왼쪽 가지를 택하여 마디 E에서 탐색을 시작한다. A보다 E가 T에 가깝다는 것은 잠재적으로 가장 근접한 정합 원의 크기를 줄일 수 있다는 것이고 네개의 구획을 건너뛰게 됐다는 것이다.
[02:42] 이제 이 과정을 반복해 보자. 이번에는 점 T와 E의 Y-축 값을 비교해 보자. E보다 T의 Y-축 값이 크다. 윗편 분할, 즉 마디 E의 오른쪽 가지의 B를 택한다. 점 B가 T에 더 가까워 정합 원의 반경을 더 줄일 수 있다.
[02:55] 좌측 위의 영역에 아직 남아있는 두개의 상자를 탐색 해보자. 우측 가지의 마디 D가 앞서 좁혀놓은 정합 원의 범위에 벗어났다. 따라서 D는 제외한다. 이제 더이상 탐색해 볼 가지가 없다. 최적 정합 원에 걸쳐있는 분할이 없다는 뜻이다.
[03:11] K-트리의 가장 큰 장점은 목표 T와 가장 근접한 점을 찾을 때 노란 색으로 표시된 점들은 아예 비교대상에 넣지도 않았다는 것이다.
[03:18] 자료창고(Database)의 규모가 방대해 질 수록 탐색 시간을 아낄 수 있는 규모는 엄청나다. 우리의 프로그램 속도가 빨라지고 시간 복잡도가 개선된다.
[03:27] 핵심 알고리즘을 변경하여 작업시간을 엄청나게 줄이고 작업규모의 증가에 대한 대응(scalability)도 엄청나게 개선 시킬 수 있다. (위 도표의 검은 실선으로 선형적이며 기울기는 O(n log n)보다 작다! 앞서 우리가 작성했던 알고리즘은 증가하는 자료의 량 n 에 따라 처리시간은 제곱으로 늘어 났었다는 점을 기억하자! 아래 도표에서 O(n^2)에 해당.)
<그림> 트리 탐색 시간 O(n log n)
[03:33] 만일 교차정합의 규모가 정말로 크다면 시간 이외에 고려할 사항이 한둘이 아니다. 예를들어 자료를 저장해 놓기 좋은 자료창고도 찾아봐야 한다. 좋은 자료관리 도구를 사용하므로서 매번 목록을 읽을 때마다 중요한 CPU 동작의 상당량을 줄일 수 있다.
[03:49] 또다른 중요한 사항으로 결합 하여 얻는 주변 관련 기술의 활용이다. 혹은 은하가 보여주는 물리적인 특성에 어떤것이 있을지 알아보는 것이다. 이 질문에 답을 하자면 아마도 천문학적 관점으로 접근하는 것 외에 전산 과학적 사고(computational thinking)를 결합하는 것이다.
[04:04] 예를들어 관측한 대상의 적색편이를 측정할 수 있다면 같은 거리에 있는 것들끼리 묶어놓을 수 있다. 그렇게 묶인 은하들은 물리적으로 유사성을 더 많이 가졌을 것이라고 볼 수 있다. 또한 두가지 탐사에서 천체의 공간적 밀도에서 추측해낸 유사성을 정량화 하기위해 통계분석을 해보고 싶을 것이다.
[04:23] 자 이제 우리는 교차정합(cross-matching)을 성공적으로 마쳤다. 이를 통해 우리가 얻은 것은 무엇인가? 거의모든 전파원들은 광학적으로도 관측 가능한 것들이다. 이는 두개의 서로다른 목록을 만들 수 있다는 뜻이다.
[04:37] 전파은하의 대부분은 퀘이사와 관련이 있다. 은하중심의 블랙홀을 찾는 곳에서 강력한 강착원반을 볼 수 있다. 강착원반의 복사는 은하내의 전체 별을 합한 것보다 밝다. 마치 밝은 별처럼 보이기 때문에 이를 별에 준한 천체(quasi-stellar object), 퀘이사(quasar)라고 부른다.
[04:59] 우리가 알고있는 전파은하의 배부분은 일반 은하의 내에 자리한다. 그곳에 별들이 떼지어 구름처럼 몰려있는 것을 볼 수 있다. 이 별들의 구름의 존재는 물질을 빨아들이는 초거대 블랙홀의 활동이 중지했다는 의미다. 그리고 그 잔여활동으로 전파 분출이 있다. 대부분 광학적으로 전파원을 확인해 왔으므로 그들의 적색편이 또한 확인할 수 있었다. 이 적색편이는 각 은하와 퀘이사의 거리를 알려준다.
[05:23] 은하의 적색편이가 0.02에서 0.5의 범위에 있는 반면 퀘이사의 적색편이는 0.2에서 3에 이른다. 이로서 대부분 은하들이 상대적으로 가깝게 위치하는 우주라는 사실을 알려준다. 반면 퀘이사는 대개 훨씬 더 멀리 있다. 광학 목록과 전파 목록을 정합해 보면서 초거대 블랙홀을 보유할 수 있는 은하가 따로 있다는 것을 알게됐고 그 은하까지 거리를 측정 할 수 있게 되었다. 이는 다른 파장대의 관측으로 얻는 정보를 취합하여 얻은 과학연구의 성과의 예다.
[05:54] 현대 천문학이 다파장 관측으로 접근하는 이유를 보여준다.
* 현대 천문학에 기여한 과학기술로 컴퓨터기술,고감도 반도체 센서,다파장 관측,우주탐사을 들 수있다.
[관련 강좌] AstroTech, https://www.coursera.org/learn/astronomy-technology
댓글 없음:
댓글 쓰기