Episode #125 of the Stack Overflow podcast is here. We talk Tilde Club and mechanical keyboards. Listen now

Questions tagged [natural-language-processing]

Natural language processing (NLP)

Filter by
Sorted by
Tagged with
31
votes
5answers
3k views

Finding interesting anagrams

Say that $a_1a_2\ldots a_n$ and $b_1b_2\ldots b_n$ are two strings of the same length. An anagramming of two strings is a bijective mapping $p:[1\ldots n]\to[1\ldots n]$ such that $a_i = b_{p(i)}$ ...
26
votes
9answers
3k views

Are programming languages becoming more like natural languages?

Can we study programming languages in the context of linguistics? Do programming languages evolve naturally in similar ways to natural languages? Although full rationality, and mathematical ...
19
votes
1answer
801 views

Compression of domain names

I am curious as to how one might very compactly compress the domain of an arbitrary IDN hostname (as defined by RFC5890) and suspect this could become an interesting challenge. A Unicode host or ...
13
votes
2answers
661 views

Identifying events related to dates in a paragraph

Is there an algorithmic approach to identify that dates given in a paragraph correlate to particular events (phrases) in the paragraph? Example, consider the following paragraph: In June 1970, the ...
11
votes
4answers
17k views

Relation and difference between information retrieval and information extraction?

From Wikipedia Information retrieval is the activity of obtaining information resources relevant to an information need from a collection of information resources. Searches can be based on ...
10
votes
1answer
582 views

Implementation of Naive Bayes

I am implementing a Naive Bayes algorithm for text categorization with Laplacian smoothing. The problem I am having is that the probability approaches zero because I am multiplying many small ...
8
votes
2answers
132 views

What are some efficient ways to find the differences between two large corpuses of text that have similar, but differently ordered content?

I have two large files containing paragraphs of English text: The first text is about 200 pages long and has about 10 paragraphs per page (each paragraph is 5 sentences long). The second text ...
7
votes
3answers
2k views

Complexity of natural language processing problems [closed]

Which natural language processing problems are NP-Complete or NP-Hard? I've searched the natural-lang-processing and complexity-theory tags (and related complexity tags), but have not turned up any ...
6
votes
2answers
678 views

Are syntax and semantic just 2 structures such that one is a model of the other?

The syntax of a language is a structure. The semantic of a language is a structure. The semantic of a language is a model of its syntax. And that's all ? The duality syntax/semantic is just model ...
5
votes
3answers
4k views

Word classification algorithms

I am looking for algorithms to classify words in a paragraph of text. I am particularly interested in a classification to determine if a certain word is noun, verb, etc., but also looking for any kind ...
5
votes
2answers
153 views

When did commercial Speech Recognition first begin using grammar (sentence structure) for prediction?

It seems as though modern speech recognition (e.g., through Android, iOS phones) make use of grammar or sentence structure. (e.g., it might have a tough time distinguishing between "grammar" and "...
5
votes
2answers
710 views

Estimate entropy, based upon observed frequency counts

Suppose I have $n$ independent observations $x_1,\dots,x_n$ from some unknown distribution over a known alphabet $\Sigma$, and I want to estimate the entropy of the distribution. I can count the ...
5
votes
2answers
474 views

Algorithm to find the probability of a given text to be about a large topic

I want the conditional probability for each topic (being the word that we give as input). For example, the text being have seen and reviewed your requirements you posted here. If you can give me ...
5
votes
1answer
601 views

nlp: phonetic edit distance between a word and the closest of a set of words

Let's say someone is using Dragon Dictation, Google Speech, or some other free form dictation software (it will recognize anything they say to the best of its ability). I have some reasonably large ...
5
votes
2answers
670 views

How to represent text for a program to add punctuation to a block of text?

I want to try and make a program where I remove the punctuation from a block of text and it then inputs it in the correct places. I have started with a simpler element of just using text and spaces, ...
5
votes
1answer
530 views

Determining interests from Twitter text using Latent Dirichlet Allocation

I would like to determine interests or hobbies that people have given their Twitter timeline data. Their timeline is their historical collection of tweets. The result I am trying to achieve is to ...
4
votes
1answer
90 views

How to express modalities in lambda calculus - are some extensions required?

Lambda calculus can be used for encoding semantics of natural language, e.g. http://yoavartzi.com/tutorial/ contains full details about semantic parsing of natural language: converting natural ...
4
votes
2answers
112 views

Advice needed. NLP and ML. Where to start? [closed]

Hi fellow computer scientists, I just began my journey to the world of ML and NLP so please bear with me. I'm hoping to find some guidance here. I would be very grateful if anyone could point me in ...
4
votes
1answer
4k views

Semantic clustering

I have a very specific question about semantic clustering. I have a list of words/phrases. I want to run an intelligent semantic clustering algorithm on this list. Please let me know what the ...
4
votes
1answer
200 views

Semantic similarity in text

Is there a relatively simple way of telling if two pieces of text are semantically similar? Some assumptions that are valid: It is all english I have a list of all the important nouns Are there any ...
4
votes
1answer
80 views

Are there repositories of automatically generated (spam) webpages?

I'm interested to see if I can use machine learning/network analysis methods to automatically detect automatically generated (spam) webpages. I'm particularly interested in webpages that look ...
4
votes
1answer
415 views

How to compute the TF-IDF scores for a handful of documents, but without my own corpus?

I have a small number of documents (I could probably get 4 or 5 documents) and want to assign terms in these documents a score based on its importance to the document. I want to find which terms are ...
4
votes
0answers
20 views

How to represent sentences with their dependency parses as input to an RNN?

I am working on a task embedding sentences into a lower-dimensional space according to style, both grammatical and lexical. As such, I want to have as input the linear ordering of tokens in each ...
4
votes
0answers
50 views

Infer probabilities, for concatenation of words

Fix an alphabet $\Sigma$, and a set of words, $W = \{w_1,\dots,w_n\} \subseteq \Sigma^*$. I have a randomized model that works like this: Alice generates a random sequence of words, using some ...
4
votes
0answers
2k views

Next-Word Prediction, Language Models, N-grams

I was looking into how a next-word prediction engine like swift key or XT9 can be implemented. Here's what I did. I read about n-grams here - en.wikipedia.org/wiki/N-gram and aicat.inf.ed.ac.uk/...
3
votes
1answer
243 views

Semantic readings of the Lambek sequent calculus

I am reading Categorial Grammar: Logical Syntax, Semantics, and Processing by Glyn Morrill and I am stuck with the Fig. 3.9: Can someone explain this set of formulas and |.| function specifically? ...
3
votes
2answers
628 views

Examples for CFG that cannot be expressed by regular language

There are nice examples for context free grammars which cannot be expressed with regular language, for example the palindrome and a similar contrived example here, but they are very intuitively ...
3
votes
2answers
70 views

How do learn the most important nodes in a tree?

I have a list of 20000 words and how often they appeared in a set of 500 newspaper articles. I am trying to build a stemmer which chops off suffuxes from each words, so ...
3
votes
1answer
217 views

Specific case of a ranking model

So the problem I'm solving is this: I have a list of conversations of 3 messages each (for eg. "hi", " how are you", "remind me to fix this bug" is one conversation, and my problem will have many of ...
3
votes
1answer
139 views

Bottom up chart parser adding active arc step

I am following Bottom up chart parsing algorithm from Natural Language Understanding book by James Allen. It is I couldn't understand the 3rd step. I thought that when active arc is added the dot ...
3
votes
2answers
114 views

Measuring the information of a document?

I'd like to measure how much information a document $D$ contains. Clearly, the New York Times published yesterday contains more information than my diary wrote on the same day. But, I do not know ...
3
votes
1answer
2k views

Proving that English is not a regular language

I am wanting to try and prove that the English language is not regular. The alphabet is the set of all words in the English dictionary. Looking at sentences, I was able to use this pattern of ...
3
votes
1answer
175 views

Choice of machine learning algorithms frequency of parts of speech

I'm new to machine learning. I have text, and I tag the text according to their parts of speech tag ie walk is tagged as verb, etc. I tag entire sentences, and then convert them into a vector based on ...
3
votes
1answer
27 views

HMM tagger - Baum Welch training

I am trying to implement a trigram HMM tagger for a language that has over 1000 tags. In my training data I have 459 tags. Now if we consider that states of the HMM are all possible bigrams of tags, ...
3
votes
1answer
4k views

How to calculate an accurate estimated reading time of text?

I suppose the calculation should not be done by only two factors (average reading speed/words per minute, and word count). But at least by a third parameter, that in my opinion should measure the ...
3
votes
1answer
121 views

Natural language query processing

I am trying to implement a natural language query preprocessing module which would, given a query formulated in natural language, extract the keywords from that query and submit it to an IR (...
3
votes
1answer
75 views

Evaluation metric for an ordering algorithm

There is a sentence with N words. The words are randomly shuffled. I have a heuristic algorithm that tries to restore the original order. I want to evaluate my algorithm on a dataset of several ...
3
votes
0answers
43 views

Explain the process of formation of word senses in WordNet

Regarding the word sense disambiguation problem, read the following fact written on Knowledge-based Word Sense Disambiguation using Topic Models: Note that although WordNet is the most widely used ...
3
votes
0answers
32 views

How to compute the loss and backprop of word2vec skip-gram using hierarchical softmax?

So we are calculating the loss $$J(\theta) = -\frac{1}{T}\sum_{t=1}^T\sum_{-m \leq j \leq m} \log P(w_{t+j}|w_t;\theta)$$ and to do this we need to calculate $$P(o|c) = \frac{\exp(u_o^Tv_c)}{\sum \...
3
votes
0answers
120 views

Semantic parsing with Grammatical Framework - is this possible?

So far I have learned about categorial grammars, type logical grammars and formal semantics of natural language, the relevant tools are Cornell Semantic Parsing Framework https://github.com/clic-lab/...
3
votes
0answers
88 views

How to translate lambda calculus into (first-order, modal) logic, is it possible at all?

It is possible (using formal semantics) to translate natural language sentences into lambda expressions. So, is it possible to translate those lambda expressions into some logic, e.g. into first-order ...
3
votes
0answers
187 views

What is the state-of-the-art in machine translation on Chinese/CJK? [closed]

Sorry for my unfamiliarity with the field. Hopefully this question is on-topic here. Currently the machine translation from western European languages to English is arguably quite robust, with Google ...
3
votes
0answers
447 views

Is English Recursively enumerable? [closed]

The title says it all. I've tried digging up debate on this issue to see a proof one way or the other but it doesn't look like anyone is able to say whether or not it is. Clearly there are recursive ...
3
votes
0answers
74 views

What are some of the methods that NLP practitioners use to automatically learn linguistic features from text? [closed]

I am learning about NLP, with an eye to starting some practical NLP projects. I see that many of the algorithms for relation extraction and named entity recognition require you to identify linguistic ...
3
votes
0answers
76 views

Document clustering for summarization

I am curious as to what steps one would reasonably need to take to perform an extraction-based text summarizer. I've taken a look at some papers I've found on Google such as this one, which explains ...
3
votes
0answers
266 views

Has someone seen this structure before?

I am working 1 with a certain structure, and I wonder if someone has seen it before. I am no mathematician, so all I can say is that I will do my best to describe this structure. It is actually very ...
2
votes
2answers
3k views

Detect if a sentence is in passive voice

Given an English sentence, I am looking for a programmatic way to tell whether the sentence is written in passive voice. Currently, I just check if there is a was ...
2
votes
2answers
2k views

What are the definitions of syntax and semantics?

For a formal language $L \subseteq \Sigma^*$ over an alphabet $\Sigma$. From https://proofwiki.org/wiki/Definition:Syntax The syntax of a formal language is its structure, and is specified by a ...
2
votes
4answers
2k views

Optimal algorithm for finding all ngrams from a pre-defined set in a text

I'm thinking about the optimal algorithm for the following problem: Input data: a text, say it's an article about 5-50 pages. a set of ngrams (ngram strings, n>2), of arbitrary length, could be more ...
2
votes
3answers
642 views

Does programming language detection need more input than natural language detection?

I wonder which one of the two needs a larger input to achieve a decent accuracy: programming language detection or natural language detection? More details: Definition of Language detection: In ...