Planar Languages and Learnability

Alexander Clark; Christophe Costa Florêncio; Chris Watkins; Mariette Serayet

Planar Languages and Learnability

Alexander Clark, Christophe Costa Florêncio, Chris Watkins, Mariette Serayet

Philosophy

Research output: Chapter in Book/Report/Conference proceeding › Conference paper

10 Citations (Scopus)

Abstract

Strings can be mapped into Hilbert spaces using feature maps such as the Parikh map. Languages can then be defined as the pre-image of hyperplanes in the feature space, rather than using grammars or automata. These are the planar languages. In this paper we show that using techniques from kernel-based learning, we can represent and efficiently learn, from positive data alone, various linguistically interesting context-sensitive languages. In particular we show that the cross-serial dependencies in Swiss German, that established the non-context-freeness of natural language, are learnable using a standard kernel. We demonstrate the polynomial-time identifiability in the limit of these classes, and discuss some language theoretic properties of these classes, and their relationship to the choice of kernel/feature map.

Original language	Undefined/Unknown
Title of host publication	Proceedings of the 8th International Colloquium on Grammatical Inference (ICGI)
Pages	148-160
Number of pages	13
Volume	4201 LNAI
Publication status	Published - 2006

Cite this

@inbook{e52273ddd0e0431b9bc28e36bb336a36,

title = "Planar Languages and Learnability",

abstract = "Strings can be mapped into Hilbert spaces using feature maps such as the Parikh map. Languages can then be defined as the pre-image of hyperplanes in the feature space, rather than using grammars or automata. These are the planar languages. In this paper we show that using techniques from kernel-based learning, we can represent and efficiently learn, from positive data alone, various linguistically interesting context-sensitive languages. In particular we show that the cross-serial dependencies in Swiss German, that established the non-context-freeness of natural language, are learnable using a standard kernel. We demonstrate the polynomial-time identifiability in the limit of these classes, and discuss some language theoretic properties of these classes, and their relationship to the choice of kernel/feature map.",

author = "Alexander Clark and {Costa Flor{\^e}ncio}, Christophe and Chris Watkins and Mariette Serayet",

year = "2006",

language = "Undefined/Unknown",

volume = "4201 LNAI",

pages = "148--160",

booktitle = "Proceedings of the 8th International Colloquium on Grammatical Inference (ICGI)",

}

TY - CHAP

T1 - Planar Languages and Learnability

AU - Clark, Alexander

AU - Costa Florêncio, Christophe

AU - Watkins, Chris

AU - Serayet, Mariette

PY - 2006

Y1 - 2006

N2 - Strings can be mapped into Hilbert spaces using feature maps such as the Parikh map. Languages can then be defined as the pre-image of hyperplanes in the feature space, rather than using grammars or automata. These are the planar languages. In this paper we show that using techniques from kernel-based learning, we can represent and efficiently learn, from positive data alone, various linguistically interesting context-sensitive languages. In particular we show that the cross-serial dependencies in Swiss German, that established the non-context-freeness of natural language, are learnable using a standard kernel. We demonstrate the polynomial-time identifiability in the limit of these classes, and discuss some language theoretic properties of these classes, and their relationship to the choice of kernel/feature map.

AB - Strings can be mapped into Hilbert spaces using feature maps such as the Parikh map. Languages can then be defined as the pre-image of hyperplanes in the feature space, rather than using grammars or automata. These are the planar languages. In this paper we show that using techniques from kernel-based learning, we can represent and efficiently learn, from positive data alone, various linguistically interesting context-sensitive languages. In particular we show that the cross-serial dependencies in Swiss German, that established the non-context-freeness of natural language, are learnable using a standard kernel. We demonstrate the polynomial-time identifiability in the limit of these classes, and discuss some language theoretic properties of these classes, and their relationship to the choice of kernel/feature map.

M3 - Conference paper

VL - 4201 LNAI

SP - 148

EP - 160

BT - Proceedings of the 8th International Colloquium on Grammatical Inference (ICGI)

ER -