Wyniki wyszukiwania - BazTech

1

Hilberg’s Conjecture : a Challenge for Machine Learning

Dębowski Ł.

Schedae Informaticae

|

2014

|

Vol. 23

33--44

EN

We review three mathematical developments linked with Hilberg’s conjecture – a hypothesis about the power-law growth of entropy of texts in natural language, which sets up a challenge for machine learning. First, considerations concerning maximal repetition indicate that universal codes such as the Lempel-Ziv code may fail to efficiently compress sources that satisfy Hilberg’s conjecture. Second, Hilberg’s conjecture implies the empirically observed power-law growth of vocabulary in texts. Third, Hilberg’s conjecture can be explained by a hypothesis that texts describe consistently an infinite random object.

2

Przykładowe zastosowanie gradacyjnej analizy danych w badaniach lingwistycznych

Hajnicz E., Dębowski Ł., Wiech M.

Prace Instytutu Podstaw Informatyki Polskiej Akademii Nauk

|

2007

|

Nr 1005

1-40

PL

W niniejszym raporcie przebadano potencjał gradacyjnej analizy danych w odniesieniu do klasyfikacji czasowników względem stylów tekstów zgromadzonych w Korpusie IPI PAN. Ponieważ w Korpusie dominują dwa style: publicystyczny i protokół, analizę przeprowadzono dla dwóch zestawów danych: pełnego i z wyłączeniem wspomnianych stylów. Analogiczny proces analizy przeprowadzono dla danych zagregowanych po kategoriach semantycznych (sensach) czasowników pochodzących z wordnetu. Uzyskane wyniki zostały porównane.

EN

An example of grade data analysis application for linguistic research In the report, the potential of grade analysis is explored for the classification of verbs with regard to the IPI PAN Corpus text styles. Since two styles, publicystyczny (newspapers) and protokół (parliament protocols), dominate in the Corpus, the analysis is performed for two datasets: the entire Corpus and the subcorpus without the dominant styles. An analogous analysis is provided for the data aggregated by means of wordnet-like semantic categories (senses) of verbs. The obtained results are compared.

3

Ergodic decomposition of excess entropy and conditional mutual information

Dębowski Ł.

Prace Instytutu Podstaw Informatyki Polskiej Akademii Nauk

|

2006

|

Nr 993

1-34

EN

The article discusses excess entropy defined as mutual information between the past and future of a stationary process. The central result is an ergodic decomposition: Excess entropy is the sum of self-information of shift-invariant sigma-field and the average of excess entropies for the ergodic components of the process. The result is derived using generalized conditional mutual information for fields of events, developed in the paper anew. Some corollary of the ergodic decomposition is that excess entropy is infinite for the class of processes with uncountably many ergodic components, called here uncountable description processes (UDP's). UDP's can be defined without the use of measure theory and the article argues for their potential utility in linguistics. Moreover, it is shown that finite-order excess entropies (some approximations of excess entropy) are dominated by the expected excess lengths of any universal code. Hence, universal codes may be used for rough estimation of excess entropy. Nevertheless, the excess code lengths diverge to infinity for almost every process with zero excess entropy, which is another corollary of the ergodic decomposition.

PL

W artykule omówiono pojęcie entropii nadwyżkowej zdefiniowanej jako informacja wzajemna między przeszłością a przyszłością procesu stacjonarnego. Centralnym rezulatem jest rozkład ergodyczny entropii nadwyżkowej: Entropia nadwyżkowa równa jest sumie entropii sigma-ciała niezmienniczego i wartości oczekiwanej entropii nadwyżkowej losowej miary ergodycznej procesu. Rezultat ten wynika z własności uogólnionej warunkowej informacji wzajemnej, rozwiniętej w artykule w nowatorski sposób. Korzystając z otrzymanego rozkładu ergodycznego, udowodniono, że entropia nadwyżkowa jest nieskończona dla klasy procesów o nieprzeliczalnie wielu składowych ergodycznych, nazwanych procesami nieprzeliczalnego opisu (PNO). Pokazano, że PNO można zdefiniować bez użycia aparatu teoriomiarowego, i zaargumentowano za ich potencjalną użytecznością w lingwistyce. Ponadto udowodniono, że entropie nadwyżkowej skończonego rzędu (pewne przybliżenia entropii nadwyżkowej) są majoryzowane przez nadwyżkowe długości dowolnego kodu uniwersalnego. Zatem kody uniwersalne mogą służyć do zgrubnego szacowania entropii nadwyżkowej. Jednakże, z rozkładu ergodycznego wynika także, że nadwyżkowe długości kodów uniwersalnych rozbiegają do nieskończoności dla prawie każdego procesu o zerowej entropii nadwyżkowej.

4

Tagowanie i dezambiguacja morfosyntaktyczna : przegląd metod i oprogramowania

Dębowski Ł.

Prace Instytutu Podstaw Informatyki Polskiej Akademii Nauk

|

2001

|

Nr 934

1-31

PL

Przedstawiono aktualne metody i dostępne oprogramowanie do automatycznego tagowania i uczenia się tagerów. Omówiono skuteczność zastosowań przedstawionych metod i oprogramowania do dezambiguacji morfosyntaktycznej tekstów w językach naturalnych.

EN

We present state-of-the-art methods and available software for automatic tagging and tagger learning. Furthermore, we discuss applicability of presented methods and software for morphosyntactic disambiguation of texts in natural languages.

5

Quantitative considerations on finding the shortest descriptions for meaningful symbolic sequences

Dębowski Ł.

Prace Instytutu Podstaw Informatyki Polskiej Akademii Nauk

|

2001

|

Nr 924

1-36

EN

The notes provide elements of a new quantitive theory for unsupervised learning from pragmatic language communication. It is argued that the suitable quantitive inference framework free from paradoxes should be based on minimum description lenght (MDL) interpreted as a simplified algorithmic complexity rather than on classical frequwntist probability. Furthermore, it is argued that recently observed non-extensivity of entropy in meaningful symbolic sequences can arise if and only if unsupervised acquisition of the MDL theories for these sequences produces infinite theories and when the unsupervised acquisition is optimal as well. Such result shakes rigorously the belief that a finite formal theory of natural language could be constructed by hands of any experts. On the other hand, unsupervised machine learning is pointed out as a feasible and the only right way to implementing language competence into Ais. From this perspective, a promising compression-learning algorithm by de Marcken, its efficiency and its extension are discussed. Important parallels with research in cognitive science and statistical physics are pointed out, as well. Thus, the notes may be interesting not only for computer scientists and linguists but also for other statistical and symbolic theorists.

PL

W niniejszych notatkach przedstawiono elementy nowej, ilościowej teorii uczenia bez nadzoru na podstawie pragmatycznej komunikacji językowej. Podano argumenty wskazujące na to, że odpowiedni formalizm wnioskowania ilościowego wolny od paradoksów powinien bazować na minimalnej długości opisu jako uproszczonej mierze złożoności algorytmicznej, a nie na prawdopodobieństwie jako klasycznej mierze częstości. Pokazano także, że niedawno zaobserwowana nieekstensywność entropii niepustych semantycznie ciągów symboli zachodzi wtedy i tylko wtedy, gdy teorie najkrótszych opisów dla tych ciągów mogą rosnąć nieskończenie, a także wtedy, gdy uczenie bez nadzoru zachodzi maksymalnie efektywnie. Rezultat ten w sposób ścisły podważa przekonanie, że skończona formalna teoria języka naturalnego może być podana przez jakiegokolwiek specjalistę. Z drugiej strony, wynik ten ukazuje maszynowe uczenie bez nadzoru jako perspektywicznie realizowalny a zarazem jedyny właściwy sposób implementowania kompetencji językowej w sztucznej inteligencji. Z tego względu przeprowadzono dyskusję obiecującego algorytmu uczenia opartego na kompresji, podanego przez de Marckena. Rozważono wstępnie możliwe rozszerzenia tego algorytmu. Ponieważ przedstawiono istotnie powiązania pomiędzy omawianymi kwestiami a bieżącymi badaniami w kognitywistyce i fizyce statystycznej, niniejsze notatki mogą zainteresować nie tylko informatyków i lingwistów, ale także innych teoretyków zajmujących się naukami statystycznymi i symbolicznymi.