Parsing city of origin and destination city from a string

After reading Steven Pinker's book The Stuff of Thought in which he describes verbs as the chassis of a sentence, I thought we would see various Natural Language Understanding algorithms that leveraged "verb classes". Beth Levin published a book called Verb Classes and Alternations which is effectively a database/index of a subset of verbs. Each verb takes one or two arguments and the arguments can appear on the LHS, RHS, or both (i.e. alternations). You can get a feel for them from a 2011 paper by Levin [1].

Normally you would start with a Parts of Speech algorithm but with the limited context of flights (international only?) you could focus only on a "to" clause and a "from" clause with the city/country found in the RHS of each clause.

Resolving ambiguous cities could start with a simple ranking algorithm based on a list of International/Domestic destinations and their corresponding traffic level.

NLU is hard but constrained domains like this are tractable, in my overly optimistic opinion.

[1] https://web.stanford.edu/~bclevin/mpeva11vclass.pdf

If only someone made a version of this answer that was more, let’s say, board-room accessible. So much conflict could be avoided, if engineers were not seen as ”non-believing naysayers” when top brass wants some of that hot new AI

If this was not frowned upon on StackOverflow, the correct answer would recommend a commercial API.

That said, if I were to implement this from scratch, I would not start with a positive list of cities. Rather, I would implement a couple of patterns like: "from X to Y", "X to Y", ""to Y from X".

But invariably there are going to be ambiguities. How do you deal with a city called "from to" :-D? How to you parse "from from to to to from"? I'd probably tokenize it using place lists, like

    "from (from to) to (to from)"
    "from (from to) (to to) from"
    "from from (to to) to from"
    ...

and then, maybe assigning probabilities to each parsing, decide that the first one is most likely.

A side comment, for someone like me who isn't an NLP expert, it seems strange that there are no libraries that let me parse a string accoring to some rules in all possible ways (like a tree) and pick the one that is most probable. I'm sure this exists, but it is hard to search for...

Rather than as a general parsing problem, isn't it possible to reformulate this in a different way that is much easier to solve by using the fact that these are strings describing flights we want to get destination and sources from?

So what you could do is take a general database of all flights (which is structured data and easy to work with) and then the problem is to label the unstructured input data with the probability it relates to a particular source, destination pair.

For example, there are no flights from York (lovely though York is) to Venice, so that mistake isn't one such a model could even make. Whereas there are a lot of flights to and from New York (including to Venice), and since that number is large it's a much higher probability labeling than some others.

If you have the money, give it to mechanical turk. If you have interesting content, use it as a captcha.

This is a bog standard modern NLP problem, I love how all the comments here are on how impossible it is using traditional heuristics and quoting various pop neuroscience authors and anecdotes. You only need a sufficiently large language model (and fine-tuned on short location strings) and run Named Entity Recognition on the input. Tricky? Yes. But there is only a finite number of prefix names in the English language and should automated solutions fail, you can always fallback to using a natural language form. A large neural network based solution running in the cloud would be able to get to 95+% accuracy. It would not be perfect but is good enough for most use cases.

Although the SO question is focused on the goal, this broad kind of task is quite a common requirement for chatbots, so looking at tools like RASA and Spacy for this are good places to explore (for those not opting for the commercial API approach others sensibly suggested)

https://rasa.com/docs/rasa/nlu/entity-extraction/

Spacy have a handy demo of NER (although it appears down for me right now): https://explosion.ai/demos/displacy-ent/

In a former life I was tasked with exploring the complexity of extracting discrete information from resumes. Any format of resume. "100% complex", was my finding. It is amazing how much processing the human mind can do naturally.

The answer to this is the main attraction, a great overview of the process of a data project.

And when you've dealt with the problems of the text extraction like in the long answer, you're left with the next huge problem: Context and inferring intent.

In the example, the poster shows inferring full location, not just the name in the example output.

Some examples where that gets tricky:

If I want driving instructions "from London to Hamilton" odds are I want London, Ontario to Hamilton, Ontario.

But what about "from London to York"? Without knowing more, I can't tell if that is in England or Ontario, and "knowing more" here involves a lot of guesses about in what context someone would qualify a name based on where they live relative to different locations with those names.

If I want "London to Paris" I could mean London, Ontario to Paris, Arkansas, but odds are very much I don't, because it seems unlikely someone far from either place would leave it unqualified. If that someone is close to either Ontario or Arkansas, it's tempting to think they'd still refer to the bigger place... But I see enough Candians on e.g. London Craigslist assuming it's for London, Ontario that this seems to depend on additional context.

But here be dragons. Qualified names are often still tricky to interpret unambiguously. Let's say I've against all odds been to Paris, Wisconsin once, and I want to go back there. Chances are I might write "to Paris, Wisconsin" or similar... But which one? Paris, Grant County, or Paris, Kenosha County"? Or I might even write "to Paris, USA" if I wasn't painfully aware there's at least a dozen Paris-es in the US.

And what about when I mess them up? When I started writing the paragraph above, I first mis-remembered and wrote Paris, Wyoming.. Joy...

From experience, you can get decent results on average with a dataset with size and population and assume that the bigger or more populated a place is, the larger is the region where it is likely to be the best choice, however. But there will be many that remains ambiguous.

But when you look at names that are very common and where many alternatives exist that are of a wide range of sizes, spread all over the place, that too becomes difficult. Examples: "from Santa Cruz to San Jose". California, right, because you have both names in the same state? Except that also applies to Arizona. Or New Mexico. To know whether people there would be likely to talk about them without specifying more detail, you need additional knowledge for each of these locations, and e.g. try to guess when some of the locations are too small for even relative "locals" to ignore them. And those are just the examples in the US that have both names in the same state, but there are dozens of both names across the Americas and further afield.

(As you might tell, I've spent too much time having to deal with location data...)

Can get quite far using a CRF solution. But nothing is close to perfect here.

While I enjoyed the long answer by alvas (well, they're suggesting you can only hit 100% accuracy with a rulebase; a man or woman after my own heart) I think the real problem the user asking the question, Merv Merzoug has, is not as complicated as it's made to be. Specifically, the user wants to parse successfully only a particular kind of English sentence - not arbitrary natural English sentences. What's more, those are sentences that are found in a particular, restricted context, that of strings that record travel details (most likely for some kind of travel agency and the like).

Given that those strings are going to be on the short side (you don't need to anticipate someone writing an epic saga in dactylic verse to describe a flight) the whole set of such sentences is probably finite and relatively small and can be represented by an equally finite and much smaller set of rules. So while alvas' comment is spot on regarding the amount of work one needs to do to cover all the exceptions and edge cases that might crop up even in such a small subset of natural English, it is not a problem so big as to be impossible to solve with some elbow grease.

There is much precedent of solving much more complex problems with hand-crafted grammar rules. For a very recent example, the latest online version of Magic the Gathering, M:tG Arena, apparently uses a hand-crafted context-free grammar to represent the language used on Magic cards [1]. The grammar is used in a parser that executes cards as scripts in a scripting language. Creating a grammar for the entire M:tG language is a job that a dedicated programming team can accomplish in a reasonable amount of time but even representing a small but substantial subset of that language is a goal that is in the range of, er, let's say ah a degree student of Computer Science in her final year :)

_______________________

[1] Just let me find that link. I got it around here somewhere...

Yep, here we go:

Magic Arena's GRE: The Groundwork for future digital products, in Chris Clay's Interview

To dispel any misconceptions: the GRP is not a machine learning approach to Natural Language Processing. It's more of a compiler/parser that uses rules and logic we've crafted. We have a dictionary that defines the parts of speech and some semantic data for "Magic Words". We also have a huge list of syntax rules for "Magic Sentences", similar to a Context Free Grammar. With this, and our good friend the Natural Language Toolkit, we generate a parse tree for ability text. The tree groups individual words into phrases, multiple phrases into sentences, and all the sentences under the ability as a whole. We then process that representation of an ability into higher-level ideas, specific to Magic. “Draw a card” is no longer just a verb and an object, but is an action and entity with regards to game play. We take verb 'atoms' (destroy, discard, exile) and use them to construct molecules ("triggered ability", "sequence of effects", "replacement effect"). With that semantic representation of the ability, we can then basically compile it into code. That code is then added to the GRE,and executes when you play Arena!

https://www.reddit.com/r/magicTCG/comments/74hw1z/magic_aren...