Connectionists: Brain-like computing fanfare and big data fanfare

[Marcello Pelillo]

On Thu, 30 Jan 2014, Ivan Raikov wrote:

> Well, I think it is not so clear that we will be swallowed up by statistical methods, because exact Bayesian inference is NP-hard.
> I think you will have a really hard time arguing that the brain solves NP-hard problems.
> In fact, I think a central question is how the heck does the brain *avoid* having to solve NP-hard problems :-)
> Of course, there are many kinds of inexact inference algorithms based on random sampling, which have polynomial time complexity,
> but they usually have problems with optimality. So I think statistics is just one more tool for those cases when there  is no data.
>


In using the argument from NP-hardness we should keep in mind that classical complexity theory deals with the worst-case scenario.
In practice, however, one is interested in typical-case behavior, which is of course much more difficult to characterize.

A while ago, Monasson et al. published a Nature paper precisely on this issue, and showed that intractable problems such as K-SAT exhibit phase 
transition phenomena.

R. Monasson, R. Zecchina, S. Kirkpatrick, B. Selman, and L. Troyansky, Determining Computational Complexity from Characteristic Phase 
Transitions, Nature 400, 133 (1999).

In 1999 we also run a NIPS workshop on this topic: http://www.dsi.unive.it/~nips99/

I think there were follow-ups to these studies but I'm not sure how far they have gone, though...

Marcello

---
Marcello Pelillo, FIEEE, FIAPR
Professor of Computer Science
Computer Vision and Pattern Recognition Lab, Director
Center for Knowledge, Interaction and Intelligent Systems (KIIS), Director

DAIS
Ca' Foscari University, Venice
Via Torino 155, 30172 Venezia Mestre, Italy
Tel: (39) 041 2348.440
Fax: (39) 041 2348.419
E-mail: marcello.pelillo at gmail.com
URL: http://www.dsi.unive.it/~pelillo


>    Ivan
> 
> 
>