학습 분류기 시스템

학습 분류기 시스템(LCS)은 발견 요소(예: 전형적으로 유전 알고리즘)와 학습 요소(감독된 학습, 강화 학습 또는 감독되지 않은 학습)를 결합한 규칙 기반 기계 학습 방법의 패러다임이다.^[2] 학습 분류자 시스템은 예측(예: 행동 모델링,^[3] 분류,^[4][5] 데이터 마이닝,^[5][6][7] 회귀,^[8] 함수 근사치 ^[9]또는 게임 전략)을 하기 위해 지식을 단편적으로 저장하고 적용하는 상황 의존적인 규칙 집합을 식별하려고 한다. 이 접근방식은 복잡한 솔루션 공간을 더 작고 단순한 부분으로 나눌 수 있게 한다.

학습 분류기 시스템의 배후에 있는 설립 개념은 규칙 기반의 에이전트를 사용하여 인공 인지 시스템(즉, 인공지능)을 형성함으로써 복잡한 적응 시스템을 모델링하려는 시도에서 비롯되었다.

방법론

주어진 학습 분류기 시스템의 구조와 구성요소는 상당히 가변적일 수 있다. LCS를 여러 개의 상호작용 구성요소로 구성된 기계로 생각하면 유용하다. 주어진 문제 영역(알고리즘 구성 블록과 같은)의 요구에 적합하게 또는 알고리즘을 다양한 문제 영역에서 작동할 수 있을 정도로 충분히 유연하게 만들기 위해 구성요소를 추가 또는 제거하거나 기존 구성요소를 수정/변경할 수 있다. 결과적으로, LCS 패러다임은 기계 학습을 요구하는 많은 문제 영역에 유연하게 적용될 수 있다. LCS 구현의 주요 구분은 (1) 미시간식 아키텍처 대 다음과 같다. 피츠버그 스타일 아키텍처,^[10] (2) 강화 학습 대 감독 학습, (3) 증분 학습 대 배치 학습, (4) 온라인 학습 대 오프라인 학습, (5) 강도 기반 피트니스 대 정확도 기반 피트니스, (6) 완전한 액션 맵핑 대 베스트 액션 맵핑. 이러한 분할이 반드시 상호 배타적인 것은 아니다. 예를 들어, 가장 잘 알려져 있고 가장 잘 연구된 LCS 알고리즘인 ^[11]XCS는 미시건식이며, 강화 학습을 위해 설계되었지만 또한 감독된 학습을 수행할 수 있으며, 온라인 또는 오프라인에서 가능한 증분 학습을 적용하고, 정확성에 기반한 적합성을 적용하며, 완전한 액션 맵핑을 생성하려고 한다.

일반 LCS 알고리즘의 요소

LCS는 특정 방법이 아닌 유전 기반 기계 학습의 패러다임임을 염두에 두고, 다음은 일반적인 현대적(즉, XCS 후) LCS 알고리즘의 핵심 요소를 개괄적으로 설명한다. 단순성을 위해 우리는 감독된 학습이 있는 미시간식 건축에 초점을 맞추도록 한다. 이 유형의 일반 LCS에 관련된 순차적 단계를 나열한 오른쪽의 그림을 참조하십시오.

환경

환경은 LCS가 배우는 데이터의 원천이다. 오프라인 유한 교육 데이터 세트(데이터 마이닝, 분류 또는 회귀 문제의 특성) 또는 라이브 교육 인스턴스의 온라인 순차 스트림일 수 있다. 각 훈련 인스턴스(instance)는 몇 가지 특징(속성 또는 독립 변수라고도 함)과 단일 관심 종점(class, action, 표현형, 예측 또는 종속 변수라고도 함)을 포함하는 것으로 가정한다. LCS 학습의 일부는 피쳐 선택을 포함할 수 있으므로, 훈련 데이터의 모든 피쳐가 유용한 것은 아니다. 인스턴스(instance)의 형상값 집합을 일반적으로 상태라고 한다. 단순성을 위해 Boolean/binary 피쳐와 Boolean/binary 클래스가 있는 문제 도메인의 예를 가정해 봅시다. 미시건식 시스템의 경우, 환경의 한 예는 각 학습 사이클(즉, 증분 학습)에 대해 훈련된다. 피츠버그식 시스템은 배치 학습을 수행하며, 여기서 규칙 집합은 훈련 데이터의 대부분 또는 전체에 걸쳐 각 반복을 평가한다.

규칙/분류기/인구

규칙은 상태 값과 일부 예측 사이의 상황에 따른 관계다. 규칙은 일반적으로 {IF:그러면} 식, (예: {IF '조건' THEN 'action'}, 또는 보다 구체적인 예로서 {IF '빨간색' AND '옥타곤' THEN 'stop-sign'}). LCS와 규칙 기반 기계 학습에서 모두 중요한 개념은 규칙이 조건이 충족될 때만 적용 가능하기 때문에 개별 규칙 자체가 모델이 아니라는 것이다. 규칙을 솔루션 공간의 "로컬 모델"이라고 생각해 보십시오.

규칙은 다양한 데이터 유형(예: 이진수, 이산수치, 순서형, 연속수치)을 처리하는 다양한 방법으로 나타낼 수 있다. 2진수 데이터의 경우 LCS는 전통적으로 3진수 규칙 표현을 적용한다(즉, 규칙은 데이터의 각 형상에 대해 0, 1 또는 '#'을 포함할 수 있다). '상관없음' 기호(예: '#')는 규칙을 허용하는 규칙의 조건 내에서 와일드 카드 역할을 하며, 시스템은 전체적으로 형상과 대상 끝점 사이의 관계를 일반화하여 예측하는 역할을 한다. 다음 규칙(#1###0 ~ 1)을 고려하십시오(즉, 조건 ~ 동작). 이 규칙은 다음과 같이 해석할 수 있다: 두 번째 형상이 1이고 여섯 번째 형상이 0이면 클래스 예측 = 1이다. 우리는 이 규칙에서 두 번째와 여섯 번째 특징이 명시되어 있는 반면 다른 것들은 일반화되었다고 말할 것이다. 이 규칙과 해당 예측은 규칙 조건이 인스턴스에서 충족되는 경우에만 해당 인스턴스에 적용할 수 있다. 이것은 더 흔히 일치라고 불린다. 미시건식 LCS에서는 각 규칙에는 자체 적합성뿐만 아니라, 존재하는 규칙의 복사본 수(숫자), 규칙의 나이, 정확성 또는 보상 예측의 정확성, 기타 서술적 또는 경험적 통계 등을 설명할 수 있는 여러 규칙 매개변수가 그것과 연관되어 있다. 그 매개변수와 함께 규칙을 분류기(classifier)라고 부르기도 한다. 미시건식 시스템에서 분류자는 사용자가 정의한 최대 분류자 수를 가진 모집단 [P] 내에 포함된다. 대부분의 확률적 검색 알고리즘(예: 진화 알고리즘)과는 달리 LCS 모집단은 비어 있는 상태로 시작한다(즉, 규칙 모집단을 무작위로 초기화할 필요가 없다). 분류자는 대신 커버 메커니즘으로 모집단에 처음 도입될 것이다.

모든 LCS에서 훈련된 모델은 단일 규칙/분류기가 아니라 규칙/분류기 집합이다. 미시건식 LCS에서는 훈련된(선택적으로 압축된) 분류자 전체 모집단이 예측 모델을 형성한다.

매칭

LCS에서 가장 중요하고 종종 시간이 많이 걸리는 요소 중 하나는 일치 과정이다. LCS 학습 주기의 첫 번째 단계는 환경에서 단일 교육 인스턴스를 가져와서 매칭이 이루어지는 [P]에 전달한다. 2단계에서 [P]의 모든 규칙을 교육 인스턴스와 비교하여 일치하는 규칙(즉, 현재 인스턴스와 컨텍스트적으로 관련됨)을 확인한다. 3단계에서는 모든 일치 규칙이 일치 집합 [M]으로 이동된다. 규칙 조건에 지정된 모든 형상값이 훈련 인스턴스의 해당 형상값과 동일한 경우 규칙은 훈련 인스턴스와 일치한다. 예를 들어, 교육 인스턴스가 (001001 ~ 0)이라고 가정할 때, 이러한 규칙은 (##0##### ~ 0), (00###1 ~ 0), (#01001 ~ 1)과 일치하지만, 이러한 규칙은 (1##########0) (#1#0 ~ 1)과 일치하지 않는다. 일치할 때 규칙에서 지정한 엔드포인트/행동은 고려되지 않는다는 점에 유의하십시오. 결과적으로, 매치 세트는 충돌하는 행동을 제안하는 분류자를 포함할 수 있다. 네 번째 단계에서는 감독 학습을 실시하고 있으므로 [M]을 올바른 세트[C]와 잘못된 세트[I]로 구분한다. 일치 규칙이 올바른 동작을 제안할 경우(훈련 인스턴스의 알려진 동작에 기초하여), 그렇지 않을 경우 [I]로 간다. 강화 학습 LCS에서는 올바른 동작을 알 수 없기 때문에 여기에서 대신 액션 세트 [A]가 형성될 것이다.

커버링

학습 주기의 이 시점에서, 분류자가 [M]이나 [C]로 만들지 않은 경우(인구가 빈 상태로 시작하는 경우처럼), 커버 메커니즘(5단계)이 적용된다. 커버링은 온라인 스마트 인구 초기화의 한 형태다. 덮는 것은 무작위로 현재의 훈련 사례와 일치하는 규칙을 생성한다(그리고 감독되는 학습의 경우, 그 규칙도 올바른 행동으로 생성된다). 교육 인스턴스가 (001001 ~ 0)인 경우, 커버를 적용하면 (#0#0## ~ 0), (001001 ~ 0), (#010### ~ 0) 규칙 중 하나가 생성될 수 있다. 커버링(covering)은 각 학습 주기에 [C]에 하나 이상의 올바른 일치 규칙이 있을 뿐만 아니라 모집단에 초기화되는 모든 규칙이 하나 이상의 훈련 인스턴스와 일치하도록 보장한다. 이는 LCS가 어떤 교육 인스턴스에도 일치하지 않는 규칙의 검색 공간을 탐색하는 것을 방지한다.

매개 변수 업데이트/학점 할당/학습

여섯 번째 단계에서는 [M]의 규칙 매개변수를 업데이트하여 현재 훈련 인스턴스에서 얻은 새로운 경험을 반영한다. LCS 알고리즘에 따라 이 단계에서 많은 업데이트가 발생할 수 있다. 감독된 학습을 위해 규칙의 정확성/오류만 간단히 업데이트할 수 있다. 규칙 정확도/오차는 전체 교육 데이터에 대해 계산되지 않고 일치하는 모든 인스턴스에 대해서만 계산되므로 모델 정확도/오류와는 다르다. 규칙 정확도는 규칙이 올바른 집합[C]에 있는 횟수를 일치 집합[M]에 있는 횟수로 나누어 계산한다. 규칙의 정확성은 '지역적 정확성'이라고 생각할 수 있다. 규칙 적합성 또한 여기서 업데이트되며, 일반적으로 규칙 정확도의 함수로 계산된다. 피트니스의 개념은 고전적인 유전 알고리즘에서 직접 취한다. LCS가 크레딧 할당 및 학습을 수행하기 위해 매개 변수를 업데이트하는 방법에는 여러 가지 차이가 있다는 점에 유의하십시오.

서브섬션

일곱 번째 단계에서는 일반적으로 서브섬프 메커니즘이 적용된다. Subsumption은 문제 공간의 중복 부분을 포괄하는 분류자를 병합하는 명시적 일반화 메커니즘이다. 서브섬 분류기는 서브섬 분류기를 효과적으로 흡수한다(그리고 그 숫자의 증가가 있다. 이는 소분류 분류기가 정확하듯이 보다 일반적일 때에만 발생할 수 있으며, 분류기가 소진하는 모든 문제 공간을 포괄한다.

규칙 탐색/유전자 알고리즘

8단계에서 LCS는 건강(적자 생존)을 바탕으로 부모 분류자 2명을 선발하는 고엘리트주의 유전 알고리즘(GA)을 채택한다. 부모는 일반적으로 토너먼트 선택을 사용하여 [C]에서 선택된다. 일부 시스템은 룰렛 휠 선택 또는 결정론적 선택을 적용했으며, [P] - 범용 선택 또는 [M]에서 상위 규칙을 다르게 선택했다. 크로스오버와 돌연변이 연산자는 이제 두 가지 새로운 자손 규칙을 생성하기 위해 적용된다. 이 때, 부모 규칙과 자손 규칙은 모두 [P]로 반환된다. LCS 유전 알고리즘은 각각의 학습 반복을 할 때마다 인구의 대다수가 보존되기 때문에 높은 엘리트주의를 가지고 있다. 규칙 발견은 대안적으로 분포 알고리즘의 추정과 같은 다른 방법에 의해 수행될 수 있지만, GA는 단연코 가장 일반적인 접근법이다. GA와 같은 진화 알고리즘은 확률적 검색을 사용하며, 이것은 LCS를 확률적 알고리즘으로 만든다. LCS는 검색 공간을 교묘하게 탐색하려 하지만 규칙 조합에 대한 철저한 검색을 수행하지 않으며, 최적의 솔루션으로 수렴할 것을 보장하지 않는다.

삭제

일반 LCS 학습 주기의 마지막 단계는 최대 모집단 크기를 유지하는 것이다. 삭제 메커니즘은 삭제할 분류자를 선택한다(일반적으로 룰렛 휠 선택을 사용한다). 분류자가 삭제 대상으로 선택될 확률은 그 적합성과 반비례한다. 분류기가 삭제 대상으로 선택되면 그 분점 매개변수가 1로 감소한다. 분류기의 숫자가 0으로 줄어들면 모집단에서 완전히 제거된다.

트레이닝

LCS는 일부 사용자 정의 교육 반복 횟수에 대해 또는 일부 사용자 정의 종료 기준이 충족될 때까지 이 단계를 반복하여 순환한다. 온라인 학습의 경우, LCS는 환경으로부터 반복될 때마다 완전히 새로운 교육 인스턴스를 얻게 될 것이다. 오프라인 학습의 경우 LCS는 유한한 훈련 데이터 세트를 통해 반복된다. 데이터 집합의 마지막 인스턴스에 도달하면 첫 번째 인스턴스로 돌아가서 데이터 집합을 다시 순환한다.

규칙 압축

일단 훈련이 완료되면, 규칙 모집단은 불가피하게 가난하고, 중복되고, 경험 없는 규칙들을 포함할 것이다. 후처리 단계로 규칙 컴팩트, 즉 응축 휴리스틱을 적용하는 것이 일반적이다. 결과적으로 압축된 규칙 모집단은 예측 모델(예: 테스트 인스턴스에 대한 예측)으로 적용되거나 지식 검색을 위해 해석될 준비가 되어 있다.

예측

규칙 압축이 적용되었는지 여부에 관계없이, LCS 알고리즘의 출력은 이전에 보이지 않았던 인스턴스에 대한 예측에 적용될 수 있는 분류자 집합이다. 예측 메커니즘은 감독되는 LCS 학습 사이클의 일부는 아니지만, LCS 학습 사이클의 강화에 중요한 역할을 할 것이다. 현재로서는 시험 데이터에 대한 예측을 위해 예측 메커니즘을 적용할 수 있는 방법을 고려한다. 예측 시 LCS 학습 구성요소는 모집단이 들어오는 시험 데이터로부터 계속 학습하지 않도록 비활성화된다. 테스트 인스턴스는 [P]에 전달되며, 여기서 평상시처럼 매치 세트[M]가 형성된다. 이 시점에서 일치 집합은 예측 배열로 다르게 전달된다. 경기 세트의 규칙은 다른 동작을 예측할 수 있으므로, 투표 방식이 적용된다. 단순 투표 방식에서는 일치 규칙의 '보트'를 가장 강력하게 지지하는 행동이 승리하고, 선택된 예측이 된다. 모든 규칙이 동등한 표를 얻는 것은 아니다. 오히려 단일 룰에 대한 투표의 강도는 일반적으로 그 수량과 적합성에 비례한다. 이러한 투표 방식과 LCS의 매장 지식의 성격은 LCS 알고리즘이 암묵적으로 앙상블 학습자임을 시사한다.

해석

개별 LCS 규칙은 일반적으로 다음과 같은 경우 사람이 읽을 수 있다.그러면 표현. LCS 예측 모델을 구성하는 규칙은 다른 규칙 매개변수로 순위를 정하고 수동으로 검사할 수 있다. 통계와 그래픽을 이용해 지식발견을 지도하는 글로벌 전략도 제시됐다.^[12][13] 인공 신경망, 무작위 숲 또는 유전자 프로그래밍과 같은 다른 진보된 기계 학습 접근방식과 관련하여 학습 분류기 시스템은 해석 가능한 해결책이 필요한 문제에 특히 잘 적합하다.

역사

초년

존 헨리 홀랜드는 1975년 그의 획기적인 책 "자연과 인공 시스템의 적응"^[14]과 홀랜드의 스키마 정리를 공식화한 것을 통해 유전 알고리즘(GA)을 대중화한 작품으로 가장 잘 알려져 있다. 1976년, 홀랜드는 GA 개념의 확장을 그가 "인식 시스템"^[15]이라고 부르는 것으로 개념화하였고, 논문 "적응 알고리즘에 기초한 인식 시스템"^[16]에서 최초의 학습 분류 시스템으로 알려지게 될 것에 대한 최초의 상세한 설명을 제공하였다. 인지 시스템 원(CS-1)이라는 이름의 이 첫 번째 시스템은 인간의 판독 가능한 규칙을 사용하여 알 수 없는 근본적인 역학을 가진 실제 시스템(즉, 환경)을 모델링 도구로 고안되었다. 온라인 머신러닝(machine learning)을 실시하여 간헐적인 보수/보상에 근거하여 환경에 적응하고(즉, 강화학습) 이러한 규칙을 적용하여 실제 시스템에 맞는 행동을 발생시키는 것이 목표였다. 이 초기 야심 찬 실행은 나중에 일관되지 않은 결과를 낳으면서 지나치게 복잡한 것으로 간주되었다.^[2][17]

1980년부터 Kenneth de Jong과 그의 제자인 Stephen Smith는 (LS-1)와 규칙 기반 기계 학습에 대해 다른 접근법을 취했는데, 여기서 학습은 온라인 적응 과정이 아닌 오프라인 최적화 과정으로 간주되었다.^[18][19][20] 이 새로운 접근법은 표준 유전 알고리즘과 더 유사하지만 독립적인 규칙 집합을 발전시켰다. 그 때부터 미시간 대학의 홀랜드가 도입한 온라인 학습 틀에서 영감을 받은 LCS 방법을 미시간식 LCS라고 불렀고, 피츠버그 대학의 스미스, 드종에서 영감을 받은 방법을 피츠버그식 LCS라고 불렀다.^[2][17] 1986년, 네덜란드는 향후 10년간 표준 미시간 스타일의 LCS로 간주될 만한 것을 개발했다.^[21]

는 측은 연구의 초창기에 나타났던 다른 중요한 개념(1) 양동이를 이어받아 불을 알고리즘의 부모의 규칙 신용 assignment[22](2)선택에 대한 공용'environmental 틈새의(포지티브전[M]을 세웠다)오히려보다 미국 전체 인구 피복(3)[P],[23]은 형식화(빌딩 블록 접근법)가장 먼저 C. 소개되어 포함했다reate opErator,[24]액션의 형식화[A],[24]세트(5)단순화된 알고리즘 architecture,[24](6)strength-based fitness,[21], 또는 관리한 무구 분식 학습 problems[25]의(7)배려와 정확한 집합의 도입[C],[26](8)accuracy-based fitness[27](9)퍼지 논리의 LCS[28]을 조합(후일 sp(4).퍼지 loopcontrolsystemalg의 혈통Awned.(10), (10) 다단계 문제에 대한 성능 향상을 위한 긴 액션 체인 및 기본 계층 구조 권장,^[29][30][31] (11) 잠재 학습(이후 예상 분류 시스템(ACS)의 새로운 분과에 영감을 주었으며),^[32] (12) 첫 Q-러닝과 같은 신용 할당 기법의 도입.^[33] 이러한 개념들이 모두 현대 LCS 알고리즘에 적용되는 것은 아니지만, 각각은 LCS 패러다임 개발의 랜드마크였다.

혁명

학습 분류기 시스템에 대한 관심은 1990년대 중반 강화 학습을 위한 Q-Learning 알고리즘의^[34] 개발, 스튜어트 윌슨에 의한 대폭 간소화된 미시건 스타일 LCS 아키텍처의 도입 등 두 가지 사건으로 인해 크게 활기를 띠었다.^[11][35] Wilson의 Zeroth-level Classifier System(ZCS)^[35]은 Hollands 표준 LCS 구현에 기반한 알고리즘 이해도를 높이는 데 초점을 맞췄다.^[21] 이는 부분적으로 원래의 BBA 신용 할당에 필수적인 규칙 입찰과 내부 메시지 목록을 제거하고 이를 하이브리드 BBA/Q-Learning 전략으로 대체함으로써 이루어졌다. ZCS는 훨씬 더 단순한 LCS 아키텍처가 원래의 보다 복잡한 구현뿐만 아니라 더 잘 수행될 수 있다는 것을 증명했다. 하지만 ZCS는 여전히 일반 분류기 확산 등 실적 단점으로 어려움을 겪었다.

1995년, 윌슨은 영화에서 그는 선형 분급기 시스템 XCS을 소개했다 자신의 획기적인 종이,"Classifier 건강 정확성에 기초한"을 출판했다.[11]XCS고accuracy-based 건강, 틈새 GA(이번 조치에 연기[A]을 세웠다), 명시적 일반화 메커니즘적 포섭을 Q-Learni의 각색한 작품이라고 덧붙였다 ZCS의 단순한 건축했다.ng 신용 할당. XCS는 정확하고 극대화된 일반 분류기를 진화시키면서 최적의 성능에 도달할 수 있는 능력과 더불어 인상적인 문제 유연성(강화 학습과 감독 학습 모두 수행할 수 있음)으로 대중화되었다. XCS는 후에 가장 잘 알려져 있고 가장 많이 연구된 LCS 알고리즘이 되었고 정확도 기반 LCS의 새로운 제품군을 정의했다. ZCS는 강도에 기반한 LCS와 동의어가 되었다. XCS는 LCS와 강화 학습 분야 사이의 격차를 성공적으로 메웠기 때문에 또한 중요하다. XCS의 성공에 따라, LCS는 나중에 일반화 능력을 부여받은 강화 학습 시스템으로 설명되었다.^[36] 강화 학습은 일반적으로 상태/행동 공간의 완전한 표현을 지도화하는 가치 함수를 배우려고 한다. 마찬가지로, XCS의 설계는 환경(강도 기반 LCS의 경우처럼)에서 높은 보상에 초점을 맞추기보다는 문제 공간에 대한 일체형적이고 정확한 표현(즉, 완전한 지도)을 형성하도록 한다. 개념적으로 완전한 지도는 당신이 해야 할 일, 혹은 옳은 일뿐만 아니라 하지 말아야 할 일, 혹은 잘못된 것을 포착한다. 달리, 대부분의 강도에 기반한 LCS 또는 독점적으로 감독되는 학습 LCS는 최상의 행동 지도(또는 부분 지도)의 형태로 효율적인 일반화의 규칙 집합을 추구한다. 강도 대 정확도 기반 적합성 및 완전 대 최선의 행동 지도 간의 비교는 이후 더 자세히 검토되었다.^[37][38]

XCS의 결과로

XCS는 완전히 새로운 세대의 LCS 알고리즘과 애플리케이션의 개발에 영감을 주었다. 1995년 콩돈은 질병의 실제 역학조사에 LCS를 가장 먼저 적용했고, 이후 역학구분을 ^[40]위해 BOOLE++,^[41] EpiCS를^[42] 개발한 홈즈가 촘촘히 뒤를 이었다. 이러한 초기 작품들은 생물정보학 애플리케이션에서 대표되는 복잡하고 대규모 데이터 마이닝 작업에 LCS 알고리즘을 적용하는 데 나중에 관심을 불러일으켰다. 1998년 스톨츠만은 고전적인 '조건-행동' 표현보다는 '조건-작용-효과'의 형태로 규칙을 포함하는 예상 분류 시스템(ACS)을 도입했다.^[32] ACS는 환경의 모든 가능한 상황에서 작용의 지각 결과를 예측하도록 설계되었다. 즉, 시스템은 주어진 상황에서 무엇을 할 것인가를 명시하는 모델뿐만 아니라, 구체적인 조치가 실행된 후에 어떤 일이 일어날 것인가에 대한 정보도 제공하는 모델을 진화한다. 이 LCS 알고리즘 계열은 다단계 문제, 계획, 학습 속도 향상 또는 모호한 지각 별칭에 가장 적합하다(즉, 구별되는 상태에서 동일한 관찰을 얻지만 다른 행동이 필요한 경우). Butz는 후에 원래의 방법에 대한 많은 개선점을 개발하기 위해 LCS의 기대되는 이 가족을 추구했다.^[43] 2002년에 Wilson은 함수 근사치를 수행하기 위해 계산된 동작을 추가하면서 XCSF를 도입했다.^[44] 2003년 베르나도-만실라는 XCS 알고리즘을 감독하는 학습, 단단계 문제, 최상의 액션 세트 형성의 과제에 특화한 supervision Classifier System(UCS)을 도입했다. UCS는 많은 강화 학습자의 특징인 탐구/설명 학습 단계뿐만 아니라 단순하고 정확성 기반 규칙 적합성을 위해 강화 학습 전략을 제거했다. Bull은 LCS 프레임워크에 대한 더 나은 이론적 이해를 개발하기 위해 단순 정확도 기반 LCS(^[45]YCS)와 단순 강도 기반 LCS Minimal Classifier System(MCS)^[46]을 도입했다. Bacardit은 GAssist와^[47] BioHEL,^[48] 바이오정보학 애플리케이션에서 대규모 데이터셋에 대한 데이터 마이닝과 확장성을 위해 설계된 피츠버그 스타일의 LCS를 소개했다. 2008년, Drugowitsch는 LCS 알고리즘의 이론적 검토를 포함한 "학습 분류기 시스템의 설계 및 분석"이라는 책을 출판했다.^[49] Butz는 XCSF를^[1] 위한 GUI 내에 첫 번째 규칙 온라인 학습 시각화를 도입했다(이 페이지 상단에 있는 이미지 참조). UCS 프레임워크를 확장하고 ExSTraCS를 도입했는데, 이는 시끄러운 문제 영역(예: 역학 및 생물정보학)에서 학습을 감독하도록 명시적으로 설계되었다.^[50] ExSTraCS(2)장기 기억의 형태를 특성 tracking,[52]로 더 효율적이며 이질 데이터 패턴의 특성화 학습을 허용하면서 언급한 중요한 특징을 향한 data,[51]에,와 유연한 규칙 표현 Bacardit's과 비슷하(3)덮개와 유전자 알고리즘 운전하는(1)전문적인 지식 통합하였다. 섞 이산형 속성 리스트 표현.^[53] Bacardit과 Urbanowicz 모두 LCS 규칙을 해석하고 데이터 마이닝에 대한 지식 검색을 수행하기 위한 통계 및 시각화 전략을 탐구했다.^[12][13] 브라운과 아이크발은 빌딩 블록을 코드 조각 형태로 재사용하는 개념을 탐구했고, 보다 단순한 멀티플렉서 문제로부터 유용한 빌딩 블록을 먼저 학습함으로써 135비트 멀티플렉서 벤치마크 문제를 최초로 해결했다.^[54] 이후 미시간 스타일의 LCS 확장성을 개선하기 위해 ExSTraCS 2.0이 도입되어 135비트 멀티플렉서 벤치마크 문제를 최초로 직접 해결하는 데 성공했다.^[5] n비트 멀티플렉서 문제는 인식성이 높고 이질적인 문제여서 매우 도전적인 기계 학습 과제가 되고 있다.

변형

미시건 스타일 학습 분류기 시스템

미시건 스타일 LCS는 유전 알고리즘이 개별 규칙 수준에서 작동하고 해결책은 규칙 모집단 전체로 표현되는 규칙 모집단이 특징이다. 미시간 스타일 시스템은 또한 강화 학습과 감독 학습을 동시에 수행할 수 있는 점증적으로 학습하고 온라인과 오프라인 학습도 학습한다. 미시건식 시스템은 더 많은 수의 문제 영역에 적용할 수 있다는 이점과 점증적 학습의 고유한 이점을 가지고 있다.

피츠버그 스타일 학습 분류기 시스템

피츠버그-스타일 LCS는 각 규칙 집합이 잠재적 해결책인 가변 길이 규칙 집합 모집단으로 특징지어진다. 유전 알고리즘은 일반적으로 전체 규칙 집합 수준에서 작동한다. 피츠버그 스타일의 시스템은 또한 순서 규칙 목록을 독특하게 진화시킬 수 있을 뿐만 아니라 기본 규칙을 채택할 수 있다. 이러한 시스템은 보다 작은 규칙 집합을 식별하여 수동 규칙 검사와 관련하여 이러한 시스템을 보다 쉽게 해석할 수 있는 자연적 이점을 가지고 있다.

하이브리드 시스템

두 시스템의 핵심 강점을 결합하려는 시스템도 제시됐다.

이점

• 적응형: 그들은 온라인 학습의 경우 변화하는 환경에 적응할 수 있다.
• 무료 모델: 그들은 환경이나 데이터 내의 연관성 패턴에 대해 제한적인 가정을 한다.
  • 그들은 이전의 지식들에 의존하지 않고 복잡하고, 인식적이고, 이질적인, 또는 분산된 기본 패턴을 모델링할 수 있다.
  • 이들은 데이터의 예측 특성과 비예측 특성의 수에 대해 가정을 하지 않는다.
• 앙상블 학습자: 일반적으로 예측을 제공하는 특정 인스턴스(instance)에 단일 모델이 적용되지 않는다. 대신에 관련성이 있고 종종 상충되는 규칙 집합은 모호한 예측으로 해석될 수 있는 '투표'에 기여한다.
• 확률적 학습자: 비결정론적 학습은 결정론적 학습이나 철저한 학습이 난해해지는 대규모 또는 높은 복잡성 문제에 유리하다.
• 암시적으로 다중 목적어: 규칙은 최대 일반성/간단성을 장려하는 암묵적이고 명시적인 압력으로 정확성을 향해 진화한다. 이 암묵적 일반화 압력은 LCS만의 독특한 것이다. 효과적으로, 더 일반적인 규칙은 매치 세트에서 더 자주 나타날 것이다. 결과적으로, 그들은 부모로 선택될 수 있는 더 빈번한 기회를 갖게 되고, 그들의 더 일반적인 (게놈)을 자손의 규칙으로 물려준다.
• 해석 가능:데이터 마이닝 및 지식 발견을 위해 개별 LCS 규칙은 논리적이며, 다음과 같은 경우 인간이 해석할 수 있도록 만들 수 있다.그렇다면 진술. 또한 중요한 특징과 규칙 집단 전체의 연관성 패턴을 식별하는 글로벌 지식 발견이 가능하도록 효과적인 전략도 도입되었다.^[12]
• 유연한 애플리케이션
  • 단일 또는 다중 단계 문제
  • 감독, 강화 또는 감독되지 않은 학습
  • 바이너리 클래스 및 다중 클래스 분류
  • 회귀
  • 이산형 또는 연속형 피쳐(또는 두 가지 유형의 일부 혼합)
  • 문제 도메인을 정리하거나 소음이 많은 경우
  • 균형 조정 또는 불균형 데이터셋.
  • 누락된 데이터 수용(예: 교육 사례에서 누락된 피쳐 값)

단점들

• 제한된 소프트웨어 가용성: 제한된 수의 오픈 소스, 접근 가능한 LCS 구현이 있으며, 사용자 친화적이거나 머신러닝 실무자가 접근할 수 있도록 설계된 LCS 구현은 더 적다.
• 해석: LCS 알고리즘이 일부 고급 기계 학습자보다 확실히 더 해석 가능한 반면, 사용자는 일련의 규칙(때로는 LCS 모델을 이해하기 위한 큰 규칙 집합)을 해석해야 한다. 규칙의 압축 방법과 해석 전략은 여전히 활발한 연구의 영역으로 남아 있다.
• 이론/융합 증거: LCS 알고리즘 뒤에는 비교적 작은 이론적 작업이 있다. 이는 상대적인 알고리즘 복잡성(많은 상호작용 구성요소를 적용)과 확률적 특성 때문일 가능성이 높다.
• 오버피팅: 다른 기계 학습자와 마찬가지로 LCS는 암묵적이고 명시적인 일반화 압력에도 불구하고 오버피팅에 시달릴 수 있다.
• 실행 매개변수: LCS에는 고려해야 할 실행 매개변수가 많다. 일반적으로, 최대 규칙 모집단 크기와 최대 학습 반복 횟수라는 두 가지 중요한 매개변수를 제외하고 대부분의 매개변수는 커뮤니티에서 결정한 기본값을 그대로 둘 수 있다. 이러한 매개변수를 최적화하는 것은 매우 문제에 좌우될 가능성이 있다.
• 악명: 나이에도 불구하고 LCS 알고리즘은 여전히 기계학습 커뮤니티에서도 널리 알려져 있지 않다. 결과적으로, LCS 알고리즘은 다른 확립된 기계 학습 접근법에 비해 거의 고려되지 않는다. 이는 (1) LCS는 비교적 복잡한 알고리즘 접근법, (2) LCS, 규칙 기반 모델링은 거의 모든 기계 학습 접근법과 다른 모델링 패러다임이다. (3) LCS 소프트웨어 구현은 흔하지 않다.
• 계산적으로 비싸다양한 비용: 일부 철저한 접근법보다 확실히 더 실현 가능한 반면, LCS 알고리즘은 계산적으로 비용이 많이 들 수 있다. 단순하고 선형적인 학습 문제를 위해 LCS를 적용할 필요가 없다. LCS 알고리즘은 복잡한 문제 공간 또는 사전 지식이 거의 없는 문제 공간에 가장 적합하다.

문제 도메인

• 적응 제어
• 데이터 마이닝
• 엔지니어링 디자인
• 피쳐 선택
• 함수 근사
• 게임 플레이
• 이미지 분류
• 지식 처리
• 메디컬 진단
• 모델링.
• 항법
• 최적화
• 예측
• 쿼리 중
• 로보틱스
• 라우팅
• 규칙 유도
• 스케줄링
• 전략

용어.

'학습수업(LCS)'이라는 명칭은 '분류하는 법을 배운다'(예: 의사결정 나무, 인공신경망)는 기계학습 알고리즘이 많지만 LCS는 아니기 때문에 다소 오해의 소지가 있다. '규칙 기반 머신러닝(RBML)'이라는 용어는 이러한 시스템의 필수적인 '규칙 기반' 구성요소를 보다 명확하게 포착하고 있지만, LCS(예: 협회 규칙 학습 또는 인공 면역 시스템)로 간주되지 않는 방법에도 일반화되기 때문에 유용하다. '유전자 기반 머신러닝', 심지어 '유전자 알고리즘'^[39]과 같은 보다 일반적인 용어들도 학습 분류 체계로서 보다 특성적으로 정의될 것을 언급하기 위해 적용되었다. 유전 알고리즘과 유사하기 때문에 피츠버그식 학습 분류기 시스템을 '유전자 알고리즘'이라고 부르기도 한다. 이를 넘어 일부 LCS 알고리즘, 또는 밀접하게 관련된 방법을 '인지 시스템',^[16] '어댑티브 에이전트', '생산 시스템' 또는 일반적으로 '분류 시스템'^[55][56]이라고 지칭해 왔다. 이러한 용어의 변화는 그 분야의 혼란에 기여한다.

2000년대까지 거의 모든 학습 분류 시스템 방법은 강화 학습 문제를 염두에 두고 개발되었다. 그 결과, '학습 분류 시스템'이라는 용어는 일반적으로 '시행착오' 강화 학습과 유전 알고리즘의 글로벌 검색이 결합된 것으로 정의되었다. 감독되는 학습 어플리케이션에 대한 관심, 심지어 감독되지 않은 학습에 대한 관심은 이후 이 용어의 사용과 정의를 넓혔다.

참고 항목

• 규칙 기반 기계 학습
• 생산체계
• 전문가 시스템
• 유전 알고리즘
• 협회규칙학습
• 인공 면역 체계
• 인구 기반 증분 학습
• 머신러닝

참조

외부 링크

비디오 튜토리얼

• 간단명료하게 분류기 시스템 학습 - (2016) 기본 LCS 알고리즘에 들어가 구성 요소와 작동 방식을 배우십시오.

웹 페이지

• LCS & GBML Central
• UWE 학습 분류기 연구 그룹
• 예측 역학