This week finds me at the Simons Institute for Theoretical Computer Science in Berkeley California. Simons started about the same time I joined the administrative ranks and never had the opportunity to spend a full semester there. I can manage a shorter trip and purposely chose a week with no workshops and great visitors including Sam Buss, Russell Impagliazzo, Valentine Kabanets, Toni Pitassi, Ryan Williams, former student Rahul Santhanam and former postdocs Pavan Aduri and Vinod Variyam and many others including the next generations of complexity theory leaders. Simons is having programs on Meta-Complexity and an "extended reunion" for Satisfiability. Apparently I used to work on Meta-Complexity before it was a thing.
Computational complexity traditionally has tried to get ahead of new technologies, and modelled randomized, parallel, quantum computation and cryptography in the infancy of their development allowing complexity to help guide our understanding and development of these areas. In the last twenty years or so, complexity has migrated more towards mathematics, and has mostly missed technological changes like cloud computing, hierarchical memory models, edge and mobile computing for example.
But the recent advances in optimization and machine learning cannot be ignored. There has certainly been plenty of discussion of ChatGPT and Russell gave an informal lecture yesterday trying to model large-language models at some level. I've been having some discussions about how complexity can answer questions like what it means for a model to be explainable.
Complexity theory also ought to reckon that practically we seem to be getting the best of P = NP while avoiding losing cryptography simultaneously in Heuristica and Cryptomania among Russell's five worlds. Russell claims we're not in Heuristica, at least not now, since we can still generate hard to solve problems. But if our models aren't modeling the world we live in, perhaps it's time to rethink the models.
Machine learning has been studied from a TCS point of view for decades now, so it's not like this area has been ignored altogether.
ReplyDeleteThe problem with "explainable" is that it can be something a little bit subjective. What is a an explanation? What is an acceptable language for giving explanations? First - order logic without any restrictions ? And what properties should satisfy a valid explanation ?
ReplyDeleteStriving for "explainable" is futile, understanding is a purely personal matter because the "Aha" moment is a quale akin to raw perception like a smell, joy or pain.
DeleteTo be "explainable", you'd have to have an internal representation of the thing to be explained, to be working from a _model_ of the thing being discussed. As every discussion of the LLM approach makes very clear, LLMs don't do that. So the idea that ChatGPT could be persuaded to produce explanations for what it said is, in principle, problematic. Or at least really hard.
ReplyDeleteFor your entertainment, here's ChatGPT falling on it's face doing music. (The vlogger's conclusion: my job's safe for the nonce.) It comes up with correct answers for simple things, but the chord prorgessions it spat out were pretty bad. (And the inanity of its comments got painfully blatant really quickly. At least in music, this technology ain't ready for release. Not.even.close.)
(Interestingly, when asked to produce a list of tunes with a particular property (being in 5/4 time), it comes up with a few correct answers, but blithely adds wrong answers into the list. Still a few bugs in the system, it seems.)
It may be that there is a lot of material on the internet about music that's flaky. Music theory is actually quite hard, but everyone likes to talk about music.
https://www.youtube.com/watch?v=PlVX3hzp2qM&ab_channel=DavidBennettPiano%27s2ndChannel
Many humans I interact with also seem to be working without internal models.
DeleteDavid Marcus' comment makes no sense without the deleted comment it is replying to...
ReplyDeleteI get why you deleted it: you thought it was just rude. But it was technically accurate: ChatGPT is a statistical token sequence generator, and as such, has no internal models of anything.
There is, I suppose, an argument that if something appears to be doing amazing smart things much of the time, then the errors are just noise and can be ignored. I think that that's the wrong way to look at programs: a program's operation is best discovered by finding where it messes up.
People are different. Sure, people mess up all the time, e.g. fail to figure out some important point in a class and struggle hopelessly for the rest of the term. But people (some of the time!) really do work from very powerful internal models and correct those models when problems arise. And do logical reasoning from those models. (See Fodor's "In Crirical Condition" and other works for someone who thinks human reasoning is essentially perfect, taking everything possible into account. Overmuch, I submit, but worth a read.)
The claim of the LLM technology is that it produces text that is, for all functional purposes, the result of correct logical inferencing from good internal models without doing the work of (a) figuring out how to do that modelling and inferencing and (b) actually doing that modelling and inferencing.
I personally don't like this approach. But that's opinion. The facts on the ground are that LLM's don't actually do logical inferencing. And thus the problem of "explaining" their output is really hard, since, there's nothing there to explain.
Sorry, looks like I marked your earlier comment as spam by mistake, or blogger automatically did. It's been reposted.
DeleteThanks. Sorry for being grumpy.
DeleteHere is a post where the author used ChatGPT4 to help him write code:
Deletehttps://statmodeling.stat.columbia.edu/2023/04/18/chatgpt4-writes-stan-code-so-i-dont-have-to/
In this comment
https://statmodeling.stat.columbia.edu/2023/04/18/chatgpt4-writes-stan-code-so-i-dont-have-to/#comment-2204104
the author wrote, 'Indeed, it does generate lots of buggy code. But so do I! For me, and I think for a lot of people, “programming” is mostly debugging mixed with some refactoring, just as writing is mostly rewriting.'
That isn't how I write code. I write code the way I write math.
Maybe many people are more like ChatGPT4 than they are like me.
Trying asking GPT4 (which is the most powerful model publicly available) to add two 20 digit numbers.
ReplyDeleteThe current large models are good for some vaguely defined tasks that humans learn to perform well and traditional algorithms are not good at, but the samples for these tasks are coming from particular very biased distributions that are not modeled in a mathematical way, like the literature in English. The question is how we can make meaningful statements when the model does not work really on any of distributions that classical complexity theory have cared about, like those we care about in cryptography, but from these anthropological distributions.
What is needed is to understand these models is not to claim that they are solving hard classical problems but solving particular distributions that humans care about on tasks that humans care about and both are very hard to characterize mathematically.
The ridiculous predicament humans find themselves in...
DeleteHumans who are a mere spec of organic matter on a speck of dust in an unimaginably vast cosmos of nothingness (see the Voyager 'sun beam' photo to grasp the utter insignificance of earth, let alone all of life on earth).
Humans themselves will never ever get to anything beyond the outer planets, the physics of this is simply insurmountable. We can stare at far away stuff with advanced telescopes but there is no hope of actually knowing what's going on even in our neighboring star systems in fine-grained detail.
On this spec of dust, we arrogantly luxuriate harnessing what we thought were inexhaustible stores of energy sequestered by living organisms over hundreds of millions of years without even realizing how this gift was endowed to us.
And we, this spec of inconsequential organic matter on a spec of dust, have come to the preposterously ridiculous conclusion that inventing a statistical representation of internet information is somehow comparable to intelligent life.
Not so fast dear humans, we have no idea how the quadrillions upon quadrillions of intelligent life that has existed and continues to exist on this spec of dust works.
As the old story goes "the emperor has no clothes".
Yes, you can use other algorithms to solve problems. This just shows the model itself is not really solving the hard problems in computational complexity.
DeleteIt is capable of solving a set of problems that are essentially disjoint from what computational complexity theory has historically cared about.
I don't want to say we cannot say anything in the classical computation complexity theory about these ML models, but my gut feeling says that until we define a new computational framework that incorporates the particular anthropologic distributions and anthropologic computational problems the results will not be very interesting.
At the minimum, we need to capture some mathematical properties of these anthropologic distributions. ML is neither good at worst case complexity nor at average case where the distributions are mathematically nice. There are cases (e.g. in cryptography) that we do not care about anthropologic distributions; and ML models so far don't show any sign of being able to deal with these cases.
There is a lot of hyper-hype currently about large language models. The language and vision have turned out to be simpler in ways than factoring natural numbers which is absolutely not surprising considering that humans and other animals have been solving these problems for a very long time. Are we in computational complexity theory really surprised that we have been able to build ML models that do tasks similar to what humans have been doing? These problems were obviously computationally extremely feasible problems, and not NP-hard problems at all (and the NP-hard variant of these problems ML has made absolutely zero progress on).
It is legit to ask about LLMs but some of Lance's claims about "missing" things like cloud computing, edge, mobile computing etc seem a bit off base. To the extent that there have been interesting questions wrt these models they have generally been asked (e.g. in cloud computing) and some have been answered. (BTW: Lance: I think you meant "ought" not "out".)
ReplyDeleteOn LLMs: While people can add or multiply big numbers, they would rather use a calculator or Excel or a package like Wolfram Alpha. What tools are reasonable to allow GPT4 to use? GPT4 apparently is terrible at Sudoku, because of the lack of backtracking. Native SAT solving is also surely bad also. If GPT4 could do the triage to find out what tools might be used and try to apply them, would that be so different from how humans work?
Fixed the typo. It's not that we've completely missed areas like cloud and edge computing but they certainly haven't played the role in complexity as say random and quantum.
Delete