알고리즘 학습 이론

알고리즘 학습 이론은 기계 학습 문제와 알고리즘을 분석하기 위한 수학적인 틀이다. 동의어에는 형식적인 학습 이론과 알고리즘적인 귀납 추론이^{[citation needed]} 포함된다. 알고리즘 학습 이론은 통계적 가정과 분석을 사용하지 않는다는 점에서 통계적 학습 이론과 다르다. 알고리즘 학습 이론과 통계 학습 이론 모두 기계 학습과 관련이 있으므로 컴퓨터 학습 이론의^{[citation needed]} 분과로 볼 수 있다.

구분특성

일반적으로 통계적 학습 이론과 대부분의 통계적 이론과는 달리 알고리즘 학습 이론은 데이터가 랜덤 표본, 즉 데이터 포인트가 서로 독립적이라고 가정하지 않는다. 이것은 언어 학습과 자동화된 과학적 발견과 같이 관찰이 (상대적으로) 소음은 없지만 무작위가 아닌 영역에 이 이론을 적합하게 만든다.^[2][3]

알고리즘 학습 이론의 기본 개념은 한계에서 학습하는 것이다: 데이터 포인트의 수가 증가함에 따라 학습 알고리즘은 문제 공간과 일치하는 모든 가능한 데이터 순서에 대한 정확한 가설로 수렴되어야 한다. 이것은 통계적 일관성의 비확률적 버전으로서, 한계에서 정확한 모델에 대한 수렴이 필요하지만, 학습자가 확률 측정값^{[citation needed]} 0으로 데이터 시퀀스에 실패하도록 허용한다.

알고리즘 학습 이론은 튜링 기계의 학습 능력을 조사한다. 다른 프레임워크에서는 예를 들어, 다항식 시간에 가설을 더 빨리 계산하는 학습자 등 튜링 머신보다 훨씬 제한된 수준의 학습 알고리즘을 고려한다. 그러한 틀의 예는 아마도 대략적으로 올바른 학습일^{[citation needed]} 것이다.

한계에서의 학습

이 개념은 E. Mark Gold의 세미날짜지 "Language Identification in the limit"^[4]에 소개되었다. 언어 식별의 목적은 한 프로그램을 실행하는 기계가 다른 프로그램을 개발할 수 있도록 하는 데 있으며, 주어진 문장을 시험하여 그것이 "문법적"인지 "문법적"인지를 결정할 수 있다. 배우고 있는 언어는 영어나 다른 자연어일 필요는 없다 - 사실 "문법적"의 정의는 시험관에게 절대적으로 알려진 것이 될 수 있다.

골드의 학습 모델에서 테스터는 각 단계에서 학습자에게 예문장을 주고, 학습자는 가설로 응답하는데, 이는 문법적 정확성을 판단하기 위한 제안 프로그램이다. 검사자는 가능한 모든 문장(문법적 또는 그렇지 않은 문장)이 결국 목록에 나타나도록 요구하지만, 특별한 순서는 요구되지 않는다. 학습자는 각 단계에서 가설이 지금까지의 모든 문장에 대해 정확해야 한다.^{[citation needed]}

특정 학습자는 그 가설이 더 이상 변하지 않는 일정 수의 단계가 있다면 "한계에 있는 언어를 배울 수 있다"고 한다.^{[citation needed]} 모든 가능한 문장은 입력의 순서(과거 또는 미래) 어디선가 나타나고 가설은 모든 입력(과거 또는 미래)에 대해 정확하기 때문에, 이 시점에서 그것은 정말로 언어를 배운 것이다. 따라서 가설은 모든 문장(과거 또는 미래)에 대해 정확하다. 학습자가 정확한 가설에 도달한 시점을 알 수 있어야 할 필요는 없으며, 필요한 것은 그것이 사실이라는 것뿐이다.

Gold는 튜링 머신 프로그램에 의해 정의되는 모든 언어는 열거법을 사용하는 또 다른 튜링 완성 기계에 의해 한계로 학습될 수 있다는 것을 보여주었다.^{[clarification needed]} 이는 학습자가 모든 가능한 튜링 머신 프로그램을 차례로 테스트하여 지금까지 올바른 프로그램이 발견될 때까지 수행되며, 이는 현재 단계에 대한 가설을 형성한다. 결국 올바른 프로그램에 도달하게 되고, 그 후에는 가설이 다시는 바뀌지 않게 된다(그러나 학습자는 그것이 바뀔 필요가 없다는 것을 알지 못한다는 점에 유의한다).

금은 또한 학습자에게 긍정적인 예(즉, 문법적이지 않은 문장이 아닌 문법적인 문장만이 입력에 나타난다)만 주어진다면, 언어에 가능한 문장의 수가 한정되어 있는 경우에만 언어의 학습을 보장할 수 있다는 것을 보여주었다(예를 들어, 문장을 아는 경우 이것이 가능하다).n 길이가 제한되어야 한다).^{[clarification needed]}

한계에 있는 언어 식별은 매우 추상적인 모델이다. 실전에 발생할 수 있는 런타임이나 컴퓨터 메모리의 제한을 허용하지 않으며, 입력에 오류가 있을 경우 열거 방법이 실패할 수 있다. 그러나 이 프레임워크는 매우 강력하다. 왜냐하면 이러한 엄격한 조건이 유지된다면 계산 가능하다고^{[citation needed]} 알려진 프로그램의 학습을 허용하기 때문이다. 이것은 튜링 머신 프로그램이 기존의 어떤 프로그래밍 언어에서 어떤 프로그램이라도 모방하도록 쓰여질 수 있기 때문이다. Church-Turing 논문을 참조하십시오.

기타 식별 기준

학습 이론가들은 다음과 같은 다른 학습 기준을 연구했다.^[5]

• 효율성: 정확한 가설로 수렴하기 전에 필요한 데이터 지점의 수를 최소화하십시오.
• 마음 변화: 수렴 전에 발생하는 가설 변화의 수를 최소화한다.^[6]

마인드 변화 한계는 통계 학습 이론에서 연구되는 실수 한계와 밀접한 관련이 있다.^[7] 케빈 켈리는 마음의 변화를 최소화하는 것은 오캄의 레이저의 의미에서 지극히 단순한 가설을 선택하는 것과 밀접한 관련이 있다고 제안했다.^[8]

연차회의

1990년 이후, 첫 해(1990–1997년)에 워크샵이라고 불리는 알고리즘 학습 이론에 관한 국제 컨퍼런스(ALT)가 있다.^[9] 1992년부터, 소송절차는 LNCS 시리즈와 함께 출판되었다.^[10] 31차 회의는 2020년 2월 샌디에이고에서 열린다.^[11]

참고 항목

• 형식 인식론
• 샘플 제외 치수

참조

외부 링크