trentmkelly/LessWrong-43k huggingface dataset:
Additional space complexity isn't always a useful metric 
by Brendan Long — 2023-01-04T21:53:05.049Z
Link: https://www.brendanlong.com/additional-space-complexity-isnt-always-a-useful-metric.html

I've been subscribed to Interview Cake for years, and today they had a really interesting question: Given a list of n + 1 integers in the range 1...n, find one of the duplicates (there is guaranteed to be at least one) in O(n) time and O(1) additional space. The answer is really interesting[1], and I recommend trying it, but I don't think it makes sense to care about additional space rather than total space, and I still think using a set to keep track of numbers (the most obvious solution) is the best solution in practice.

The reason I thought this was worth writing about is that the "O(1)" linked list algorithm can't be streamed, so it doesn't make any sense to treat the memory the input uses and the additional memory as fundamentally different (they both need to be allocated on the same machine). Since the algorithm requires that you hold the input in memory, the only sane way to treat the space complexity to consider the total, i.e. the linked list solution is O(n) for the input + O(1) for the rest of the algorithm, which is still O(n).

In this specific case, the constant factors are also huge. The numbers are guaranteed to be densely packed and in the range 1...n, so our set can be a bit array of length n (i.e. to mark "2" as being in our set, we set bit 2 of our array). This means that our additional space is actually going to be smaller than our input by a factor of the size of our integer type (i.e. with 32-bit integers, the input will be 32x larger than our bit array). With any reasonable integer size, the size of the input is going to be massively larger than the additional memory for our set.

In a previous post on a similar question, I pointed out that a hash table with a million 32-bit entries will only use 8 MB of memory, but this case is even better. If you want to find the duplicate in a list of a million 32-bit integers, your list will take 4 MB of memory but the set of numbers you've seen will only take 125 KB of memory.

Finally, remember how I said that the linked list solution can't be streamed? Well, the set solution can, so taking that and the bit array optimization into account, the set solution can use substantially less memory in-practice because it only has to store the extremely-efficient bit set and doesn't have to hold the entire input in memory!

For reference, here's a Python solution that uses substantially less memory than the link...
List of links for getting into AI safety
by zef — 2023-01-04T19:45:09.663Z

This is a quick list I made when I was looking into material on getting into safety research. It's not thorough and/or carefully arranged, I had just put it together for myself and think it can be useful to people, although there are many ways it could be improved, which I sadly don't have time for. Hope this is helpful!

Doing research in AI safety

How to pursue a career in technical AI alignment

FAQ Career Advice for Alignment researchers

AI safety starter pack - EA Forum

Beneficial AI Research Career Advice

Advice on Pursuing Technical AI Safety Research

AI safety technical courses, reading lists, and curriculums

AI alignment resources | Victoria Krakovna

AI Safety Support - Lots of Links

awesome-ai-alignment: A curated list of awesome resources for getting-started-with and staying-in-touch-with Artificial Intelligence Alignment research.

How To Get Into Independent Research On Alignment/Agency

General research in AI tips

How I became a machine learning practitioner

How to Read Research Papers

Want To Be An Expert? Build Deep Models

Lessons Learned Reproducing a Deep Reinforcement Learning Paper

An Opinionated Guide to ML Research

A Survival Guide to a PhD

Machine Learning PhD Applications — Everything You Need to Know — Tim Dettmers

Film Study for Research - Jacob Steinhardt

How to PhD

How to succeed as an early-stage researcher: the “lean startup” approach

Research Taste Exercises

A Recipe for Training Neural Networks

Technical Safety content

Concrete Problems in AI Safety

Neel Nanda's posts on Mechanistic Interpretability

Without specific countermeasures, the easiest path to transformative AI likely leads to AI takeover

My Overview of the AI Alignment Landscape: Full Sequence - Neel Nanda

Reading List: Evan Hubinger's AI Safety Worldview

What are the coolest topics in AI safety, to a hopelessly pure mathematician? - EA Forum

Risks from Learned Optimization - AI Alignment Forum

Testing The Natural Abstraction Hypothesis: Project Intro - AI Alignment Forum

Alignment research exercises - AI Alignment Forum

Intro to ML Safety

The Library - AI Alignment Forum

Recommended Materials – Center for Human-Compatible Artificial Intelligence

AGI Safety: Safety and Control Considerations for Artificial General Intelligence

TAI Safety Bibliography

Study Guide - John Wentworth

Looking back on my alignment PhD
Opening Facebook Links Externally
by jefftk — 2023-01-04T19:00:02.305Z

When I'm on my phone and click a link in Facebook I want it to open in
my normal browser, but it defaults to an "in-app" browser. I
really don't like in-app browsers, and I think

Alex
Russell's explanation of their problems is very good. I've turned
this behavior off, but Facebook regularly forgets my decision, most
recently a few weeks ago. The setting had moved since

the
last time I did this, so here are screenshots showing how to turn
it off on Android:

Click on the icon of your profile image overlaid with a hamburger menu
in the upper right, and scroll to the bottom:

Click "Settings & privacy":

Click "Settings":

Click "Profile settings":

Click "Media and contacts" settings:

Toggle "Links open externally":
Conversational canyons
by Henrik Karlsson — 2023-01-04T18:55:04.386Z
Link: https://escapingflatland.substack.com/p/conversation

Conversations are streams: they pass by without leaving much behind. But if you add a notebook—if you write down short summaries of what you talk about so you can return to it in later conversations and expand—then you have a landscape for the conversation to flow through, and this changes it in interesting ways.

When I started writing summaries, I thought it would be a small change. I already kept a detailed journal—I could just as well keep one for conversations, too. I could jot down a few notes about the key ideas, turning a two-hour conversation into 400 words or so. After a few months, however, it became clear that these notes were in fact not a small change. The notebook had entirely altered the shape of my conversations.

Because I had the notes, I would review them if I was to speak with the same person again, adding comments about thoughts I’d had in the interim, rank ordering which topics I wanted to revisit, and so on. This way good ideas and topics would not be dropped but revisited and expanded. They would be connected to new insights, merged, and refined. Through this, the conversations became richer. They became more useful and interesting.

The conversational stream was flowing through a landscape. On its banks ideas would wash up. Gradually, the banks would move, too—the landscape is shaped by the flow of words into a canyon. A canyon that shapes the stream of words in turn.

I don’t write down the conversations I have with most people. But there are a few who I keep coming back to—friends with minds that are forever churning, minds like mysterious machines I can never fully grasp but am continually delighted by. When we talk they all take me to different places; when I add a notebook they all go deep.

The first conversation I wrote down was with Torbjörn, a software engineer who has an uncanny ability to guess my thoughts. When he gets excited he SPEAKS IN ALL CAPS, and he gets excited about everything.

At the time, we talked on the phone once a week for about two hours. I would set off from my house toward the ocean and cross into the nature reserve. Walking along the ravine and the cliffs for a few hours, I would talk to Torbjörn about open research questions and software projects we were involved with. He would ask me for strategic advice about his consultancy. We also talked about our relationships, aliens, the ravings o...
Progress links and tweets, 2023-01-04
by jasoncrawford — 2023-01-04T18:23:03.959Z
Link: https://rootsofprogress.org/links-and-tweets-2023-01-04

Progress Forum

Building Fast and Slow Part III: Design of the World Trade Center (Brian Potter)
Why pessimism sounds smart (a oldie by yours truly)

Announcements

Foresight Institute has a spot for a J1 visa in San Francisco in 2023 (@allisondman)

Tweets

One container ship carries more than the whole English fleet did 440 years ago. Also: “What, load boxes ashore and then load the boxes on the ship?”
“A fully general argument against ever doing anything that changes anything, ever”
Sometimes giving someone a book changes the course of their life

Retweets

“We already have the tools to preserve brains fantastically well”
So many of the world’s great infrastructure projects would be impossible today
The 1930 campaign to stop people from listening to recorded music
Who are some good, interesting, up-and-coming, not-yet-famous essayists/bloggers?
ChatGPT can correct OCR errors in historical texts
California court rules that economic growth as such is an environmental harm (!)
A rapid combo test for covid, flu and RSV. Unfortunately illegal in the US
200 COP in MI: Analysing Training Dynamics
by Neel Nanda — 2023-01-04T16:08:58.089Z

This is the sixth post in a sequence called 200 Concrete Open Problems in Mechanistic Interpretability. Start here, then read in any order. If you want to learn the basics before you think about open problems, check out my post on getting started. Look up jargon in

my Mechanistic Interpretability Explainer

Disclaimer: Mechanistic Interpretability is a small and young field, and I was involved with much of the research and resources linked here. Please take this sequence as a bunch of my personal takes, and try to seek out other researcher’s opinions too!

Motivating papers:

A Mechanistic Interpretability Analysis of Grokking

,

In-Context Learning and Induction Heads

Background

Skip to motivation if you’re familiar with the grokking modular addition and induction heads papers

Several mechanistic interpretability papers have helped find surprising and interesting things about the training dynamics of networks - understanding what is actually going on in a model during training. There’s a lot of things I’m confused about here! How do models change over training? Why do they generalise at all (and how do they generalise)? How much of their path to the eventual solution is consistent across runs and directed vs a random walk? How and when do the different circuits in the model develop, and how do these influence the development of subsequent circuits?

The questions here are of broad interest to anyone who wants to understand what the hell is going on inside neural networks, and there are angles of attack on this that are nothing to do with Mechanistic Interpretability. But I think that MI is a particularly promising approach. If you buy the fundamental claim that the building blocks of neural networks are interpretable circuits that work together to complete a task, then studying these building blocks seems like a grounded and principled approach. Neural networks are extremely complicated and confusing and it’s very easy to mislead yourself. Having a good starting point of a network you actually understand makes it far easier to make real progress.

I am particularly interested in understanding phase transitions (aka emergent phenomena), where a specific capability suddenly emerges in models at a specific point in training. Two MI papers that get significant traction here are

A Mechanistic In

...
What's up with  ChatGPT and the Turing Test?
by JoshuaFox — 2023-01-04T15:37:15.865Z

ChatGPT looks like it would pass the Turing Test, the gold standard of benchmarks measuring whether an AI has reached human-level intelligence. Yet Googling around, it doesn't seem that anyone has put on a full Turing Test.

Please comment with your thoughts on whether or how such a test can be put on.

It doesn't seem difficult. The Loebner Prize has measured progress towards the Turing Test since 1990. All you need is a human judge and test subject, and ChatGPT.

The Turing Test is not perfect. It is a sufficient but not necessary test of human-level intelligence: An AI that can pass it can cover any area of human intelligence transmissible in text chat, at a level such that human-level intelligence (the judges) cannot tell the difference.

But it has long been recognized that an AI which is generally human-level or beyond could still fail the Turing Test. If it had personality quirks, yet otherwise managed to cover almost all areas of achievement -- think of neuroatypicality taken a few steps further -- we would call it generally intelligent. If it communicated only in telegraphic staccato yet was vastly more able than humans to earn billions of dollars a day, to create art admired by humans who don't know who created it, correctly interpret human feeling, we would still consider it intelligent. If it used nothing but nanonengineering to convert the Earth to computer chips within minutes, so it could better achieve its goal of calculating digits of π, we might not want to call it intelligence, but then again, we'd be dead.

Also, because humans are the judges, an AI that can fool the judges with psychological tricks could pass: Even the Eliza of the sixties could do that to some extent.

Still, the Turing Test is a milestone. Ray Kurzweil has long said, repeating it recently, that we can expect an AI to pass in 2029.

One reason we can't do a Turing Test is that ChatGPT is programmed specifically not to pass: It readily states that it is a language model. This quirk could be bypassed, either by prompt engineering or by manually editing out such claims. But the avoidance of simulation might be too deep for that. ChatGPT is also much faster than human, but that could be handled with an artificial delay.

We could try alternative tests for human-like intelligence:

Reverse Turing Test: The human test subject tries to match ChatGPT. Just as a Turing Test determines wheth

...
2022 was the year AGI arrived (Just don't call it that)
by Logan Zoellner — 2023-01-04T15:19:55.009Z

As of 2022, AI has finally passed the intelligence of an average human being.

For example on the SAT it scores in the 52nd percentile

On an IQ test, it scores slightly below average

How about computer programming?

But self-driving cars are always 5-years-away, right?

C'mon, there's got to be something humans are better at.

How about drawing?

Composing music?

Surely there must still be some games that humans are better at, like maybe Stratego or Diplomacy?

Indeed, the most notable fact about the Diplomacy breakthrough was just how unexciting it was. No new groundbreaking techniques, no largest AI model ever trained. Just the obvious methods applied in the obvious way. And it worked.

Hypothesis

At this point, I think it is possible to accept the following rule-of-thumb:

For any task that one of the large AI labs (DeepMind, OpenAI, Meta) is willing to invest sufficient resources in they can obtain average level human performance using current AI techniques.

Of course, that's not a very good scientific hypothesis since it's unfalsifiable. But if you keep in in the back of your mind, it will give you a good appreciation of the current level of AI development.

But.. what about the Turing Test?

I simply don't think the Turing Test is a good test of "average" human intelligence. Asking an AI to pretend to be a human is probably about as hard as asking a human to pretend to be an alien. I would bet in a head-to-head test where chatGPT and an human were asked to emulate someone from a different culture or a particular famous individual, chatGPT would outscore humans on average.

The "G" in AGI stands for "General", those are all specific use-cases!

It's true that the current focus of AI labs is on specific use-cases. Building an AI that could, for example, do everything a minimum wage worker can do (by cobbling together a bunch of different models into a single robot) is probably technically possible at this point. But it's not the focus of AI labs currently because:

Building a superhuman AI focused on a specific task is more economically valuable than building a much more expensive AI that is bad at a large number of things.
Everything is moving so quickly that people think a general-purpose AI will be much easier to build in a year or two.

So what happens next?

I don't know. You don't know. None of us know.

Roughly speaking, ther...
From Simon’s ant to machine learning, a parable
by Bill Benzon — 2023-01-04T14:37:56.679Z

Simon’s ant is a well-known thought experiment from Chapter 3, “The Psychology of Thinking: Embedding Artifice in Nature,” in Herbert A. Simon (1981), The Sciences of the Artificial. It’s a parable about computation, about how computational requirements depend on the problem to be solved. Stated that way, it is an obvious truism. But Simon’s thought experiment invites you to consider this truism where the “problem to be solved” is an environment external to the computer – it is thus reminiscent of Braitenberg’s primitive vehicles (which I discussed in this post).

Think of it like this: the nervous system requires environmental support if it is to maintain its physical stability and operational coherence. Note that Simon was not at all interested in the physical requirements of the nervous system. Rather, he was interested in suggesting that we can get complex behavior from relatively simple devices, and simplicity translates into design requirements for a nervous system.

Simon asks us to imagine an ant moving about on a beach:

We watch an ant make his laborious way across a wind- and wave-molded beach. He moves ahead, angles to the right to ease his climb up a steep dunelet, detours around a pebble, stops for a moment to exchange information with a compatriot. Thus he makes his weaving, halting way back to his home. So as not to anthropomorphize about his purposes, I sketch the path on a piece of paper. It is a sequence of irregular, angular segments--not quite a random walk, for it has an underlying sense of direction, of aiming toward a goal.

After introducing a friend, to whom he shows the sketch and to whom he addresses a series of unanswered questions about the sketched path, Simon goes on to observe:

Viewed as a geometric figure, the ant’s path is irregular, complex, hard to describe. But its complexity is really a complexity in the surface of the beach, not a complexity in the ant. On that same beach another small creature with a home at the same place as the ant might well follow a very similar path.

What does this tell us about machine learning?

Think of the ant as the machine, that is, the computer system, and the environment as the HUMONGOUS pile of data it is walking through. What the machine does is quite simple. In the case of large language models, which is what I’ve thought the most about, the machine makes a guess about the next word and adjusts pa...
Basic Facts about Language Model Internals
by beren — 2023-01-04T13:01:35.223Z

This post was written as part of the work done at

Conjecture

.

As mentioned in

our retrospective

, while also producing long and deep pieces of research, we are also experimenting with a high iteration frequency. This is an example of this strand of our work. The goal here is to highlight interesting and unexplained language model facts. This is the first in a series of posts which will be exploring the basic ‘facts on the ground’ of large language models at increasing levels of complexity.

Understanding the internals of large-scale deep learning models, and especially large language models (LLMs) is a daunting task which has been relatively understudied. Gaining such an understanding of how large models work internally could also be very important for alignment. If we can understand how the representations of these networks form and what they look like, we could potentially track

goal misgeneralization

, as well as detect

mesaoptimizers

or

deceptive behaviour

during training and, if our tools are good enough, edit or remove such malicious behaviour during training or at runtime.

When faced with a large problem of unknown difficulty, it is often good to first look at lots of relevant data, to survey the landscape, and build up a general map of the terrain before diving into some specific niche. The goal of this series of works is to do precisely this – to gather and catalogue the large number of easily accessible bits of information we can get about the behaviour and internals of large models, without commiting to a deep dive into any specific phenomenon.

While lots of work in interpretability has focused on interpreting specific circuits, or understanding relatively small pieces of neural networks, there has been relatively little work in extensively cataloging the basic phenomenological states and distributions comprising language models at an intermediate level of analysis. This is despite the fact that, as experimenters with the models literally sitting in our hard-drives, we have easy and often trivial access to these facts. Examples include distributional properties of activations, gradients, and weights.

While such basic statistics cannot be meaningful ‘explanations’ for network behaviour in and of themselves, they are often highly useful for constraining one’s world model of what can be going on in the network. They provide pot...