言語処理学会 第21回年次大会 発表論文集 (2015年3月)

Formal Concept Analysis meets grammar typology
Kow Kuroda
kow.k@ks.kyorin-u.ac.jp
Medical Department, Kyorin University

1Introduction

How to work out a typology of grammar that can help language learners to figure out the grammar features/attributethat they need most seriously at learning a (new) language?
If such a typology exists, it surely will be helpful but it
requires measuring the similarity among grammars of language rather than their vocabularies. How to implement theidea? Everybody knows that grammar is a very complex
entity and it’s really hard to rank features relevant to it.
So-called “language distance” turns out not to be as useful as expected, because it usually measures the rate ofshared vocabulary elements. This could put phylogenic bias
into grammar classification, so that languages with different
types tend to be classified as close when they are branching
off the same root. Discussions of grammar typology tend to
rely on diachronic evidence. This is simply because we areconvinced, perhaps correctly, that grammars have evolved.
Does this mean that it is impossible to think of grammar typologies solely based on synchronic evidence and toexpect them to be useful in actual learning process of a language? This is the very question we want to address in thispaper. And the suggested answer is positive.

Admittedly, the selection of languages in (1) is biased
for well-documented languages with attributes that amend
manually checking, but its was done with two goals in mind.
First, it aims to cover as wide a variety of languages as possible. Second, it aims to include as many phylogenically unrelated languages as possible. The second point is importantbecause this research looks for patterns that would suggest
convergent evolution of grammars without reference to theevolution of human languages that has actually occurred.
Formal Concept Analysis (FCA) (Ganter and Wille 1999)
was used for analysis. FCA is a mathematical approach toclassification and is proved to be powerful enough to handle data with essential complexity efficiently. Building on
lattice theory, it works on a “formal context” and produces
a “Hasse diagram” as result.
The formal context in Figure 1 was manually preparedand FCA was applied to it.2) ConceptExplorer 1.33)
was used to perform FCA with drawing options: Layout =minimal intersection, Draw mode = stability(other options don’t affect results).

3 Results

We compare two kinds of result. One kind is FCA in which
all attributes are used, and therefore the result is “uncompromised.” Another kind is FCA in which a selection of attributes are used, and therefore the result is “compromised.”
The 15 languages listed in (1) were selected:
This selection is done, through trial and error, to optimize(1) Bulgarian, Chinese, Czech, English, French, Finnish, Ger- of the results. ConceptExplorer 1.3 has an option Show
man, Hebrew, Hungarian, Japanese, Korean, Latin, Russian, collisions to assist this process.
Figure 2 shows the “uncompromised” FCA. Compared
Swahili, and Tagalog
to “compromised” FCAs, this form of FCA is not really
After dozens of tests with trial and error, the following 24 revealing, but some note would be helpful about it.
First, the lower in the Hasse diagram a language is, theattributes were selected:1)
more feature-loaded its grammar is. In this respect, lan(2) A1 HAS DEFINITE ARTICLE; A2 HAS INDEFINITE ARTICLE; A3 N EN - guages directly connected to the bottom such as Swahili,Hebrew, Hungarian, Russian/Czech, Finnish, French, Latin,CODES PLURALITY ; A4 N ENCODES CLASS ; A5 N ENCODES CASE ;A6 RELATIVE CLAUSE FOLLOWS N; A7 HAS POSTPOSITIONS; A8 HAS German, are languages with most “feature-loaded” (andcomplex) grammars. On the other hand, Chinese has a less
PREPOSITIONS ; A9 A AGREES WITH N- PLURALITY ; A10 A AGREES WITH4)
N- CLASS; A11 A AGREES WITH N- CASE; A12 A FOLLOWS N; A13 O feature-loaded (and simple) grammar.
MUST FOLLOW V ; A14 REQUIRES S UBJECT ; A15 V ENCODES VOICE ;Second, uncompromised use of all features rarely yields a
A16 V ENCODES TENSE; A17 V ENCODES ASPECT; A18 V AGREES WITH good analysis. The following criteria are presumed to assess
S UBJECT; A19 V ENCODES PERSON; A20 V ENCODES PLURALITY; A212) Many details of the attribute-value pairs are admittedly debatable andV ENCODES N- CLASS; A22 V INFINITIVE IS DERIVED; A23 V AGREES
are open to critical assessment in that some of them look illegitimate toWITH O BJECT ; A24 HAS TENSE AGREEMENT

2

Data and Analysis

1) After experiments, a decision was made to let (N) CLASS to include

G ENDER, knowing that this may deviate from usual practice in linguistics. This means that G ENDER is treated in the same way as “Nounclasses” found in languages like Tagalog and Swahili.

salted linguists.
3) http://conexp.sourceforge.net/4) It is out of the scope of this research to ask what determines the complexity of a grammar, but it is worth a mention that the size of speaker
population correlates with it (Lupyan and Dale 2010).

― 329 ―

Copyright(C) 2015 The Association for Natural Language Processing.
All Rights Reserved.

has_ has_ N_en
relati has_ has_ A_agr A_ag A_ag
O_m
V_ag V_enc
V_en V_en V_en V_en V_infi V_ag tens
defi indef codes N_en N_en ve_cl post prep ees_w rees_ rees_ A_fo ust_f requi rees_ odes_ V_en code code code code nitive_ rees_ e_ag
nite inite _plur codes codes _follo posit ositio _Nplu w_Nc w_Nc llows ollo res_ w_Su plural codes s_voi s_ten s_per s_as is_deri w_O rees check
Language_art _art ality _class _case ws_N ions ns
rality lass ase_N w_V Subj bj
ity_class ceseson pect vedbj
ment _sum
Bulgarian
10
1
10
101
1
100001
10111100013Chinese
0000000100001000010000003Czech
00111101111000111111110016English
11
100
10
100001
1
100111010113
Finnish00
101111
10
10001
101
1
10
10013French
11110101
1101111101
110
101
18
German111111011
1
100
11
101110101
18
Hebrew
101
10101110110111111110017
Hungarian
111001
10000000110111111013Japanese000000
100000000001
1001004
Korean000000100000000001
100
1004
Latin
001
11101111
1001
101
1
1010116
Russian0011110111
1000111111110016
Swahili
00110101110110111111111017Tagalog
00000101000110101
10010109CountAverage

60.4

40.3

110.73850.53 0.33

120.8

40.3

120.8

98
50.6 0.53 0.33

50.3

60.4

30.2

120.8

100.67

50.33

15
1

130.9

110.7

70.5

120.8

3
0.2

4
0.3

190
12.7

Figure 1: formal context encoding 15 languages with 25 attributes

Figure 2: Uncompromised FCA: red indicates “collision”

the goodness of FCA: A Hesse diagram is good if i) objects
are as much separated as possible (condition 1), but ii) there
are as few empty nodes as possible (condition 2), and iii)
the diagram is in a geometrically good shape (condition 3).
For example, the Hasse digram in Figure 2 fails to meet
conditions 2 and 3.
The three conditions cancel each other, because they arein relation of “trade-off” that need to be “compromised.”This means that the there is no fast and sure way to obtain the optimal output by FCA. Thus, we need to manually compare several results generated under different selections of attributes to obtain optimal ones. This is what isattempted in the following.

3.1

Optimization 1

Optimization can be achieved by discarding either objects
or attributes. In our analysis, all objects are expected to be
sufficiently reliable and were retained.
The Hasse diagram in Figure 3 is one of the “compromised” FCAs. We contend that this is the best optimizationin that conditions 1 and 3 are fully satisfied at cost of discarding condition 2, as far as we see reason that accidental
gaps in data, either in terms of object or attribute, often result in empty nodes.

Figure 3: Compromised FCA 1 with 5 empty nodes
3.1.1 Feature interactions
Figure 3 presents the result of separating attributes into
“converging” attributes in (3) and “diverging” attributes in(4):(3) A1 HAS DEFINITE ARTICLE; A2 HAS INDEFINITE ARTICLE; A3 N EN CODES PLURALITY ; A4 N ENCODES CLASS ; A6 RELATIVE CLAUSE FOL LOWS N ; A8 HAS PREPOSITIONS ; A9 A AGREES WITH N- PLURALITY ;A10 A AGREES WITH N- CLASS; A12 A FOLLOWS N; A14 REQUIRESS UBJECT; A15 V ENCODES VOICE; A16 V ENCODES TENSE; A18 V
AGREES WITH S UBJECT ; A19 V ENCODES PERSON ; A20 V ENCODESPLURALITY ; A21 V ENCODES N- CLASS ;(4) A5 N ENCODES CASE; A7 HAS POSTPOSITIONS; A13 O MUST FOLLOW
V; A17 V ENCODES ASPECT; A22 V INFINITIVE IS DERIVED; A23 V
AGREES WITH O BJECT ; A24 HAS TENSE AGREEMENT ;Attributes in (4) are called “divergent,” because inclusion of them inevitably adds undesirable complications tothe output. The best account for this would be that certain
attributes get inconsistent values and thus contradictions aregenerated. But this is not necessarily due to “errors” in encoding. 4.3 discusses it more deeply.

― 330 ―

Copyright(C) 2015 The Association for Natural Language Processing.
All Rights Reserved.

3.1.2

Implications among attributes

The FCA in Figure 3 expresses the following:(5) Correlations (stated bottom-up)
a. Two attributes, A4 N ENCODES CLASS and A10 A AGREESWITH N- CLASS , correlate, if not equivalent.
b. Two attributes, A19 V ENCODES PERSON, and A20 V EN CODES PLURALITY , correlate, if not equivalent.
c. Two attributes A6 RELATIVE CLAUSE FOLLOWS N, and A18
V AGREES WITH S UBJECT, correlate, if not equivalent.
(6) Implications (stated bottom-up, indirect implications
not expanded)
a. A2 HAS INDEFINITE ARTICLE is a precondition for A14
REQUIRES S UBJECT .
b. A1 HAS DEFINITE ARTICLE is a precondition for A2 HAS
INDEFINITE ARTICLE .
c. A9 A AGREES WITH N- PLURALITY is a precondition for
A4 N ENCODES CLASS and A10 A AGREES WITH N- CLASS.
d. A20 V ENCODES PLURALITY is a precondition for A4 NENCODES CLASS , A9 A AGREES WITH N- PLURALITY , and A10A AGREES WITH N- CLASS.
e. A19 V ENCODES PERSON and A3 N ENCODES PLURALITY area precondition for A20 V ENCODES PLURALITY.
f. A8 HAS PREPOSITIONS is a precondition for A14 REQUIRESS UBJECT, A9 A AGREES WITH N- PLURALITY, A12 A FOLLOWS
N, and A21 V ENCODES N- CLASS.
g. A15 V ENCODES VOICE and A6 RELATIVE CLAUSE FOLLOWS
N are a precondition for A16 V ENCODES TENSE, A3 N
ENCODES PLURALITY , A12 A FOLLOWS N , and A18 V AGREESWITH S UBJECT .
h. A16 V ENCODES TENSE is a precondition for A19 V EN CODES PERSON and A3 N ENCODES PLURALITY .
3.1.3

Figure 4: Compromised FCA 2 with 4 empty nodes
3.2.2 Optimization 3
Figure 5 presents Optimization 3 in which A1 and A9 arediscarded additionally, generating 3 empty nodes. This
Hasse diagram involves three empty nodes, without nodeoverloading. But the geometry is less symmetrical.

Beyond Greenberg’s universals

Obviously, (5) and (6) re-capture some of Greenberg’s language universals (Greenberg 1966), but the Hasse diagramin Figure 3 tells more, provided that it is a correct analysis. What FCA gives us is not a “list” of implications, buta complex “space” encoding how attributes are combined
to define grammar types in a hierarchical fashion, thereby
providing something like a “geometry” of grammars.

Figure 5: Compromised FCA 3 with 3 empty nodes

3.2.3 Optimization 4

3.2

Comparison with other optimizations

In what follows, we compare the FCA in Figure 3 against
other possibilities to defend that it is the best result under
the available data. Note, however, that the comparison is
not intended to be exhaustive. Space limitation discourages
us to investigate all the relevant combinations of attributes
even if it is practically possible.

Figure 6 presents Optimization 4 in which A9, A12 andA20 are discarded additionally, generating 2 empty nodes.
This Hasse diagram involves two empty nodes, with overloaded nodes: at one node, Swahili and Russian/Czech areundifferentiated; at another, French and German undifferentiated. This suggests that the result is not optimal.
3.2.4 Optimization 5

3.2.1

Optimization 2

Figure 4 presents Optimization 2 in which A20 V ENCODES PLU RALITY is discarded additionally, generating 4 empty nodes.
This Hasse diagram involves four empty nodes, without
overloaded nodes. The major difference from Figure 3 isthat the geometry is simpler and less symmetrical, suggesting the result is sub-optimal.

Figure 7 presents Optimization 5 without empty nodes under the selection of attributes in A3, A4, A5, A6, A7, A8, A9,A10, A11, A15, A16, A18, A19, and A20.
This Hasse diagram is free from empty nodes, but somenodes are overloaded. This means that certain objects areunder-represented and FCA fails to differentiate them sufficiently. This means that this result is not optimal.

― 331 ―

Copyright(C) 2015 The Association for Natural Language Processing.
All Rights Reserved.

Figure 6: Compromised FCA 4 with 2 empty nodes

derstand the representation at its face value. Most notably,
encoding of attributes suffers from abstractions at severallevels. For one, grammatical categories like Noun, Verb
Adjective are abstractions. In reality, each of them subsumes a group of words that behave differently. For another,V subsumes different word classes such as Present, Past,Participle, Perfective, Imperfective, Infinitive. The same isvery true of Adjectives, too. For yet another, the operational
definition Case is problematic, to say the least. Also, it is
not clear how far the notion Noun class should cover. All
this encourages us to reinterpret what the Hasse diagrams
represent more probabilistically. Perhaps, grammar types
are best understood as “attractors” in a dynamical system,in analogy with “niches” over a “fitness” landscape.

4.3 Why divergent attributes?

Figure 7: Compromised FCA 5 without empty nodes

4Discussion

4.1

Relativized learnability index

The Hasse digram in Figure 3 presents something like a“common ground” of grammars: A18 V AGREES WITH S UBJECT(and A19 V ENCODES PERSON as one of its most accessible incarnation). This feature is so important that we can suspect alarge and deep gap between inside and outside the domain
in which it holds. Only Chinese, Japanese and Korean areoutside the domain. Another influential attribute is A3 N EN CODES PLURALITY . Many languages have grammars sensitive toit. This would create another barrier in language learning.
This has important implications for language learning. In
fact, it is imaginable that learners face more difficulty if
their mother tongue is one of the agreement-free languages.
If a learner speaks a language without person-agreement
on verbs and plurality-encoding on nouns, it would posea handicap in his or her learning. We can reasonably predict that, other things being equal, descending the Hasse
diagram poses more difficulty in learning. This defines relativized learnability index for grammar.

4.2

Caveat on the nature of representation

FCA is a powerful and useful tool to reveal about grammar
types; yet proper interpretation of its results demands additional explanation. In the Hasse diagrams, grammar types
are represented as discrete objects. We are discourage to un-

Why are some attributes divergent? We can see two possibilities for this, on different grounds. First, it is rather likelythat certain attributes were specified for “wrong” values in
the formal context used. This would have produced inconsistencies in encoding. Why is this the case? The answer
would be, at least in part, that certain grammatical phenomena are ill-defined. Case, for example, turned out to be too
unreliable an attribute to add complications, thereby suggesting that its identification involves essential difficulty.
There is another possibility, however, which is of moretheoretical importance. For any existing language, there isa chance that attested grammatical features are accidentally
valued, or even spurious, and there is no systematic way todecide which ones are the case. Careful choice of relevant
features is essential for valid generalizations.
After all, language would be a “system of trade-offs” thatinvolves counterbalancing a large number of costs and benefits. Why is grammar not so? If this line of thought isvalid, it will be completely misguided to try to think ofgrammar as a “systematic” phenomenon and expect it tobe properly characterizable by a “monolithic” system ofrigid “rules and principles.” Knowledge of language mustbe much more probabilistic, if not stochastic, and involves
much more complexity in it.

5 Conclusion
This paper presented a FCA-based analysis of grammar typology in terms of attributes/features such as A19 V ENCODESPERSON , The presented approach gives promising results that
capture implications among attributes of grammar and automatically identifies grammar types, though the results arepreliminary in many respects.

References
Ganter, B. and R. Wille (1999). Formal Concept Analysis:
Mathematical Foundations. Berlin: Springer-Verlag.
Greenberg, J. H. (1966). Language Universals: With SpecialReference to Feature Hierarchies. The Hague: Mouton.
Lupyan, G. and R. Dale (2010). Language structure is partly
determined by social structure. PLoS ONE 5(1), 1–10.

― 332 ―

Copyright(C) 2015 The Association for Natural Language Processing.
All Rights Reserved.