'삽질예방' 카테고리의 글 목록 (4 Page)

2008. 1. 28. 00:29

SVD와 압축 삽질예방/SVD2008. 1. 28. 00:29

출처 : http://markov.tistory.com/30
좋은 정보 감사합니다.

ㅡㅡㅡㅡㅡㅡㅡ

이번 글에서 다룰 내용은, m*n 행렬 X를 k*n 행렬 Z로 손실 압축(lossy compression)하는 방법입니다(k < n < m).

이렇게 크기가 줄어든 행렬 Z는, 목적에 따라 그 자체로 써먹을 수도 있지만 대부분은 원래의 m*n 행렬로 복원(decompression)한 다음에 사용하게 됩니다. 압축이 X에서 Z로의 변환이라면, 복원은 Z에서 X로의 역변환이 되겠죠. 역변환된 m*n 행렬을 ${\small \hat{\mathbf{X}}}$ 이라고 합시다. 이는 손실 압축된 Z로부터 복원한 것이므로, 원래의 X와는 약간 다를 것입니다. 즉, "정보의 괴리"가 발생합니다.

우리의 목적은, 압축률을 k*n으로 고정하였을 때, 원래의 X와 복원된 ${\small \hat{\mathbf{X}}}$ 간의 차이를 최소화 하는 압축 및 복원 알고리즘을 찾는 것입니다. 이것을 식으로 쓰면 아래와 같은 형태가 되겠죠.

(1) $\min_{\hat{\mathbf{X}}} ||\mathbf{X} - \hat{\mathbf{X}}||$

Z는 k*n으로 압축된 행렬이고 k < n이므로, Z의 rank는 최대 k입니다. 따라서 Z로부터 복원된 행렬 ${\small \hat{\mathbf{X}}}$ 의 rank 또한 최대 k가 됩니다. 반면, 원래의 행렬 X의 rank는 n으로, k보다 큽니다. 즉, 식 (1)은 X와의 오차가 가장 작은 rank k짜리 행렬을 찾는 문제가 되며, 이를 rank-k approximation 이라고 합니다.

이때 식 (1)의 norm이 2 norm이나 Frobenius norm이라면, 오차가 가장 작은 rank-k 행렬은 X를 ${\small \mathbf{X} = \mathbf{USV^T}}$ 로 SVD한 것에서 [singular value가 가장 큰 순서대로 k개를 뽑아 구성한 행렬]이 됩니다(주1). 이를 식으로 나타내면 아래와 같습니다.

(2) $\begin{array}{ccccc} \hat{\mathbf{X}} & = & \mathbf{U}_k & \mathbf{S}_k & \mathbf{V}_k^T\\ _{(m\times n)} & & _{(m\times k)} & _{(k\times k)} & _{(k\times n)} \end{array}$
$= \Big[\mathbf{u}_1|\cdots|\mathbf{u}_k\Big]\bigg[\begin{array}{ccc} s_1 & &\\ & \ddots &\\ & & s_k\end{array}\bigg]\left[\begin{array}{c} \mathbf{v}_1^T\\ \hline\\ \vdots\\ \hline\\ \mathbf{v}_k^T\end{array}\right]$

주석 보기

식 (2)에서 ${\small \mathbf{U}_k}$ 는 [U의 첫 번째부터 k번째까지의 열벡터들]만으로 이루어진 행렬을 의미하며( ${\small \mathbf{V}_k}$ 도 마찬가지 의미), ${\small \mathbf{S}_k}$ 는 [S의 첫 번째부터 k번째까지의 대각선 원소값들]로 이루어진 대각행렬을 나타냅니다. 각 행렬의 밑에 해당 행렬의 크기를 괄호로 표시하였습니다.

자, 이것으로 우리는, "압축 후 복원된 행렬은 식 (2)와 같아야 한다"라는 사실을 알았습니다. 그러면 이제 남은 것은, "X를 어떻게 압축했다가 복원하면 식 (2)와 같은 행렬을 얻을 수 있는지?"를 유도해내는 일이 되겠죠!

압축과 복원은, 간단히 행렬의 곱으로 구현할 수 있습니다. 예를 들어 m*n 행렬 X를 k*n 행렬 Z로 압축한다고 하면, 아래와 같이 k*m짜리 행렬 W를 X 앞에 곱해주는 것입니다. 이때 W가 바로 압축 변환이 됩니다.

(3) $\mathbf{Z} = \mathbf{WX}$

이번엔 Z를 ${\small \hat{\mathbf{X}}}$ 으로 복원해 보겠습니다. Z는 k*n이고 ${\small \hat{\mathbf{X}}}$ 은 m*n이니, 복원 변환은 m*k짜리 행렬이 되며(이를 Y라고 합시다) 이것을 아래와 같이 Z 앞에 곱해주면 됩니다.

(4) $\hat{\mathbf{X}} = \mathbf{YZ} = \mathbf{YWX}$

이제 압축 변환 행렬 W와 복원 변환 행렬 Y가 각각 무엇인가를 구해야 합니다만, 그러기 전에 여기서 한 가지 짚고 넘어갈 점이 있습니다. 복원된 행렬을 재압축할 때의 문제인데요... jpg 파일을 편집해보신 분들은 많이 느끼셨을 점인데, jpg 포맷은 복원된 이미지를 재압축하면 정보의 추가 손실이 발생하지요. 마찬가지로 음원 압축에서 널리 쓰이는 mp3 포맷도 그렇고요. 이거 꽤 불편하고 나쁘지 않습니까? 이 글에서 다룰 알고리즘은 ${\small \hat{\mathbf{X}}}$ 을 재압축하였을 때 추가적인 정보 손실이나 변환 없이 다시 Z로 돌아올 수 있도록 해 봅시다.

식 (4)에서 ${\small \hat{\mathbf{X}} = \mathbf{YWX}}$ 라고 했으니, 이걸 다시 압축하려면 W를 곱하면 되겠군요. 즉, WYWX = Z, 또는 WYWX = WX가 되어야 합니다(식 (3)에 의해 Z = WX이므로).
따라서, ${\small \mathbf{WY} = \mathbf{I}}$ 가 되어야 합니다. 이는 다시 말하면,

(5) $\mathbf{Y} = \mathbf{W}^T$ 이고 $\mathbf{WW^T} = \mathbf{I}$

이어야 한다는 얘기가 됩니다. 직교행렬(orthogonal matrix)과 비슷한 조건인데, ${\small \mathbf{W^TW} = \mathbf{I}}$ 는 성립하지 않는다는 것이

다릅니다(주2).

주석 보기

따라서 식 (4)의 우변은 ${\small \mathbf{W^TWX}}$ 가 되는데, 이때 X를 ${\small \mathbf{X} = \mathbf{USV^T}}$ 로 SVD하면 더 쪼개지죠.
또한, [식 (4) = 식 (2) = ${\small \hat{\mathbf{X}}}$ ]이므로, 아래와 같이 식 (6)을 얻을 수 있으며

(6) $\mathbf{W^TWUSV^T} = \mathbf{U}_k\mathbf{S}_k\mathbf{V}_k^T$

이를 풀면 최종적으로 식 (7)과 같이 답을 얻을 수 있습니다(주3). 식 (7)에서 Q는 크기가 k*k인 임의의 직교행렬을 의미합니다.

(7) $\mathbf{W = QU}_k^T$

주석 보기

즉, U 앞에 곱해지는 행렬이 직교행렬이라면, 무엇을 곱하든 최적의(= 정보 손실을 최소화 하는) 압축 변환 행렬 W를 얻을 수 있습니다. ambiguity가 있다는 거죠. 하지만 Q가 달라짐으로 해서 나타나는 변화는, 기껏해야 W가 span하는 공간의 좌표계가 회전(rotation)하거나 좌표축의 순서가 바뀌는(permutation) 정도 뿐입니다. 만약 우리 목적이 X로부터 추상화된 의미를 뽑아내는 것이라면 Q를 설정하는 것이 중요한 문제가 되겠지만, 목적이 압축일 때는 Q를 어떻게 잡든 전혀 영향을 주지 않습니다. 따라서 식 (7)의 Q에 단위행렬을 대입하여(단위행렬도 직교행렬이죠) 아래와 같은 결과를 얻을 수 있습니다.

(8) $\mathbf{W} = \mathbf{U}_k^T$

결론적으로, 압축률이 [1 - k/m]일 때(즉, m*n 행렬을 k*n으로 압축), 복원된 행렬의 정보 손실을 최소화 하는 압축 및 복원 알고리즘은 아래와 같습니다.

준비 과정: X를 아래와 같이 singular value decomposition하여 U를 얻는다.
$\mathbf{X} = \mathbf{USV}^T$
압축
$\mathbf{Z} = \mathbf{U}_k^T\mathbf{X}$
복원
$\hat{\mathbf{X}} = \mathbf{U}_k\mathbf{Z}$

자... 이렇게 해서 알고리즘이 나왔네요. 식이 참 간단해 보이는데, complexity는 얼마나 되는 걸까요?
위의 알고리즘에서 가장 시간이 오래 걸리는 부분은, 아이러니하게도 '준비 과정' 부분입니다. 통상적인 알고리즘을 쓰게 되면, m*n 행렬(m > n) X를 SVD 하는 데에 ${\small \mathcal{O}(m^2 n)}$ 이 걸립니다.

하지만 우리가 원하는 건 모든 singular vector가 아니죠. singular value가 가장 큰 순서대로 k개의 벡터만 있으면 되니까요. 이럴 때는 time complexity를 꽤 많이 줄일 수 있습니다. 널리 쓰이는 방법으로는 Lanczos algorithm이 있는데, 이건 ${\small \mathcal{O}(mnk^2)}$ 이 걸립니다. 통상적인 알고리즘에 비해 훨씬 쓸만하죠!
뿐만 아니라, 이 분야는 정말 끊임없이 알고리즘이 나오는 분야여서, 보다 효율적인 알고리즘들도 하나하나 찾을 수 없을 정도로 많죠. (구글링을 해보니 첫 페이지부터 ${\small \mathcal{O}(mnk)}$ 짜리 알고리즘이 나오는군요;;)

마지막으로 구현에 대해 말씀드리고 글을 마치겠습니다. 압축과 복원 부분이야 그냥 행렬 곱셈이니까 구현이 어렵지 않고, SVD는 지원하는 공개 라이브러리들이 많으니 언어에 맞게 골라 사용하시면 됩니다.

C/C++: LAPACK이 널리 쓰입니다(Redhat Linux, Windows). 또한, 단순히 SVD를 위해 쓰기는 다소 무겁지만 OpenCV도 아주 좋은 라이브러리입니다(이건 .NET도 지원합니다). OpenCV는 Visual Studio를 위해 프로젝트 파일(.sln, .proj)을 제공하며, 컴파일하려면 약간의 설정이 필요합니다.
Java: JAMA라는 라이브러리가 있습니다. 구현은 통상적인 알고리즘을 쓴 것 같습니다만, 설치/사용법이 아주 간편하고, 꼭 필요한 몇 개의 decomposition 방법들만 구현되어 있어 가볍습니다.
Ruby: linalg라는, LAPACK을 wrapping한 라이브러리를 추천합니다. JAMA와 마찬가지로 설치/사용법이 아주 간편합니다.

:

Posted by Kwang-sung Jun

2008. 1. 24. 15:07

vim 7.0 삽질예방/vim2008. 1. 24. 15:07

http://pelican7.egloos.com/1419616

http://happyoutlet.net/entry/vim-%EC%B4%88-%EA%B0%84%EB%8B%A8-%EB%A7%A4%EB%89%B4%EC%96%BC

#
*

: 현재 커서 밑에 있는 단어를 서치한다.

ctrl + O
tab

: 커서 위치 이동, 앞으로 가기, 뒤로가기.. (가끔씩 원하지 않게도 엉뚱한곳으로 점프되었을때 사용한다.)

] + i
] + I

-> 현재 파일 내에서 함수가 어디서 정의되었으며 어디서 호출되었는지를 보여준다.

:

Posted by Kwang-sung Jun

2008. 1. 22. 16:34

pthread 예제 삽질예방/pthread2008. 1. 22. 16:34



#include <STDIO.H>
#include <PTHREAD.H>
#include <SEMAPHORE.H>

void* PrintHelp(void* nothing);
void* PrintHelp2(void* nothing);

sem_t sem;

int main(void)
{
    pthread_t th1, th2;
    void* arg;

    sem_init(&sem, 0, 0); 

    pthread_create(&th1, NULL, PrintHelp, arg);
    pthread_create(&th2, NULL, PrintHelp2, arg);

    pthread_join(th2, NULL);
    pthread_join(th1, NULL);

    sem_destroy(&sem);

    return 0;
}

void* PrintHelp(void* nothing)
{
    sem_wait(&sem);
    printf("print help...\n");

    return 0;
}

void* PrintHelp2(void* nothing)
{
    getchar();
    printf("Print2Ended\n");
    sem_post(&sem);

    return 0;
}

:

Posted by Kwang-sung Jun

2008. 1. 22. 16:30

DbgPrint() 삽질예방/DbgPrint()2008. 1. 22. 16:30

#ifdef _DEBUG_
#define DbgPrint printf
#else
#define DbgPrint DummyPrintf
#endif

int DummyPrintf(const char *format, ...)
{ return 0; }

:

Posted by Kwang-sung Jun

2008. 1. 20. 15:08

리눅스 파티션나누기 작업 삽질예방/Linux2008. 1. 20. 15:08

파티션 매직을 이용하여 ext3를 생성하면 뭔가 문제가 있다. 속도가 느렸다. 심지어 리눅스에서 ntfs를 접근하는 것 보다도 드렸다 그래서 다음의 명령을 쓰길 추천한다.

gparted

apt-get으로 설치한 후 이용하면 된다.

파티션 설정할때는
먼저uuid를 알아야 하는데..(예전엔 장치이름만 알면되었으나 최근 바뀌었다고 한다, 파티션 생성할때마다 부여되는 번호인듯 하다.)
그건

vol_id /dev/sda7

<sda7>은 물론. 여러분이 마운트하고자 하는 하드웨어 장치파일이다.

다음 파티션 테이블을 수정하기/.

sudo vim /etc/fstab

fstab로부터 마운트 정보 다시 읽어오려면

mount -a

가끔은 재부팅을 한번 해야만 할 때가 있으니 조심하길 바랍니다.

보너스,, fstab에서 파일시스템의 속도 향상시키기...
<option>섹션에 삽입할것.

defaults,errors=remount-ro,noatime,data=writeback

data모드는 총 세가지인데 디폴트는 ordered라고 한다. 아마. remount-ro옵션은 rw+ordered인가... 리드온리일리는 없으니까.

파티션을 합칠면서도 자료를 읽지 않으려면

LVM

을 사용하라고 한다. 잘은 모르지만 궁금할땐 검색해 보자.

...
파티션 매직으로 파티션 나누었다가 한 7시간 정도는 삽질 하여 손해본 듯 하다.
이런 기분나쁜 삽질.....

:

Posted by Kwang-sung Jun

2008. 1. 16. 15:49

리눅스 폰트설정 삽질예방/Linux2008. 1. 16. 15:49

아래의 파일을 건드리고 난 후

sudo vim /usr/share/language-selector/fontconfig/ko_KR

다음명령을 실행시킨다.

sudo fc-cache

:

Posted by Kwang-sung Jun

2008. 1. 14. 21:28

파일에서 읽어오기 삽질예방/mysql2008. 1. 14. 21:28

comma separate value 파일에서 읽어오기

load data local infile './netflix_csv_data/mapping.csv' into
table <table_name>
fields terminated by ','
lines terminated by '\n'
(<col_1>, <col_2>);

:

Posted by Kwang-sung Jun

2008. 1. 13. 11:18

파이어 폭스 단축키 삽질예방/Firefox2008. 1. 13. 11:18

http://www.tech-faq.com/blog/master-firefox-shortcuts.html
번역본입니다.
직접 해보고 잘 안되는건 과감히 수정하였습니다. (혹시 안되는거 발견하면 코멘트 달아주세요>

URL 선택 = CTRL + L
북마크 생성= CTRL + D
탭 담기 = CTRL + W
주소에 .com 추가 = CTRL + “Enter”
주소에 .net 추가 = SHIFT + “Enter”
주소에 .org 추가 = CTRL + SHIFT +” Enter”
페이지 앞으로 = ALT + -> or just SHIFT + “Spacebar”
페이지 뒤로 = ALT + <- or just "Spacebar"
페이지 내에서 링크찾기 = ' (single quote)
페이지 내에서 찾기 = CTRL + F
페이지 새로고침 = CTRL + R
줌 인= CTRL + "+"
줌 아웃= CTRL + "-"
줌 레벨 초기값 = CTRL + 0
히스토리 = CTRL + H
홈페이지 = Alt + Home key
새 탭 생성 = CTRL + T
탭 선택(1...9)= ALT + [1..9]
새 창 = CTRL + N
새 이름으로 페이지 저장 = CTRL + S
소스 보기 = CTRL + U
웹 검색하기 = CTRL + K

:

Posted by Kwang-sung Jun

2008. 1. 10. 13:24

제안서 작성요령 삽질예방/제안서 쓰기2008. 1. 10. 13:24

<프로젝트 제목>
<주의 : ppt에 작성할 때, 반드시 첫 페이지는 목차로 시작, 끝맺음은 Q&A로 끝맺어야 한다.>

1. 해결하고자 하는 문제점에 대한 설명

2. 해결책은 어떻게 이 문제에 접근하는가?

3. 일반 유저의 시나리오와 어떻게 이 프로젝트를 사용할 수 있는가?

4. 프로젝트가 IT Festival 의 주제와 어떻게 연관이 되는지를 설명

5. 왜 <특정 기술> 이 프로젝트에 필요한지를 설명

6. 솔루션 컴포넌트의 다이어그램과 어떻게 상호 작용하는지를 보인다.

7. 팀이 어떻게 조직되었고, 업무는 어떻게 분담되었는지를 설명한다.

8. 프로젝트의 현재 상태에 대한 설명 (아이디어 상태인지, 프로토타입을
만들었는지. 특정 상황에서 실제 작동하는지)

9. 프로젝트가 향후에 어떤 모습을 보일 것인가?

10. 왜 IT Festival에 출전해야만 하는가?

11. 본 프로젝트의 완성이 가져올 파장에 대한 환상을 심어주며 종료.

:

Posted by Kwang-sung Jun

2008. 1. 9. 17:57

mysql admin 비번바꾸기 삽질예방/mysql2008. 1. 9. 17:57

mysqladmin -u root -p password <바꿀암호>

그동안 -p를 안붙이는 바람에 못하고 있었다.

:

Posted by Kwang-sung Jun

달력

« 2024/4 »

'삽질예방'에 해당되는 글 46건

SVD와 압축 삽질예방/SVD2008. 1. 28. 00:29

vim 7.0 삽질예방/vim2008. 1. 24. 15:07

pthread 예제 삽질예방/pthread2008. 1. 22. 16:34

DbgPrint() 삽질예방/DbgPrint()2008. 1. 22. 16:30

리눅스 파티션나누기 작업 삽질예방/Linux2008. 1. 20. 15:08

리눅스 폰트설정 삽질예방/Linux2008. 1. 16. 15:49

파일에서 읽어오기 삽질예방/mysql2008. 1. 14. 21:28

파이어 폭스 단축키 삽질예방/Firefox2008. 1. 13. 11:18

제안서 작성요령 삽질예방/제안서 쓰기2008. 1. 10. 13:24

mysql admin 비번바꾸기 삽질예방/mysql2008. 1. 9. 17:57

까먹을때 참고하기 위한 공간

카테고리

공지사항

태그목록

최근에 올라온 글

최근에 달린 댓글

글 보관함

링크

티스토리툴바