선택한 단어 수는 입니다.
최소 단어 이상 선택하여야 합니다.
최소 단어 이상 선택하여야 합니다.
선택한 단어 수는 30입니다.
최대 10 단어까지만 선택 가능합니다.
최대 10 단어까지만 선택 가능합니다.
문제 정의
- 한손으로 사용할 수 있는 키패드 디자인은 모바일 기기에서 사용하는 키패드와 매우 유사하다. 논문에서는 유전 알고리즘을 사용했는데 빠르게 평가하기 위한 방법을 고안했다. 평가방법은 가중치를 주는 k-gram 방식을 사용했는데 각 키에서의 위치에 따라 가중치를 주고, k개의 문자를 하나의 집합으로 보고 이 집합의 알파벳이 같은 키에 들어있으면 가중치를 주었다.
- 본 논문에서 사용하는 방식은 키 배치만을 조절하여 효율적인 키패드를 만드는 것이다. 소프트웨어적인 방법을 고려하지 않기 때문에 누르는 방식은 멀티탭 방식을 따른다.
- 본 논문은 멀티탭 방식을 기반으로 일반적인 영문 데이터가 입력될 때 필요한 키 누름 횟수를 최소화하는 키패드를 디자인했다. 8개에서 12개까지의 키를 사용하고, 알파벳 순서를 유지한 키패드 디자인과 랜덤한 순서의 키패드 디자인을 구했다.
- 기존의 T9 기반의 키패드디자인, Alphabetic 기반의 키패드와 비교해 결과를 보여줬다. 본 논문은 이전 연구를 확장하여 키의 개수, 입력데이터 종류, 알파벳 순서 유지 여부의 제약사항을 더 다양화하며 최적의 키패드 디자인을 찾고자 한다.
- 본 논문은 누르는 횟수를 최소화하는 키패드를 디자인하기 위해 동적 프로그래밍 방법을 이용했다. 이 동적 프로그래밍은 키를 누르는 횟수를 줄이기 위해서 자주 사용되는 알파벳을 각 키의 앞쪽에 위치시키는 것이 목적이다. 알파벳의 등장 횟수를 빈도(frequency)라고 정의하고 SMS 리스트에서 각 알파벳의 빈도를 구한다.
제안 방법
- 본 논문은 멀티탭 방식을 기반으로 일반적인 영문 데이터가 입력될 때 필요한 키 누름 횟수를 최소화하는 키패드를 디자인했다. 8개에서 12개까지의 키를 사용하고, 알파벳 순서를 유지한 키패드 디자인과 랜덤한 순서의 키패드 디자인을 구했다. 키패드 디자인을 생성하기 위한 방법으로 동적 프로그래밍, 유전 알고리즘, 그리고 그 둘의 결합(combination) 방법을 제안했다.
- 각 데이터 집합은 SMS 메시지, 문어(written english), 구어(spoken english), 논문, 사전으로 각 상황에 따른 영문 데이터를 바탕으로 실험했다. SMS 메시지는 하나는 정형화된 데이터를 모아둔 사이트에서 SMS 리스트를 추출했고[8], 싱가포르 국립대학에서 연구 목적으로 조사한 SMS 리스트에서도 데이터를 추출했다[7].
- 각 데이터는 사이즈가 일정하지 않다. 결과를 한 눈에 비교하기 위해 총 데이터의 크기로 결과 값을 나누어 정규화 한다.
- 실험 데이터는 자주 사용하는 SMS 데이터와 싱가포르 국립대학(National University of Singapore)에서 연구 목적으로 조사한 SMS 데이터를 사용해 테스트했다[7]. 기존의 T9 기반의 키패드디자인, Alphabetic 기반의 키패드와 비교해 결과를 보여줬다. 본 논문은 이전 연구를 확장하여 키의 개수, 입력데이터 종류, 알파벳 순서 유지 여부의 제약사항을 더 다양화하며 최적의 키패드 디자인을 찾고자 한다.
- 알파벳 순서를 유지하지 않은 키패드는 기존의 동적 프로그래밍 방법은 사용하지 않고 새로운 유전 알고리즘을 제안한다. 기존의 이진 표현 대신 순열 표현을 사용하고 이에 맞게 교차방법은 PMX를 사용한다. 단지 순서만 바뀌는 것으로 키에 알파벳을 배치하는 것을 결정할 수 없다.
- 네 번째 테스트는 GAKD와 FKD를 키의 개수와 데이터에 따라 비교한다. GAKD를 통해 생성된 키패드 디자인은 표 5와 같다.
- 대문자와 소문자를 구분해 계산하였다. 대문자를 사용하다가 소문자를 사용하기 위해서는 함수키를 한 번 누르면 되기 때문에 누르는 키 횟수를 한 번 늘리는 것으로 처리했다.
- 그림 6은 일련의 연산을 그림으로 표현한 것이다. 돌연변이 연산은 임의의 두 알파벳의 위치를 교환하는 방법을 사용했다. 두 알파벳의 위치를 교환하면 중복된 유전자가 생성되지 않는 장점이 있다.
- 두 번째 테스트는 각 데이터를 8개에서 12개까지 키 개수를 바꿔가며 동적 프로그래밍과 유전 알고리즘을 비교했다. 각 조건에서 생성된 키패드 디자인은 표 4와 같고 각 값을 비교한 결과가 그림 8의 차트에 주어진다.
- T9이 8개의 키에 알파벳이 순서대로 있는 것에 착안해 기존의 사람들이 이것에 익숙해져 있음을 전제로 하고 각 키에서 자주 사용하는 알파벳을 키의 앞쪽으로 배치했다. 반복해서 키를 누르는 것을 최소화하기 위해 이런 방법을 사용했다. 이것은 미국식 키패드에 익숙한 사용자에게 유용한 방법이다.
- 본 논문에서 제안한 유전 알고리즘은 알파벳 순서로 배치하는 키패드 디자인과 알파벳 순서를 지키지 않고 배치하는 키패드 디자인으로 나눠진다. 두 키패드 디자인 모두 Sastry의 유전 알고리즘 툴 박스를 사용했다[12].
- 만들어진 자식 해는 알파벳의 순서만을 가지고 있을 뿐 각 알파벳이 어느 키에 들어가야 하는지는 정해지지 않았다. 본 논문에서는 구분자를 정해주기 위해 4.1절의 동적 프로그래밍 방식을 유전 알고리즘 내부에 적용했다. 자식 해를 동적 프로그래밍을 이용해 배치해주는 것이다.
- 하지만 숙련도와 개인의 차이가 존재하기 때문에 객관적 자료로 사용하기는 어렵다. 본 논문에서는 데이터 입력에 필요한 실제 키를 누르는 총 횟수를 세어 비교하기로 한다. 이를 위해 다음 몇 가지 규칙에 따라 움직인다.
- 빈도를 이용한 동적 프로그래밍과 유전 알고리즘이 결과 차이를 보이는 주된 이유는 단어와 문장 구조 때문이다. 본 논문은 같은 키에 존재하는 알파벳이 연속으로 나올 때 카운트를 하나 추가한다. 대소문자가 변경될 때에도 카운트를 하나 추가해 준다.
- 재귀호출은 같은 호출을 여러 번 반복하는 경우가 발생하는데 이 재귀적 중복을 해소한 방법이 동적 프로그래밍이다[9]. 본 논문은 누르는 횟수를 최소화하는 키패드를 디자인하기 위해 동적 프로그래밍 방법을 이용했다. 이 동적 프로그래밍은 키를 누르는 횟수를 줄이기 위해서 자주 사용되는 알파벳을 각 키의 앞쪽에 위치시키는 것이 목적이다.
- 계속해서 같은 키를 누르는 경우 다음 알파벳으로 입력 문자가 바뀌기 때문에 일반적으로 일정한 시간을 대기하거나 다음 위치로 이동할 수 있는 키를 눌러야 한다. 본 논문은 이동키를 눌러 입력을 마무리하는 것으로 처리해 키를 누르는 횟수를 한 번 늘리는 방식으로 처리했다. 문자를 입력하는 도중 공백문자를 입력하기 위해서는 문자입력을 위한 이동키를 한 번 누르고 다시 공백을 위해 이동키를 한 번 더 눌러야 한다.
- 키패드 디자인을 생성하기 위한 방법으로 동적 프로그래밍, 유전 알고리즘, 그리고 그 둘의 결합(combination) 방법을 제안했다. 생성된 키패드 디자인은 SMS, 구어, 문어, 논문, 사전 데이터를 이용해 실제 눌러진키 횟수를 구해 값을 비교했다. 비교 대상은 기존의 키패드 디자인과 기존 논문에서 설계된 키패드 디자인, 빈도 기반 키패드 디자인, 그리고 본 논문에서 제안한 방법의 결과이다.
- 세 번째 테스트는 기존의 연구 결과를 그와 같은 키의 개수를 가지는 GAKD와 FKD의 결과와 비교한다. GAKD는 4.
- 키패드를 디자인하기 위해 동적 프로그래밍과 유전 알고리즘 방법을 제안한 알파벳 순서를 유지한 키패드는 저자들의 이전 학술대회 논문[4]에 사용된 방법에 데이터의 종류와 키의 개수를 변화시킨 다양한 결과를 도출한다. 알파벳 순서를 유지하지 않은 키패드는 기존의 동적 프로그래밍 방법은 사용하지 않고 새로운 유전 알고리즘을 제안한다. 기존의 이진 표현 대신 순열 표현을 사용하고 이에 맞게 교차방법은 PMX를 사용한다.
- 단지 순서만 바뀌는 것으로 키에 알파벳을 배치하는 것을 결정할 수 없다. 유전 알고리즘을 통해 구한 자식 해에 동적 프로그래밍을 적용해 키패드 배치를 결정하고 이를 평가한다.
- 두 키패드 디자인 모두 Sastry의 유전 알고리즘 툴 박스를 사용했다[12]. 일반적인 목적으로 사용되는 유전 알고리즘을 지원하는 이 라이브러리를 목적에 맞게 하기 위해 두 경우로 나누어 각각 파라미터를 설정했다. 표 2는 알파벳 순서 유지 키패드 디자인을 위한 파라미터 값이다.
- 첫 번째 테스트는 알파벳 순서를 유지한 키패드 디자인을 기존의 알려진 키패드 디자인과 비교했다.
- 8개에서 12개까지의 키를 사용하고, 알파벳 순서를 유지한 키패드 디자인과 랜덤한 순서의 키패드 디자인을 구했다. 키패드 디자인을 생성하기 위한 방법으로 동적 프로그래밍, 유전 알고리즘, 그리고 그 둘의 결합(combination) 방법을 제안했다. 생성된 키패드 디자인은 SMS, 구어, 문어, 논문, 사전 데이터를 이용해 실제 눌러진키 횟수를 구해 값을 비교했다.
- 예를 들면 “ghi"가 할당된 키에서 ‘i'라는 문자를 입력하기 위해서는 키를 3번 눌러야 한다. 키패드를 디자인하기 위해 동적 프로그래밍과 유전 알고리즘 방법을 제안한 알파벳 순서를 유지한 키패드는 저자들의 이전 학술대회 논문[4]에 사용된 방법에 데이터의 종류와 키의 개수를 변화시킨 다양한 결과를 도출한다. 알파벳 순서를 유지하지 않은 키패드는 기존의 동적 프로그래밍 방법은 사용하지 않고 새로운 유전 알고리즘을 제안한다.
대상 데이터
- 문어는 뉴욕 타임즈의 2009년 2월 기사들을 데이터로 만들었다. 구어는 유명한 미국 드라마인 프렌즈(friends)의 대본을 데이터로 만들었다. 논문과 사전은 표준적인 논문과 영어사전을 바탕으로 데이터를 생성했다.
- SMS 메시지는 하나는 정형화된 데이터를 모아둔 사이트에서 SMS 리스트를 추출했고[8], 싱가포르 국립대학에서 연구 목적으로 조사한 SMS 리스트에서도 데이터를 추출했다[7]. 문어는 뉴욕 타임즈의 2009년 2월 기사들을 데이터로 만들었다. 구어는 유명한 미국 드라마인 프렌즈(friends)의 대본을 데이터로 만들었다.
- 생성된 키패드 디자인은 SMS, 구어, 문어, 논문, 사전 데이터를 이용해 실제 눌러진키 횟수를 구해 값을 비교했다. 비교 대상은 기존의 키패드 디자인과 기존 논문에서 설계된 키패드 디자인, 빈도 기반 키패드 디자인, 그리고 본 논문에서 제안한 방법의 결과이다. 실험으로부터 유전 알고리즘을 통해 생성된 키패드 디자인이모든 경우에 가장 좋은 성능을 보이는 것을 알 수 있었다.
- 키패드 디자인을 생성하기 위해 동적 프로그래밍과 유전 알고리즘을 사용했다. 실험 데이터는 자주 사용하는 SMS 데이터와 싱가포르 국립대학(National University of Singapore)에서 연구 목적으로 조사한 SMS 데이터를 사용해 테스트했다[7]. 기존의 T9 기반의 키패드디자인, Alphabetic 기반의 키패드와 비교해 결과를 보여줬다.
- 우리는 문자 이외의 기호들은 공백으로 취급한다. 실험을 위한 문장은 실제 영어권에서 사용하는 데이터를 사용한다.
- 키의 개수는 8개에서 12개까지로 제한한다. 알파벳만을 실험대상으로 한정한다. 문자를 입력하다 보면 여러 가지 다른 기호들이 들어갈 수 있는데 이는 각 휴대폰마다 다르게 설정되어 있다.
데이터처리
- 논문에서는 유전 알고리즘을 사용했는데 빠르게 평가하기 위한 방법을 고안했다. 평가방법은 가중치를 주는 k-gram 방식을 사용했는데 각 키에서의 위치에 따라 가중치를 주고, k개의 문자를 하나의 집합으로 보고 이 집합의 알파벳이 같은 키에 들어있으면 가중치를 주었다. 이는 연속된 문자가 같은 키에 존재하면 이동키를 눌러주는 행동을 계산해 준 것이다.
이론/모형
- 제안한 방법과 비교하기 위한 키패드 디자인은 Less-tap[6], k-gram[5], KOGA (Keyboard Optimization using Genetic Techniques)[13]이다. Less-tap은 빈도를, k-gram과 KOGA 는 유전 알고리즘을 사용했다. 그림 9를 통해 각 값을 비교해 볼 수 있다.
- 이렇게 생성된 부모 해를 교차와 돌연변이 연산을 통해 자식 해를 생성한다. 교차방식은 PMX(partially matched crossover) 방식을 사용했다[10]. PMX는 염색체가 순열로 표시되는 경우에 사용되는 잘 알려진 교차 방식이다.
- 본 논문에서 제안한 유전 알고리즘은 알파벳 순서로 배치하는 키패드 디자인과 알파벳 순서를 지키지 않고 배치하는 키패드 디자인으로 나눠진다. 두 키패드 디자인 모두 Sastry의 유전 알고리즘 툴 박스를 사용했다[12]. 일반적인 목적으로 사용되는 유전 알고리즘을 지원하는 이 라이브러리를 목적에 맞게 하기 위해 두 경우로 나누어 각각 파라미터를 설정했다.
- 이를 위한 파라미터 값은 표 3과 같다. 알파벳 순서 유지 키패드 디자인은 유전자 표기를 위해 구분자를 주었지만 랜덤 순서 키패드 디자인은 이것이 불가능하기 때문에 알파벳을 1에서 26 사이의 값의 순열(permutation) 표현 방식을 사용했다. 예를 들면 ‘a’는 1이고 ‘z’는 26이다.
- FKD(Frequency-based Keypad Design)는 동적 프로그래밍 방법을 사용하지 못하기 때문에 새로 제안한 방법으로 가장 자주 나오는 알파벳을 정렬하여 각 키의 앞쪽부터 차례로 할당한 키패드 디자인이다. 제안한 방법과 비교하기 위한 키패드 디자인은 Less-tap[6], k-gram[5], KOGA (Keyboard Optimization using Genetic Techniques)[13]이다. Less-tap은 빈도를, k-gram과 KOGA 는 유전 알고리즘을 사용했다.
- 제약사항으로 8개 또는 9개의 키를 이용하고, 알파벳 순서를 유지했다. 키 입력 방식은 T9의 예측 방식이 아닌 멀티탭 방식을 사용했다. 키패드 디자인을 생성하기 위해 동적 프로그래밍과 유전 알고리즘을 사용했다.
- 키 입력 방식은 T9의 예측 방식이 아닌 멀티탭 방식을 사용했다. 키패드 디자인을 생성하기 위해 동적 프로그래밍과 유전 알고리즘을 사용했다. 실험 데이터는 자주 사용하는 SMS 데이터와 싱가포르 국립대학(National University of Singapore)에서 연구 목적으로 조사한 SMS 데이터를 사용해 테스트했다[7].
성능/효과
- T9KD와 AKD는 SMS에서 최적의 값을 보여준다. GAKD는 사전 데이터를 사용했을 때 가장 좋은 값을 가지는데 T9KD와 AKD 보다 각각 21%, 22% 개선했다. SMS 데이터를 사용할 때에도 T9KD보다 14%, AKD보다 17% 더 높은 성능을 보여준다.
- GAKD는 Less-tap을 SMS 데이터에서 4% 개선하고 있다. 각 데이터별로는 구어에서 5%, 문어는 8%, 논문과 사전에서는 9% 개선한다. GAKD는 k-gram을 9개 키에서 평균 2%, 10개 키에서 평균 5% 개선한다.
- 그림 10을 통해 각 조건에서의 성능을 비교할 수 있다. 데이터 종류에 따른 차이를 보면 GAKD는 FKD를 평균적으로 SMS에서 1%, 구어에서 1.6%, 문어에서 1.7%, 논문에서 2.1%, 사전에서 1.6% 개선했다. 키의 개수별로 값을 보면 GAKD가 FKD를 평균적으로 8개 키에서는 2%, 9개 키는 1.
- 비교 대상은 기존의 키패드 디자인과 기존 논문에서 설계된 키패드 디자인, 빈도 기반 키패드 디자인, 그리고 본 논문에서 제안한 방법의 결과이다. 실험으로부터 유전 알고리즘을 통해 생성된 키패드 디자인이모든 경우에 가장 좋은 성능을 보이는 것을 알 수 있었다. 키의 개수가 증가하면 한 키에 바인딩 되는 알파벳의 수가 줄기 때문에 큰 성능 개선을 얻을 수는 없었지만 제안한 유전 알고리즘을 이용하여 각 상황에 따라 최적의 키패드를 디자인할 수 있다는 것이 본 논문의 성과이다.
- 실험으로부터 유전 알고리즘을 통해 생성된 키패드 디자인이모든 경우에 가장 좋은 성능을 보이는 것을 알 수 있었다. 키의 개수가 증가하면 한 키에 바인딩 되는 알파벳의 수가 줄기 때문에 큰 성능 개선을 얻을 수는 없었지만 제안한 유전 알고리즘을 이용하여 각 상황에 따라 최적의 키패드를 디자인할 수 있다는 것이 본 논문의 성과이다.
- 6% 개선했다. 키의 개수별로 값을 보면 GAKD가 FKD를 평균적으로 8개 키에서는 2%, 9개 키는 1.9%, 10개 키는 1.8%, 11개 키는 1.2%, 12개 키는 1% 개선했다. 키의 개수가 증가할수록 개선율이 줄어드는데이는 한 키에 바인딩 되는 알파벳이 줄어들어 같은 키를 반복하여 누르는 횟수가 줄기 때문이다.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.