The Stack Overflow podcast is back! Listen to an interview with our new CEO.

# Tag Info

32

Not really, no. Programming languages have become more like natural languages only in the sense of “words we have in english” (sic). A key feature of programming languages is that they are not ambiguous. When you write a program and execute it, it has a well-defined meaning, which is its behavior. If you want to write a program that works as intended (a ...

20

This problem is known as the “minimum common string partition problem.” (More precisely, the answer in the minimum common string partition problem equals the answer in your problem plus 1.) Unfortunately, it is NP-hard, even with the restriction that each letter occurs at most twice in each of the input strings, as is proved by Goldstein, Kilman, and Zheng ...

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 ...

9

This is a followup to Tsuyoshi Ito's answer above, summarizing the most relevant portion of the GKZ05 paper he cited. The paper proves a reduction to the Maximal Independent Set (MIS) problem. Construct a graph $G$ whose vertices are pairs $(i, j)$ such that $a_i = b_j$ and $a_{i+1} = b_{j+1}$. Connect vertices $(i, j)$ and $(k, \ell)$ (where $i≤k$) with an ...

9

Information retrieval is based on a query - you specify what information you need and it is returned in human understandable form. Information extraction is about structuring unstructured information - given some sources all of the (relevant) information is structured in a form that will be easy for processing. This will not necessary be in human ...

7

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 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 ...

6

There are a lot of different approaches that you could take. While the commenters are right, coming up with a distance metric is important, based on my own experience, finding good representations of your words/phrases is going to be significantly more important. Most of the "semantic" clustering algorithms that immediately come to mind are document level, ...

6

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 ...

6

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

What you want to solve is a string matching problem. Wikipedia (and any textbook on the matter) contains a rich list of algorithms with their respective runtimes. Be aware that they give worst-case runtimes. Different algorithms behave differently on natural text; some perform better because of the large alphabet and some worst because of its repetitive ...

5

As far as I know, much of the speech recognition software is build using Hidden Markov Models (HMM) where observations are individual sound phonemes, and the states correspond to words (or some partitions of the words). I don't think the systems take into account grammar or sentence structure in the sense that they encode rules of English so much as they ...

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 ...

4

In general, the problem of identifying dates and other temporal markers in text is called the problem of extracting temporal references. The search linked will take you to papers related to this.

4

Here's a simple technique. Train an LDA using something like MALLET over your collection of texts. For each pair of documents you want to compare, obtain the topic distributions and compute the Hellinger distance between them. Things you can tweak include term weighting, the LDA hyperparameters, and the metric for comparing distributions. Term weighting ...

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

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

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

You can try simple probabilistic graphical models, the simplest one being Naive Bayes. One way to do this would be to represent a portion of text as a word frequency vector, that will be associated with a topic (the "class variable"). Then you use many such texts that are associated with topics to train your model (i.e. you model the probability of a ...

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

The first thing you need to consider is that stemming rules are language-specific - a stemmer for the English language will not work for Spanish. That being said, there is already an implementation which you can use, it's called Snowball and it already has a Spanish stemmer you can use. The only thing you need to figure out is how you want to install and ...

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