패턴 이론

Pattern theory

울프 그레넌더가 공식화한 패턴 이론은 세계의 지식을 패턴으로 묘사하는 수학적인 형식주의다. 패턴을 인식하고 분류하는 알고리즘과 기계를 처방하는 데서 출발하는 것이 아니라 패턴 개념을 정밀한 언어로 표현하고 재표현하는 어휘를 규정한다는 점에서 인공지능에 대한 다른 접근법과 다르다. 수학적 범위에 있어 패턴 이론은 대수학 통계학뿐만 아니라 국소 위상학 및 지구적 내향성 특성까지 포괄한다.

새로운 대수 어휘 외에, 통계적 접근방식은 다음을 목표로 하는 점에서 참신하다.

  • 이전에는 흔히 볼 수 있었던 인위적인 자극보다는 실제의 데이터를 이용한 데이터 세트숨겨진 변수를 파악한다.
  • Gibbs 유사 그래프의 정점을 이루는 관측 변수에 대한 모델과 숨겨진 변수에 대한 사전 분포를 공식화한다.
  • 이러한 그래프의 랜덤성과 변동성을 연구하십시오.
  • 패턴의 변형을 나열하여 적용된 확률적 모델의 기본 클래스를 만든다.
  • 신호만 분석하지 않고 모델에서 합성(샘플)하십시오.

브라운 대학 패턴 이론 그룹은 1972년 울프 그레넌더에 의해 결성되었다.[1] 많은 수학자들이 현재 이 그룹에서 일하고 있는데, 그들 중 필즈 메달리스트데이비드 뭄포드가 주목할 만하다. 뭄포드는 패턴 이론에서 그레난더를 자신의 "구루"로 간주한다.[citation needed]

예: 자연어 문법

문법자동화
문법 생성기

우리는 뒤따르는 대수적 정의에 동기를 부여하는 예로부터 시작한다. 만약 우리가 언어 패턴을 표현하고 싶다면, 가장 중요한 것은 단어일 것이다. 그러나 "하기 위해서"와 같은 정해진 구절원자와 같은 단어의 부적절함을 즉시 나타낸다. 다른 원시성을 찾는데 있어서, 우리는 문법의 규칙을 시도할지도 모른다. 우리는 그래머를 유한 상태 오토마타 또는 문맥이 없는 그래머로 표현할 수 있다. 아래는 유한 상태 문법 자동화의 표본이다.

패턴 이론에서 자동화와 프로그래밍 코드의 몇 가지 간단한 규칙으로부터 다음과 같은 구절이 생성된다.

작은 오두막을 소유한 소년은 깊은 숲으로 갔다.
왕자는 호수로 걸어갔다.
소녀는 호수로 걸어갔고 공주는 호수로 갔다.
그 예쁜 왕자는 어두운 숲으로 걸어갔다.

그러한 문장을 만들기 위해 유한 상태 오토마타에서 규칙을 다시 쓰는 것은 다음과 같은 문장을 만드는 발전기 역할을 한다: 만일 기계가 상태 1에서 시작되면 상태 2로 가서 "the"라는 단어를 쓴다. 주 2부터 왕자, 소년, 공주, 소녀, 무작위로 선택된 4개의 단어 중 하나를 쓴다. 주어진 단어를 선택할 확률은 자동화에 해당하는 마르코프 체인에 의해 주어진다. 이러한 단순한 자동화는 때때로 더 어색한 문장을 만들어 낸다.

사악한 왕자는 호수로 걸어갔다.
왕자는 어두운 숲으로 걸었고 왕자는 숲으로 걸었고 작은 작은 집을 소유한 어떤 크고 작은 오두막집에 살았던 공주는 숲으로 갔다.

유한 상태 도표에서 우리는 신호를 생성하는 다음과 같은 발전기(오른쪽 표시)를 유추할 수 있다. 발전기는 4-투플이다: 현재 상태, 다음 상태, 단어 쓰기, 여러 선택사항이 있을 때 쓰여진 단어의 확률. 즉, 각 발전기는 마르코프 체인에 대한 상태 다이어그램상태 전환 화살표가 된다.

발전기 구성이 선형적으로 결합되어 그 출력이 문장을 형성하므로 각 발전기가 발전기 전후에 발전기에 "결합"한다고 상상해 보십시오. 이 결합을 1x,1y,2x,2y,...12x,12y로 표시한다. 각 숫자 라벨은 자동화의 상태에 대응하고 각 문자 "x"와 "y"는 인바운드 및 아웃바운드 채권에 대응한다. 다음 본드 테이블(왼쪽)은 자동 도표와 동일하다. 단순성을 위해 본드 테이블의 절반만 표시되며, 실제로 이 테이블은 대칭적이다.

1배 1y 2배 2y 3배 3y 4배 4y 5배 5y 6배 6y 7배 7y 8배 8y 9배 9y 10배 10y 11배 11y 12배 12y
1배 1
1y 1
2배 1
2y 1
3배 1
3y 1 1
4배
4y 1 1
5배
5y 1
6배
6y 1
7배 1
7y
8배
8y 1
9배
9y 1
10배
10y 1
11배 1
11y 1
12배
12y

이 예에서 알 수 있듯이, 그리고 연구되는 신호의 전형으로서 원시성과 본드테이블을 식별하는 것은 어느 정도 생각을 필요로 한다. 이 예에서는 다른 신호 문제에서 쉽게 드러나지 않는 또 다른 중요한 사실을 강조한다. 즉, 구성이 관찰되는 신호가 아니라는 것이다. 오히려 문장으로서의 이미지가 관찰된다. 여기에는 관측할 수 있는 구조와 관측할 수 없는 구조를 구별할 수 있는 상당한 이유가 있다. 또한 숨겨진 마르코프 모델과 연관시킬 수 있는 대수적 구조를 제공한다. 아래의 시력 예와 같은 감각적 예에서, 숨겨진 구성과 관찰된 이미지는 훨씬 더 유사하며, 그러한 구별은 정당화되지 않는 것처럼 보일 수 있다. 다행히 문법 예시는 이런 구분을 떠올리게 한다.

보다 정교한 예는 자연어의 연계 문법 이론에서 찾을 수 있다.

대수학 기초

이 예에 따라 다음과 같은 정의가 있다.

  1. 제너레이터 g으)로 그려진
    1 and 2 dimensional generators
    관찰된 신호를 생성하는 패턴 이론의 원시적인 것이다. 구조적으로, 은 b B {\ b라고 불리는 인터페이스를 가진 값인데 이 값은 g를 연결하여 신호 발생기를 형성한다. 인접 발전기 2개는 결합값이 같을 때 연결된다. 유사성 자가 지도 ss: G -> G는 경직된 신체 변형이나 스케일링과 같이 우리가 보고 있는 세계의 불멸자들을 표현한다.
  2. 접착제 생성기를 라고 하는 결합 결합 결합 결합 테이블에 의해 로컬로 설명되어 있는 σ 배경 σ에 대한 신호를 생성하는 구성 c 부울 함수 는 규칙성 4투플 <G,S, ρ, σ σ>의 주요 구성 요소로서 정의되어 있다.
    은(는) 허용되는 발전기 이웃의 개념을 포착한 것 같다. 즉, 규칙성은 결합표를 통해 이웃이 발전기에 허용되는 것을 정의하는 자극 영역의 법칙이다. 그것은 자극 영역의 법칙이다. 나중에 부울함수에서 확률값으로 규칙성을 완화할 것이다. 부울함수에서 확률값으로, 그것은 어떤 자극적인 이웃이 가능한지를 포착할 것이다. σ은 발전기의 물리적 배열이다. 시력으로는 2차원 격자일 수 있다. 언어에서 그것은 선형적인 배열이다.
  3. 이미지(C mod R)는 지각 기기와 독립적으로 존재하는 것과 반대로 관측된 구성의 개념을 포착한다. 이미지는 구성의 구성과 유사성 변환을 이어받아 외부 결합만으로 구별되는 구성이다. 공식적으로 이미지는 3개의 속성을 가진 식별 규칙 "~"에 의해 분할된 동등성 클래스다.
    1. ext(c) = c~c'마다 ext(c')
    2. c~c'할 때마다 sc~sc'
    3. 시그마(c1,c2) ~ 시그마(c1',c2') c1~c1', c2~c2'가 모두 정규일 때마다.
    물리적 자극에 해당하는 구성은 많은 관찰자 인식의 식별 규칙에 해당하는 많은 이미지를 가질 수 있다.
  4. 패턴은 이미지의 반복 가능한 구성 요소로서 이미지의 S-invariant 하위 집합으로 정의된다. 유사성은 우리가 패턴을 정의하기 위해 사용하는 참조 변환(예: 강체 변형)이다. 언뜻 보기에 이 정의는 최소한의 서브 이미지가 반복적으로 반복되는 텍스처 패턴에만 적합한 것 같다. 우리가 개와 같은 물체의 이미지를 본다면, 그것은 반복되지 않고, 익숙해 보이고 패턴이 되어야 할 것 같다.
  5. 변형은 환경의 소음과 지각 장치의 오류를 설명하는 원래의 이미지의 변형이다. 그레넌더는 소음과 흐릿함, 다단계 중첩, 도메인 뒤틀림, 방해 등 4가지 변형을 파악한다.
    예제 2 지시된 경계
    배열
    이미지
    제너레이터
    영상을 생성하는 생성기의 이러한 구성은 본딩 테이블로 함께 짜여진 원시적 요소에 의해 생성되며, 비 "0" & "1" 생성기를 단일 경계 요소에 매핑하는 식별 규칙으로 관찰자가 인식한다. 다른 9개의 비'0'&"1" 발전기를 각각 90도씩 회전시켜 9개의 비퇴전 발전기를 만든다. "방향 경계"의 특징을 염두에 두고 발전기를 조리하여 다음과 같이 해석한다: "0" 발전기는 내부 원소에 대응하고, "1" 발전기는 외부 원소에 대응하며, "2"와 그 회전은 직선 원소이며, 나머지는 회전 원소다.
    제품(모든 nbr 본드)으로 정의된 Boolean 정규성에서는 본드 테이블을 위반하는 단일 발생기라도 포함된 구성은 고려 대상에서 제외된다. 따라서 모든 인접 발전기가 결합 테이블에 부착된 가장 순수한 형태의 형상만 허용된다. 이 엄격한 조건은 부울 결합 표 대신 확률 측정을 사용하여 완화할 수 있다.
    새로운 규칙성은 더 이상 완벽한 지시된 경계를 지시하지 않지만, 수용자 함수 A()의 관점에서 구성의 확률을 정의한다. 이러한 구성은 관심의 특성과 관련하여 불순물과 결함을 가질 수 있다.

    발전기와 완전한 본드 테이블이 주어지는 이점으로 패턴 분석의 어려운 부분이 수행된다. 새로운 종류의 신호와 형상을 다루는데 있어서 발전기와 결합 테이블을 고안하는 일은 훨씬 더 어렵다.

    다시, 그래머에서처럼 발전기와 결합 테이블을 식별하는 것은 약간의 생각을 필요로 한다. 마치 미묘한 것은 구성이 우리가 관찰하는 신호가 아니라는 사실이다. 오히려 우리는 식별 규칙의 실루엣 투영으로 그것의 이미지를 관찰한다.

부울 결합 진리 표
본드
가치
0 1 2 3 4 5
0 1 1
1 1 1
2 1
3
4
5

엔트로피

패턴이론은 p(c)가 부여한 관심의 특성의 측면에서 순서를 정의한다.

에너지(c) = -log P(c)

통계

베이지안 추론에 대한 그레난더의 패턴 이론 치료는 영상 재구성(예: 콘텐트 어드레싱 가능 메모리) 쪽으로 치우쳐 있는 것 같다. 내가 만든 이미지야, 찾아봐 그러나, Mumford의 패턴 이론에 대한 해석은 더 광범위하고 그는 PT를 더 잘 알려진 통계적 방법들을 포함하도록 정의한다. 뭄포드의 패턴이론(Pattern Theory)으로 주제를 포함하는 기준은 HMM, EM 알고리즘, 아이디어의 동적 프로그래밍 서클과 같은 "공통적인 기법과 동기에 의해 특징지어지는" 방법들이다. 이 섹션의 주제들은 패턴 이론에 대한 멈포드의 처우를 반영할 것이다. 그의 통계 패턴 이론의 원리는 다음과 같다.

  • 숨겨진 관심 상태를 유추하기 위해 구성된 신호가 아닌 실제 신호를 사용한다.
  • 그러한 신호는 순전히 결정론적 분석에 굴복하기에는 너무 많은 복잡성과 왜곡을 포함하고 있으므로 확률론적 방법 또한 채택한다.
  • 대칭, 부품의 독립성, 주요 통계량의 여유도를 포함한 신호의 자연 구조를 존중한다. Bayes의 규칙으로 숨겨진 상태를 유추하여 파생 모델에서 표본을 추출하여 검증한다.
  • 모든 양식에 걸쳐, 한정된 변형 집단은 순수한 패턴을 실제 세계의 신호로 왜곡한다.
  • 관측에 영향을 미치는 확률적 요인은 강한 조건부 독립성을 보여준다.

통계적 PT는 베이즈 정리마르코프 모델의 형태로 조건부 확률을 어디서나 활용한다. 이 두 개념은 모두 숨겨진 상태(구성)와 관찰된 상태(이미지) 사이의 관계를 표현하기 위해 사용된다. 마르코프 모델도 자극의 국부적 특성을 포착해 규칙성을 위한 본드테이블의 목적을 연상시킨다.

일반 설정은 다음과 같다.

Let s = 알고자 하는 데이터의 숨겨진 상태. i = 관측된 이미지. 베이즈 정리는 다음을 제공한다.

p (s i ) p(i) = p (s, i ) = p (i s ) p (i s ) p(s)
신호를 분석하려면(인식): fix i, p, user s를 최대화한다.
신호를 합성하려면(샘플링): s 수정, i 생성, w/ 실제 영상 비교

다음의 조건부 확률 예는 이러한 방법들을 실제 행동으로 보여준다.

로컬 특성에 대한 조건부 확률

N-그램 텍스트 문자열: 제1장 예시별 Mumford의 패턴 이론을 참조하십시오.

MAP - MDL(MDL은 MAP 확률론적 제형이 분석적으로 의미가 있는 이유를 엿볼 수 있다)

숨겨진 상태의 조건부 확률

기계번역을 위한 베이즈 정리

만약 우리가 프랑스어 문장을 영어로 번역하고 싶다면. 여기서 숨겨진 구성은 영어문장이며 그들이 만들어내는 관찰된 신호는 프랑스어 문장이다. 베이즈 정리는 p(e f)p(f) = p(e) = p(f) e(e) = p(f e)p(e)를 주고 기계 번역의 기본 방정식으로 줄인다: 적절한 e(e)에 대해 p(e f) = p(f e)p(e)를 최대화하므로 e에 대해 최대화할 때 탈락한다. 이렇게 하면 문제가 다음과 같은 세 가지 주요 계산으로 감소한다.

  1. N그램 방법과 동적 프로그래밍을 사용하여 지정된 e에 대한 p(e)
  2. 선형 및 예상 최대화(EM) 알고리즘을 사용하여 주어진 ef에 대한 p(f e)
  3. e 동적 프로그래밍을 사용하여 1과 2의 제품을 다시 최대화함

이 분석은 두 언어에 대해 대칭적인 것으로 보이며, 만약 우리가 p(f e)를 계산할 수 있다고 생각한다면, 분석을 돌려서 p(e f)를 직접 계산해보는 것은 어떨까? 이유는 p(f e)를 계산하는 동안 소스 문장이 잘 형성된다는 비대칭적인 가정이 만들어지고 그것이 무엇으로 번역될지 모르기 때문에 대상 번역에 대해 그러한 가정을 할 수 없기 때문이다.

우리는 이제 위의 3부 분해에서 p(f e)에 초점을 맞춘다. 다른 두 부분인 p(e)와 최대 e는 N그램 모델과 유사한 기법을 사용한다. 대규모 훈련 데이터 세트(캐나다 의회의 해당 데이터 세트)에서 불어-영어로 번역할 경우:

       NULL 그리고 그 프로그램은 실행되었다 Le program a ete mis approgram in application. 

문장 쌍은 정렬(2,3,4,5,6,6,6)로 인코딩할 수 있는데, 이는 프랑스어의 첫 번째 단어는 두 번째 영어 단어에서, 두 번째 단어는 세 번째 영어 단어에서, 등등이다. 선형은 번역의 간단한 인코딩이지만, 선형에 대한 보다 계산적으로 편리한 접근법은 선형을 네 가지 매개변수로 나누는 것이다.

  1. 불임: 그것에 연결될 프랑스어 문자열의 단어 수. 예: n(3 구현) = "실행"이 세 단어로 번역될 확률 - 그 단어의 불임
  2. 거짓성: 우리는 가짜 프랑스어를 집어 던질 확률을 나타내기 위해 공예품 NULL을 단어로 소개한다. 예: p1 그 보완물은 p0 = 1 - p1 될 것이다.
  3. 번역: 각 단어의 번역본. 예: t(a는 ) = 영어 "가 가지고 있는" 번역 확률은 프랑스어 "a"로 번역된다.
  4. 왜곡: 이 단어들이 차지할 프랑스어 문자열의 실제 위치. 예: d (5 2, 4, 6 ) = 4단어 영어 문장과 6단어 프랑스어 문장의 5단어 영어 문장으로 이동하는 2단계 프랑스어 단어 왜곡. 이러한 방식으로 정렬을 인코딩하여 교육 데이터에서 이전 데이터를 쉽게 표현하고 추출하며 새로운 공식은

전자파 알고리즘을 입증하는 단순성을 위해 변환 확률 t()만 포함하는 간단한 계산을 거쳐야 하지만, 그 방법이 모든 매개변수에 적용된다는 것은 말할 필요도 없다. 모든 단어에 생식력 1이 있고 (3) 왜곡 확률이 없는 NULL 단어 (2)가 없는 단순 사례(1)를 고려한다. 우리의 훈련 자료에는 bcxy, b → y의 2-sentence 쌍이 포함될 것이다. 영어 2단어 'b c'를 프랑스어 'x y'로 번역하면 두 개의 정렬이 가능한데, 1개의 단어를 포함하면 맞춤은 다음과 같다.

                         b c b b b x x y x y y 

병렬, 크로스, 싱글톤으로 각각 불린다.

전자파 알고리즘을 설명하려면 먼저 원하는 파라미터를 균일하게 설정하십시오.

t(xb ) = t(yb ) = t(xc ) = t(xc ) = t(yc ) = 12

그 후 EM은 다음과 같이 반복한다.

전자파 알고리즘의 반복

"교차 정렬"(by에 연결되는 경우)에 대한 정렬 확률은 두 번째 문장 쌍 b/y에서 상승하였다. 그것은 t(y b)를 더욱 굳혔지만, 부작용으로서도 t(x c)를 증가시켰는데, x는 같은 "교차 정렬"에서 c에 연결되기 때문이다. t(x c)를 상승시키는 효과는 반드시 t(y c)를 하강시키는 것을 의미하는데, 이는 t(y c)를 합하기 때문이다. 그래서 yc가 같이 발생하더라도, 분석 결과 서로 번역이 아니라는 것을 알 수 있다. 실제 데이터로 전자파도 통상적인 국소극단 트랩의 대상이 된다.

음성 인식을 위한 HMMs

"스키"의 진동 파괴

수십 년 동안, 과학자들이 기술적이고 분석적인 해결책을 찾으면서 언어 인식은 난관에 봉착하는 것처럼 보였다. 아래의 음파 p(t)는 "스키"라는 단어를 사용하여 생성된다.

그것의 네 개의 뚜렷한 부분은 매우 다른 특성을 가지고 있다. 화자의 두뇌의도, 과 성대의 상태, 또는 '전화기' 그 자체 등 여러 단계의 발전기(숨겨진 변수) 중에서 선택할 수 있다. 전화는 유추되어야 할 선택의 발생기이며 그것은 그 단어를 시끄럽고 매우 가변적인 방식으로 암호화한다. 음성 인식에 관한 초기 연구는 p(t)에서 추출한 이항 형상에 기초한 논리 규칙을 사용하여 이러한 추론을 결정적으로 시도했다. 예를 들어, 아래 표는 영어 자음을 구별하는 데 사용되는 몇 가지 특징을 보여준다.

실제 상황에서 신호는 옆을 지나가는 자동차와 같은 배경 소음이나 중간 문장의 기침과 같은 공예품(Mumford의 두 번째 밑그림)에 의해 더욱 복잡해진다. 결정론적 규칙 기반 접근방식은 실패했으며, 예술의 상태(예: 드래곤 네이처 스피킹)는 정밀하게 튜닝된 HMM과 베이지안 MAP 추정기 가족을 사용하여 더 잘한다. 비슷한 이야기들이 비전과 다른 자극 범주에서 연주되었다.

음성 인식에 대한 결정론적 접근 방식
p t k b d g m n f s v z
연속체 + + + +
유성 + + + + + + +
콧물 + +
라비알 + + + + +
코로날 + + + + +
앞쪽 + + + + + + + + + +
스트라이던트 + + + +
(Mumford의 패턴 이론: 지각의 수학 참조)

마르코프 확률 프로세스는 다음과 같이 도식화된다.

지수, 전자파 알고리즘

참고 항목

참조

  1. ^ "Ulf Grenander's Home Page". January 22, 2009. Archived from the original on 2009-01-22.

추가 읽기

  • 2007. Ulf Grenander와 Michael Miller 패턴 이론: 표현에서 추론까지. 옥스퍼드 대학 출판부 페이퍼백. (ISBN 9780199297061)
  • 1994. Ulf Grenander 일반 패턴 이론. 옥스퍼드 과학 출판물 (ISBN 978-0198536710)
  • 1996. Ulf Grenander 이론의 요소들. 존스홉킨스 대학 출판부 (ISBN 978-0801851889)

외부 링크