TSP 경로탐색을 위한 S-MINE 알고리즘

황숙희 ( Sook Hi Hwang ) , 원일용 ( Il Yong Weon ) , 고성범 ( Sung Bum Ko ) , 이창훈 ( Chang Hoon Lee )  한국정보처리학회, 정보처리학회논문지B [2011] 제18권 제2호, 73~82페이지(총10페이지)

메타 휴리스틱 알고리즘을 이용해 TSP (Traveling Salesman Problem) 문제를 풀고자 하는 많은 시도가 이루어지고 있다. TSP 문제는 대표적인 NP_Hard 문제로 탐색 알고리즘이나 최적화 알고리즘을 실험하는데 많이 사용되고 있으며, 복잡한 사회의 많은 문제들의 표준 모델로 제시되고 있다. 본 논문에서는 2009년 제안된 MINE 알고리즘을 TSP 에 적용시켜 메타 휴리스틱 알고리즘으로서의 탐색성능을 알아보고자 하였다. 이에 S-MINE (Search -MINE) 알고리즘을 제안하였으며, TSP 에 적용하여 그 결과를 고찰하였다.

TAG 메타 휴리스틱 알고리즘, 탐색 알고리즘, 순회판매원문제, Meta Heuristic Algorithm, Search Algorithm, Traveling Salesman Problem

모바일 퍼스널 어시스턴트의 지능 행위 구현을 위한 스마트 스크립트 시스템

김인철 ( In Cheol Kim ) , 오휘경 ( Hui Kyoung Oh )  한국정보처리학회, 정보처리학회논문지B [2011] 제18권 제2호, 83~86페이지(총4페이지)

본 논문에서는 동적 모바일 컴퓨팅 환경에 적합한 계획 실행 모델을 제시하고, 이 모델에 기초해 개발된 스마트 스크립트 시스템을 소개한다. 이 스마트 스크립트 시스템은 모바일 퍼스널 어시스턴트의 작업 지식을 기술하는 스마트 스크립트 언어와 스크립트들을 작업 목표와 환경 변화에 따라 동적으로 실행하는 실행 엔진 등을 포함한다. 또한, 본 논문에서는 스마트 스크립트 시스템의 유용성과 성능을 평가하기 위해 응용 서비스인 Smart Reservation를 구현하고, 실험을 전개한 결과를 소개한다.

TAG 모바일 퍼스널 어시스턴트, 계획 실행 모델, 스마트 스크립트 언어, 실행 엔진, Mobile Personal Assistant, Plan Execution Model, Smart Script Language, Execution Engine

한국어 자모 Viable Prefix를 이용한 외래어 표기 교정 기법

권순호 ( Soon Ho Kwon ) , 권혁철 ( Hyuk Chul Kwon )  한국정보처리학회, 정보처리학회논문지B [2011] 제18권 제2호, 87~92페이지(총6페이지)

한국어 문서에서 외래어 표기는 한 단어에 대해 한 개만 존재하는 것이 아니라 여러 개의 다른 표기로 사용되고 있다. 이러한 표기상 불일치는 하나의 단어가 다른 개념으로 인식되어 정보 검색 시스템의 성능 저하의 원인이 된다. 따라서 정보 검색 시스템에서는 다양한 외래어 표기에 대해 같은 개념으로 인식하여 검색할 수 있도록 외래어 표기법에 맞는 외래어 표기로 교정하는 전처리가 필요하다. 본 논문에서는 질의어로 외래어가 입력되면, 이를 근거로 외래어 표기법에 맞는 외래어 표기로 교정해주는 방법을 제안한다. 제안하는 기법은 한국어 자모의 viable prefix를 이용하여 후보 외래어 표기를 생성하는 가상 트리를 작성하고 불필요한 외래어를 가지치기함으로써 검색 정확도를 높이고 속도를 개선한다.

TAG 외래어 표기, 정보 검색, 음성적 유사도, Writing of Loanword, Information Retrieval, Viable Prefix, Phonetic Similarity

확장된 벡터 공간 모델을 이용한 한국어 문서 분류 방안

이상곤 ( Sang Kon Lee )  한국정보처리학회, 정보처리학회논문지B [2011] 제18권 제2호, 93~108페이지(총16페이지)

본 논문에서는 한국어 문서의 분류 정밀도 향상을 위해 애매어와 해소어 정보를 이용한 확장된 벡터 공간 모델을 제안하였다. 벡터 공간 모델에 사용된 벡터는 같은 정도의 가중치를 갖는 축이 하나 더 존재하지만, 기존의 방법은 그 축에 아무런 처리가 이루어지지 않았기 때문에 벡터끼리의 비교를 할 때 문제가 발생한다. 같은 가중치를 갖는 축이 되는 단어를 애매어라 정의하고, 단어와 분야 사이의 상호정보량을 계산하여 애매어를 결정하였다. 애매어에 의해 애매성을 해소하는 단어를 해소어라 정의하고, 애매어와 동일한 문서에서 출현하는 단어 중에서 상호 정보량을 계산하여 해소어의 세기를 결정하였다. 본 논문에서는 애매어와 해소어를 이용하여 벡터의 차원을 확장하여 문서 분류의 정밀도를 향상시키는 방법을 제안하였다.

TAG 벡터 공간 모델, 애매어, 해소어, 전치 인덱스 방법, 상호정보량, 문서분류, 정보검색, Vector Space Model, Ambiguous Word, Disambiguous Word, Transposed Index Method, Mutual Information, Document Classification, Information Retrieval

차이값 히스토그램 기반 가역 워터마킹의 행열 교차 스캐닝을 통한 성능 향상 기법

여동규 ( Dong Gyu Yeo ) , 김병만 ( Byeong Man Kim ) , 이해연 ( Hae Yeoun Lee )  한국정보처리학회, 정보처리학회논문지B [2011] 제18권 제1호, 1~10페이지(총10페이지)

가역 워터마킹 기법은 디지털 콘텐츠에 지각적 투명성을 유지하며 워터마크를 삽입한 후, 이를 아무런 손상없이 원본 상태로 복원할 수 있는 메시지 은닉 수단으로서 높은 품질과 높은 삽입용량이 요구되는 분야에서 다양하게 이용되어질 수 있다. 본 논문에서는 차이값 히스토그램 기반의 가역 워터마킹에서 응용분야의 요구에 맞게 높은 삽입용량을 제공하기 위한 효율적인 반복삽입 알고리즘을 제안한다. 제안한 방법에서는 메시지가 삽입된 영상에 대하여 반복삽입할 때, 지역성을 최대한 활용하기 위하여 행열 교차 스캐닝 방법을 이용하였다. 다양한 영상들에 대하여 비교 분석한 실험 결과에 따르면 제안한 알고리즘은 완전한 가역성과 함께 낮은 왜곡을 유지하면서도 효율적인 반복삽입을 통한 높은 삽입용량을 얻을 수 있었다.

TAG 가역 워터마킹, 차이값 히스토그램, 히스토그램 쉬프팅, 행열 교차 스캐닝, Reversible Watermarking, Differential Histogram, Histogram Shifting, Row-Column Cross Scanning

상반신 포즈 추적을 위한 키포즈 기반 예측분포

오치민 ( Chi Min Oh ) , 이칠우 ( Chil Woo Lee )  한국정보처리학회, 정보처리학회논문지B [2011] 제18권 제1호, 11~20페이지(총10페이지)

Pictorial Structures(PS)는 동적 프로그래밍을 이용하여 인체의 포즈 추적 및 인식 하는 것에 매우 효과적인 방법으로 알려져 있다. 본 논문에서 상반신 포즈는 PS와 Particle filter(PF)에 의한 동적 프로그래밍 기법으로 추적된다. PF와 같은 동적프로그래밍에서 마코프 연쇄 (Markov Chain) 기반 동적 움직임 모델은 높은 자유도를 갖는 상반신 포즈를 예측하기 어려운 단점이 있다. 본 논문에서 제안하는 방법은 키포즈 기반 예측분포이며, 이것은 상반신 실루엣과 키포즈(Key Pose)들 사이의 유사도를 참고하여 파티클(Particle)을 적절히 예측하는 것이다. 실험 결과를 통해 제안된 방법은 기존 방법 성능을 70.51% 향상시킨 것을 확인하였다.

TAG 상반신 포즈, 그림 구조체, 파티클필터, 예측분포, 키포즈, Upper Body Pose, Pictorial Structures, Particle Filter, Proposal Distribution, Key Poses

얼굴 깊이 추정을 이용한 3차원 얼굴 생성 및 추적 방법

주명호 ( Myung Ho Ju ) , 강행봉 ( Hang Bong Kang )  한국정보처리학회, 정보처리학회논문지B [2011] 제18권 제1호, 21~28페이지(총8페이지)

얼굴의 3차원 정보는 얼굴 인식이나 얼굴 합성, Human Computer Interaction (HCI) 등 다양한 분야에서 유용하게 이용될 수 있다. 그러나 일반적으로 3차원 정보는 3D 스캐너와 같은 고가의 장비를 이용하여 획득되기 때문에 얼굴의 3차원 정보를 얻기 위해서는 많은 비용이 요구된다. 본 논문에서는 일반적으로 손쉽게 얻을 수 있는 2차원의 얼굴 영상 시퀀스로부터 효과적으로 3차월 얼굴 형태를 추적하고 재구성하기 위한 3차원 Active Appearance Model (3D-AAM) 방법을 제안한다. 얼굴의 3차원 변화 정보를 추정하기 위해 학습 영상은 정면 얼굴 포즈로 다양한 얼굴 표정 변화를 포함한 영상과 표정 변화를 갖지 않으면서 서로 크게 다른 얼굴 포즈를 갖는 영상으로 구성한다. 입력 영상의 3차원...

TAG 3D 얼굴 인식, 3D 얼굴 추적, 얼굴 모델링, 3D 얼굴 형태, 3D AAM, Face Modeling, 3D Face Shape

조건부 계획수립을 위한 효과적인 그래프 기반의 휴리스틱

김현식 ( Hyun Sik Kim ) , 김인철 ( In Cheol Kim ) , 박영택 ( Young Tack Park )  한국정보처리학회, 정보처리학회논문지B [2011] 제18권 제1호, 29~38페이지(총10페이지)

계획 문제 명세로부터 영역-독립적인 휴리스틱을 유도해내기 위해서는 주어진 계획문제에 대한 간략화와 간략화된 계획문제에 대한 해 도출 과정이 요구된다. 본 논문에서는 초기 상태의 불확실성과 비결정적 동작 효과를 모두 포함한 조건부 계획문제를 풀기 위한 새로운 융합 계획그래프와 이것을 이용한 GD 휴리스틱 계산법을 소개한다. 융합 계획그래프는 고전적 계획 문제 풀이를 위한 휴리스틱 계산에 이용되는 간략화된 계획그래프를 조건부 계획문제에 적용할 수 있도록 확장한 자료구조이다. 융합 계획그래프에서는 감지 동작과 비결정적 동작들을 포함한 조건부 계획 문제에 대한 휴리스틱을 얻기 위해, 전통적인 삭제 간략화외에도 감지 동작과 비결정적 동작들에 대한 효과-융합 간략화를 추가로 이용한다. 융합 계획 그래프 의 전향 확장과 병행적으로 진행되는 GD 휴리스틱 계산에서는 목...

TAG 조건부 계획수립, 믿음 상태 공간, 탐색 휴리스틱, 계획 그래프, Contingent Planning, Belief State Space, Search Heuristic, Planning Graph

휴리스틱에 의하여 개선된 반딧불이 알고리즘의 설계와 분석

이현숙 ( Hyun Sook Rhee ) , 이정우 ( Jung Woo Lee ) , 오경환 ( Kyung Whan Oh )  한국정보처리학회, 정보처리학회논문지B [2011] 제18권 제1호, 39~44페이지(총6페이지)

본 논문에서는 최근 Xin-She Yang에 의해 소개된 반딧불이 알고리즘(FA)에 휴리스틱을 적용하여 개선하는 방안을 제안한다. 또한 이를 위하여 기존의 FA를 이와 유사한 문제영역의 알고리즘인 Particle Swarm Optimization(PSO)와 정확도 측면, 수렴 시간 측면, 각 입자의 움직임 측면에서 비교 분석한다. 비교 실험 결과, FA의 정확도는 PSO보다 나쁘지 않았지만, 수렴 속도는 느린 것으로 나타났다. 본 논문은 이에 대한 직관적인 원인을 고찰하고, 이를 극복하기 위해, 기존의 FA에 부분 돌연변이 휴리스틱을 적용하여 개선된 FA(Improved FA)를 제안한다. 벤치마크 함수들을 최적화 하는 비교 실험 결과, 개선된 FA가 PSO와 기존의 FA보다 정확도와 수렴속도 측면에서 우수함을 보...

TAG 반딧불이 알고리즘, 입자군집 최적화, 부분 돌연변이, 자연계기반의 확률적 최적화, Firefly Algorithm, Particle Swarm Optimization, Partial Mutation, Nature-inspired Stochastic Optimization

기계학습에 기반한 한국어 미등록 형태소 인식 및 품사 태깅

최맹식 ( Maeng Sik Choi ) , 김학수 ( Hark Soo Kim )  한국정보처리학회, 정보처리학회논문지B [2011] 제18권 제1호, 45~50페이지(총6페이지)

한국어 형태소 분석에서 미등록 형태소 오류들은 2가지 유형으로 나뉜다. 첫 번째 오류 유형은 형태소 분석기가 어떤 형태소열도 찾아내지 못하는 것이고, 두 번째 오류 유형은 등록 형태소들의 잘못된 조합을 찾아내는 것이다. 지금까지 대부분의 기존 미등록 형태소 추정 기술들은 단지 첫 번째 오류 유형에만 초점을 맞추어 왔다. 본 논문에서는 2가지 유형의 오류들의 모두 다룰 수 있는 미등록 형태소 추정 방법을 제안한다. 제안 방법은 SVM(Support Vector Machine)을 이용하여 미등록 형태소 오류들을 포함할 가능성이 있는 어절들을 검출한다. 그리고 CRFs(Conditional Random Fields)를 이용하여 검출된 어절들의 형태소 분리와 품사 태깅을 수행한다. 실험에서 제안 방법은 기능어 최장 일치 기반의 전형적인 방법보다 뛰어난 성능을...

TAG 미등록 형태소 추정, 미등록 형태소 인식, 미등록 형태소 태깅, Unknown Morpheme Estimation, Unknown Morpheme Recognition, Unknown Morpheme Tagging

1  2  3  4  5  6  7  8  9  10