# Tag Info

14

The usual trick to avoid this underflow is to compute with logarithms, using the identity $$\log \prod_{i=1}^n p_i = \sum_{i=1}^n \log p_i.$$ That is, instead of using probabilities, you use their logarithms. Instead of multiplying them, you add them. Another approach, which is not so common, is to normalize the product manually. Instead of keeping just ...

8

http://gate.ac.uk/ie/ gives a very nice, concise distinction: Information Extraction is not Information Retrieval: Information Extraction differs from traditional techniques in that it does not recover from a collection a subset of documents which are hopefully relevant to a query, based on key-word searching (perhaps augmented by a thesaurus). ...

7

Answering knowingly this question would require experiments. I am sure there is some data for natural languages, where it is a common problem. I recall from memory that one study gave ridiculously small figures for natural language, which is not too surprising. If you take 5 consecutive word in a sentence (the figure I recall, without being sure), there is a ...

7

I recommend you look at methods in the NLP literature for parsing a sentence and identifying its structure, classifying the tense of the sentence and the words present in it, and identifying the subject and object of the sentence. That should help you build a more accurate classifier. If you extract suitable features, given the parse tree, and then apply a ...

7

I am afraid the phrasing of the question misled me (though I did know better) in first seeing model theory as applying to any two arbitrary mathematical structures, and being the study of homomorphisms of mathematical structures. Actually this is wrong. Model Theory already contains the idea of syntax and semantics, more or less as I define it below. It ...

7

What constitutes a proof in a system like this is a derivation which is a tree of rule applications. The above translation function is defined by (structural) recursion over that tree. Note, this is why it labels the premises in the rules with $\delta$. This is intended to be mnemonic for "derivation". I'm guessing but $\mu$ and $\nu$ appear to need to be ...

6

Are extensions required? Not really. You can take an axiomatic description of a modal logic and simply provide a "primitive" lambda term for each. The modal operators would become type constructors. Haskell's IO monad can be viewed this way. Coherence conditions like the monad laws would provide some conversions between terms. A different approach, which ...

5

As D.W. said, the task of classifying words as noun, verb, etc. is called part-of-speech tagging: The machine learning algorithm typically used for this purpose is the Log-Linear Model (aka. Maximum-Entropy, in short MaxEnt). It is actually pretty straightforward: Assume you read the sentence sequentially (left to right, or right to left) Let $h$ be the ...

5

This is a standard problem in Natural Language Processing (NLP). Classifying whether each word is a noun, verb, etc., is known as "part-of-speech tagging". Searching on that term should turn up a lot of information about how to do that. If you want to tag the words in some other way, you might be able to use other tagging algorithms. They generally use ...

5

To beging with, the expression "formal language" may refer to formally defined sets of string as considered in the theory of automata and formal languages. I shall write that "Formal Language" with capital first letters. But "formal language" may also refer to some kind of language that is intended for expressing meaning, but is precisely defined ...

5

Building on the comments, there's something called the Needleman–Wunsch algorithm, for which you can find the lowest 'cost' alignment of two sequences (phonemes). You can get a good 'confusion cost matrix' by taking a normal confusion matrix and taking the log-odds of each confusion pair. As long as your set of words is less than 33k or so, you should be ...

5

The empty word $\epsilon$ isn't an integer. Integers are $0, 1, 2, 3, \dots, 10, 11, \dots$ Clearly none of them have $0$ letters when you write them, and hence they are not $\epsilon$. Hence, you want an integer to be of the form $\text{/[0-9][0-9]$^\ast$/}$.

4

For what I know, people from formal languages, logic and natural languages may have slightly different ideas about these notions. That is why (at least in the past) the wikipedia page for formal languages has been terribly messy. Starting from the bottom: Raphael is right. Syntax is the strings itself. The task of formal languages is to research methods to ...

4

Maybe one should first define what is a natural language processing (NLP) problem. For example, Context-Free (CF) grammars and languages were introduced by linguists (Chomsky type 2 language, work of Bar-Hillel and others). Ambiguity is a major problem in Linguistics for real sentence analysis, and in the formal study of CF grammars (ambiguity) and ...

4

detecting passive voice is an AI application also used/ implemented in grammar checker/ correction software with proprietary algorithms. there is a complexity/ accuracy tradeoff. simpler algorithms can be useful and better accuracy requires more sophisticated algorithms. here are two papers on the subject including a masters thesis (60p). final link is an ...

4

It all very much depends on how you model these concepts where syntax end and semantics start. When the syntax is described using a context free grammar, then there are aspects of the language not expressed in that model so we say those aspects are the semantics. However, there are many other ways of expressing (or modelling) the syntax of the language. ...

4

Morphological parsing requires a lexicon (stems and their part of speech) , morphotactics (ordering of morpheme classes), and orthographic rules (e.g. fox + PL = foxes rather than foxs). The preferred approach is to use a composition of finite state transducers to map a surface level representation (e.g., foxes) into its lexical representation (e.g., fox +N ...

4

Theoretically, you can nest sentences arbitrarily depth, by using subclauses and this excluded any finite state mechanism. The inventor of the phrase structure grammars himself looked at finite state languages, and compared them with the model of phrase structure grammars. The abstract of his paper Finite State languages reads: We find that no finite-state ...

4

You are looking for currying and uncurrying which transform functions of type $A \times B \to C$ to functions of type $A \to (B \to C)$, and vice versa. Currying takes IS to is, while uncurrying takes is to IS. This is a standard and very basic technique in $\lambda$-calculus. There are many manifestations of currying and uncurrying, for instance in ...

3

As far as I know, they do the same way they created things like Penn tree bank. They have a panel of experts, usually linguists, who sat together and decided synset taxonomy based on various widely used dictionaries. PS: Please up-vote me so I can up vote others, thanks :)

3

NLP is a big place, you might want to be more specific. Within information retrieval, stemming is a linguistic idea that has become useful as a heuristic means of reducing vocabulary size. As a practitioner I learned about it from An Introduction to Information Retrieval.

3

Like most things of this nature the best method is best found by empirical evaluation. One thing worth noting is that most smoothing schemes can be thought of as the incorporation of a prior into your likelihood estimate. For example if you are trying to estimate the parameter $\theta$ of a binary random variable $X$ and you have data $\mathcal{D} = \{x_1, \... 3 Question: Where can I access automatically generated (spam) webpages? You could use: a parody generator program. They're usually based on Markov chains (e.g. SubredditSimulator) or context-free grammars (e.g. the well known SCIGen... according to the authors "with Markov chains you might get something syntactically correct, but it is likely to be boring"!)... 3 Morphological tags can help the parser. On the other hand, the complete sentence structure, maybe even the paragraph context may help to finally disambiguate possible tags for a token. So there is no yes/no answer. Except, maybe, that tagging is, afaik, usually not attributed as work of the lexer, but rather a module of its own. 3 This isn't the best way but it's simple and fast: preprocess the input with the Porter Stemmming algorithm (it's a process for removing the commoner morphological and inflexional endings from words in English) or similar (take a look at Snowball) preprocess the input flagging words before and after every negation ("never", "not", "no", "n't"): the movie ... 3 Build a boolean classifier that classifies a message as either "task" or "not a task". Choose a classifier that can output a confidence score (many classifiers can, including ensembles like random forests; neural networks and deep learning; logistic regression; and more). Train the classifier on many messages. For a collection of 3 messages, apply the ... 3 Assuming that your data comes from a Markovian source, you can estimate the entropy of the source using an optimal compression algorithm such as Lempel–Ziv, whose theoretical version (without limiting the table size) is known to asymptotically converge to the entropy. That is, if the entropy of the source (suitable defined) is$H\$, then the expected ...

3

As far as I can see, your reading list lacks specific NLP introductions. A really good starting point is Dan Jurafsky and Chris Manning's Coursera course (for example here https://www.youtube.com/watch?v=nfoudtpBV68 ). This specifically covers spell checking in one of the first videos. In general, spell checking is a rather easy task, while (convincing) ...

3

Spell checking, grammar checking, proofreading with ML Norvig: How to Write a Spelling Corrector "Artistic Style Transfer" for articles (if it is even possible), i.e. "transfer" Shakespeare's writing style onto a given text. Yes, it is possible. Recurrent neural networks can do this. See The Unreasonable Effectiveness of Recurrent Neural ...

3

If no bracket language examples suffice, your quest is futile. Every context-free-language is a reduction of a bracket/parenthesis language. Reduction comprises homomorphism; intersection with a regular language. This is the Chomsky-Schutzenberger (representation) theorem.

Only top voted, non community-wiki answers of a minimum length are eligible