4
$\begingroup$

After reading this blog about Deep Neural Networks learning about selfies I'm struck by how generic the network in question is.

In short: I'm thinking of trying to write something vaguely similar for solving cryptic crosswords, but I can't fathom how to make the general algorithms it uses generic enough that it can develop them ?

A contextual example from the blog is how the network 'understands' filters? Would I need to teach the network about tokenizing the input around keywords, or is that something the network has to 'figure out'? How do I 'seed' the operations the network can perform?

$\endgroup$
  • $\begingroup$ have not heard NNs used for crosswords. but watson used for jeopardy (not NN technology) seems close to solving crosswords. you need a large training corpus. aka "big data". $\endgroup$ – vzn Oct 28 '15 at 22:50
  • $\begingroup$ @vzn, agreed. But you can't just throw bigdata at something that doesn't know how to handle the data. $\endgroup$ – Pureferret Oct 28 '15 at 23:02
  • 1
    $\begingroup$ you really seem to be marvelling at NN technology wrt "deep nets" (which is indeed marvelous) but it is just one AI approach. the bigger question here seems to be how to apply AI/machine learning to crossword puzzles. would you object to cases that do so but dont use NNs? as for "filters" you dont define this at all, what are you talking about? $\endgroup$ – vzn Oct 29 '15 at 0:39
  • $\begingroup$ @vzn yes, I would prefer a NN answer. $\endgroup$ – Pureferret Oct 29 '15 at 0:57
  • $\begingroup$ If you're interested in solving crossword puzzles, don't underestimate just how powerful regular expressions are. $\endgroup$ – jmite Oct 29 '15 at 2:26
3
$\begingroup$

Neural nets don't "understand", they are trained. Despite the fancy term, a neural net is simple a regression model on steroid - often high-dimensional. It's a bunch of weights (vectors) connected in a graph, with an input side and some updating rule (for example, gradient descent).

You'll need a lot of labeled data for the training set. The neural net is trained by feeding these input and telling it about the supposed output, and it readjusts its weights in the regression model.

Apart from that it's a blackbox - kinda magical. But you can't use a neural net trained to recognize selfies to do cryptography (or anything else).

$\endgroup$
  • 2
    $\begingroup$ If you try to define "understand", you end up in deep philosophy territory -- best avoid such words in CS if you ask me. $\endgroup$ – adrianN Oct 29 '15 at 14:13
2
$\begingroup$

there is some deep academic research on AI/Machine Learning applied crossword solvers, eg contained in the following paper. the basic effective systems utilize large databases of clue-answer pairs combined with dictionaries. an IR "Information Retrieval" system is built to take a given crossword clue and generate "candidate answers". these are further processed eg with part of speech analyzers to generate different "near" answers and constraint solvers guarantee words fit the current constraints eg other letters already known. the systems somewhat use "trial-and-error" just like humans. it is known/ observed that a lot of crossword puzzles reuse clues in minor variations so these systems have some degree of success just "working from memory" and not necessarily utilizing complex rules.

Automatic resolution of Crossword Puzzles (CPs) heavily depends on the quality of the answer candidate lists produced by a retrieval system for each clue of the puzzle grid. Previous work has shown that such lists can be generated using Information Retrieval (IR) search algorithms applied to the databases containing previously solved CPs and reranked with tree kernels (TKs) applied to a syntactic tree representation of the clues. In this paper, we create a labelled dataset of 2 million clues on which we apply an innovative Distributional Neural Network (DNN) for reranking clue pairs. Our DNN is computationally efficient and can thus take advantage of such large datasets showing a large improvement over the TK approach, when the latter uses small training data. In contrast, when data is scarce, TKs outperform DNNs.

you use the word "understand" in your question. that is a more general question in AI about whether systems that succeed at given AI tasks have demonstrated "understanding". it generally verges on philosophy and there is a sizeable "parallel" philosophical debate about how closely AI is to "real intelligence". much of this started with Turings test in the early 1950s. CS researchers generally take a pragmatic/ empirical, behaviorist stance on this. one can measure human performance on objective tests, and machine performance, and just compare numbers and avoid the far deeper questions (for now) of what constitutes "understanding".

another recent successful system that uses AI but not NNs and is very similar to the crossword "clue/answer" dynamic is Watson built by IBM for the jeopardy game, and decisively beat the best human player(s) at the time. it uses technology called DeepQA which is basically/ roughly an IR and post-processing system, in the vein of expert systems.

$\endgroup$
  • 1
    $\begingroup$ That's excellent. I think what I wanted to know is how to frame an Information Retrieval system in a generic way. I presume this is the analogy to the ConvNet's fillers. Is there a general term for these I can edit into my question. $\endgroup$ – Pureferret Oct 29 '15 at 18:12
  • 1
    $\begingroup$ oh! relooked at the article and found all the references to filters. these generally correspond to a crosscutting concept in vision and biological systems called feature detectors. the concept is not as widely used outside vision research but it appears to be a general concept across different "sensory modalities" in this case incl speech/ language. NN "filters" would tend to recognize the same "features" that humans do ie unimportant vs important words, parts of speech, subject vs object of sentence, etc... $\endgroup$ – vzn Oct 29 '15 at 18:27
1
$\begingroup$

I'm struck by how generic the network in question is.

That's exactly the point of a convolutional neural network: it is intended as a general architecture for solving machine learning problems in computer vision, so you don't have to craft a customized architecture for each new computer vision problem you run across.

However, convolutional neural networks are focused on computer vision kinds of problems. The "convolutional" part makes sense in that domain, where we expect that there is some kind of "spatial symmetry" in images (a banana in the upper-left corner of an image looks the same as a banana in the lower-right corner, and the two should often be treated similarly). The same is probably not going to be useful in other domains, such as solving crossword puzzles.

Therefore, I would not recommend a convolutional neural network for your application. Instead of looking to computer vision and trying to crib off what they are doing, I suggest you spend some more time learning about the fundamentals of machine learning and deep learning; that will probably help you more.

For crossword puzzles, you will probably achieve much more success by building a customized algorithm that is designed specifically for that particular problem, rather than by trying to use some machine learning algorithm. Deep learning is not "fairy dust" that can magically solve every problem in computer science. They are good for very specific tasks (supervised classification, where you have a huge training set), but not everything; solving cryptic crosswords does not sound like one of the things I'd expect deep neural networks to be especially useful for.

$\endgroup$
  • $\begingroup$ re "fairy dust" (lol), deep NNs outperform many other approaches however some of this is due to effectively utilizing "big data"; it may be one of the 1st approaches to do so, but other approaches may be starting to conquer as well. also not all deep NNs are convolutional but convolutional ones are proving to be surprisingly effective/ successful. also, ANNs can be regarded as a general information processing system that is highly adaptable to many domains, and merely because a domain has not seen it applied does not mean it wont work. it is still "early days" for deep NN research. $\endgroup$ – vzn Oct 30 '15 at 1:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.