I was invited by David Banks to give an introductory talk on large language models to the regional American Statistical Association meeting on large language models. Here are the slides:
- Bob Carpenter. 2023. Language models for statisticians: from n-grams to transformers to chatbots.
Most usefully, it has complete pseudocode up to but not including multi-head attention. It also has an annotated bibliography of the main papers if you want to catch up. After the talk, I added a couple slides on scaling laws and an annotated bibliography, which I didn’t have time to get to before the talk. I also added a slide describing multi-head attention, but without pseudocode.
P.S. The meeting was yesterday at Columbia and I hadn’t been to the stats department since the pandemic started, so it felt very strange.
P.P.S. GPT-4 helped me generate the LaTeX Tikz code to the point where I did zero searching through doc or the web. It also generates all of my pandas and plotnine code (Python clones of R’s data frames and ggplot2) and a ton of my NumPy, SciPy, and general Python code. It can explain the techniques it uses, so I’m learning a lot, too. I almost never use StackOverflow any more!
Bob, I appreciate the P.P.S. In my experience, a lot of people downplaying what LLM’s can do are the people who haven’t learned how to use them.
Yeah, it’s really quite lovely how much more streamlined using obscure LaTeX packages (or less familiar programming languages) has gotten for me. No more cycles of {want to do simple thing} -> {find relevant package and vignette} -> {modify their example} -> {verbose error message} -> {modify my modification} -> {verbose error message} -> …
Even just having something to bounce frustration off in these cases has been quite nice!
After some recent busyness concludes I mean to dive deeper into the transformer / LLM space to test out a few ideas. Is your talk recorded anywhere? Most of your refs are on my read / watch list and I can add the rest and this, too.
“I almost never use StackOverflow any more!”
Yeah, but does GPT-4 complain about the relevance of your question, blast you for failing to follow some obscure rule, edit your question so it loses its original meaning, and then mark your question as closed for being a duplicate?
…
No?
Isn’t it unfair that ChatGPT gets to do all this essentially by leaching off StackOverflow ( and other similar forums) without offering the original source zilch?
With all the agonizing about Plagiarism on here isn’t this a particularly egregious variation?
Furthermore what does this portend for the future of sites like ChatGPT. If Bob never has to refer to Stackexchange maybe sites like this will slowly fade away. If that happens does ChatGPT stagnate for lack of new material to feed off?
Is it egregious that you get to read Andrews blog and learn from all the contributors without paying them? Should you be paying the estate of ETJaynes if you utilize the knowledge you get from reading his book? How about the Physics books and Calculus books and such you read in school?
Rent seeking is bad, owning ideas is bad. Copyright is a stupid system but to the extent it is workable it must be shown that the output of the model is directly a derived work of the antecedent. It’s not plagiarism to say in your own words things that you learned about Calculus from having read a calculus book once. But if you open the text and type out the paragraph written there changing only a few words it is… You’re directly utilizing what was previously written to derive a mildly altered form.
The model “says in it’s own words” what it distilled from reading those things. It stands in relation to you saying “when I studied calculus they defined a limit as a number that no matter how close you were asked to get you could find a point where the function achieved that closeness”… Because that’s what you derived out of reading several books and hearing lectures.
Good point. Every day professionals use StackOverflow and related forums to help them do work for which they are compensated. Let he who is without sin, etc…
I hope that definition of a limit wasn’t in the calculus book you studied from. It says the limits of (sin 1/x) at 0 are all the numbers between -1 and 1.
Right, it needs some verbiage about “for all values closer than that” or “for all values larger than that” (limit at infinity)
To be fair, something that sounds plausible but is not correct seems an appropriate example of the things that models say.
Also to be fair although limits within standard analysis are not defined this way if you work with the alpha theory of non-standard analysis and take sin(1/x) for X in the series 1, 2, 3,… Then the axioms of that theory say that the ” value at Infinity” of that series does exist within the hyper real numbers defined in that theory! I would have to go back and read that paper to figure out what you can say about it though other than that it’s greater than -1 and less than 1
Why is it unfair? StackOverflow itself often contains answers that borrow from the documentation of libraries/packages or from intuition/explanations that exist in textbooks. Going one step further textbooks themselves often contain examples/explanations that are clearly inspired by other textbooks/professors. On your second point though, I do think ChatGPT will become worse in future iterations if there is nothing like StackOverflow from which it can learn from. We see a similar dynamic situation with SEO, where algorithms will degrade over time as individuals figure out how to game them
My hope is that LM training gets good enough that we’ll need less data in the future. Otherwise, this could be a problem if other people are like me.
The plagiarism threads are from Andrew, not me. Having said that, GPT isn’t plagiarizing any more than the rest of us in the sense that it’s not generating text verbatim that it finds online. So I wouldn’t call what they’re doing “leeching” any more than I’d call my reading StackOverflow “leeching”. For anything it says, it can zoom in and out in detail level and how advanced the presentation is and what style it’s in.
I have very mixed feelings about sites like Reddit and StackOverflow. They are like for-pay journals (almost all of them outside of ML) in that authors contribute all of their source material to them for free, contribute all the editing and community management for free, then they make money off of all of this authorial and editorial work without compensating contributors. Are they leeching? Is Google leeching off the web by providing search? Is YouTube leeching with abundant piracy. IP on the web is a mess.
The responses to this seem to be of the type “but *you* also read and summarize and remix stuff you read for free”. But that doesn’t make any sense, making a false equivalence of one human being reading one the one hand, with a global billionaire corporation reading *the whole Web* on the other hand.
It seems obvious that concepts like fair use, data governance and maintaining a commons of ideas should be applied differently depending on whether the actors are individuals, organizations, big bad global billionaire corporations or statistical prediction algorithms with billions of parameters that someone estimated at a cost of millions of dollars.
Also, Google is leeching and profiting of the open Web, yes. Now, as twenty years ago, we should ask why we allow corporations to wall off (through lock-in and monopoly power) and profit from the public good. The obvious remedies to curb them, taxation and breaking up monopolies, are harder to implement the larger these “shoggoths” get (https://archive.is/sLLYz)
+1
There’s also the issue that the LLMs lose the references. Back in the 5th generation (AI, not cell phones) days, NEC used Stallman’s copylefted (or whatever the term was in those days) GNU code as is. I thought Stallman should have been angered, but (a) he wasn’t, and (b) he was probably right. NEC included the copyleft message, and the authorship, in its products, fully meeting the copyleft conditions. (NEC’s ripoff of Intel’s microcode was another story, though.)
But the LLMs don’t include the references.
Bob, just a follow-up question. I’ve spent a lot of time with ChatGPT and am definitely impressed by it’s ability to write code, but by comparison, it’s ability to do math is shockingly bad. I’m curious as to why this is. Is it just about training material, i.e. ChatGPT was trained on a huge data set from Github, etc. but it’s hard to find comparable mathematical sources ? Or is there some more fundamental problems that make math more difficult? Or some combinations of the two?
It’s much better at math than it is at arithmetic. As of yesterday, I was able to share links to chats, but I don’t seem to be able to do that any more. But here’s an example of how it can help you learn math.
GPT: In the theory of Markov chains, particularly those over continuous state spaces, irreducibility is a key concept that ensures every state can be reached from any other state, either in a finite number of steps (for discrete state spaces) or with positive probability (for continuous state spaces).
The notion of ϕ-irreducibility extends this idea of irreducibility to a wider class of chains and is useful when considering chains on general state spaces. Essentially, a Markov chain is said to be ϕ-irreducible if for any starting state, it’s possible to reach any other state with a probability given by a measure ϕ that is positive for all non-null sets of the state space.
In the case of continuous state spaces, you could think of this as saying, “Given any small ‘blob’ in the state space, no matter where we start, there’s a positive probability we’ll end up inside that blob after some time.”
As for your question about other types of irreducibility: In addition to the standard irreducibility and ϕ-irreducibility, there are other related concepts in the literature of Markov chains, like Harris recurrence, positive recurrence, and ergodicity, all of which have to do with the long-term behavior of the chain. But these are more refinements or consequences of irreducibility, rather than different “kinds” of irreducibility per se.
Finally, regarding the use of the letter ϕ, it is simply a common notation in mathematics to represent a particular function or measure, in this case, the measure that helps define the irreducibility of the chain. The choice of the letter is more convention than anything else.
BC: In the theory of Markov chains, particularly those over continuous state spaces, irreducibility is a key concept that ensures every state can be reached from any other state, either in a finite number of steps (for discrete state spaces) or with positive probability (for continuous state spaces).
The notion of ϕ-irreducibility extends this idea of irreducibility to a wider class of chains and is useful when considering chains on general state spaces. Essentially, a Markov chain is said to be ϕ-irreducible if for any starting state, it’s possible to reach any other state with a probability given by a measure ϕ that is positive for all non-null sets of the state space.
In the case of continuous state spaces, you could think of this as saying, “Given any small ‘blob’ in the state space, no matter where we start, there’s a positive probability we’ll end up inside that blob after some time.”
As for your question about other types of irreducibility: In addition to the standard irreducibility and ϕ-irreducibility, there are other related concepts in the literature of Markov chains, like Harris recurrence, positive recurrence, and ergodicity, all of which have to do with the long-term behavior of the chain. But these are more refinements or consequences of irreducibility, rather than different “kinds” of irreducibility per se.
Finally, regarding the use of the letter ϕ, it is simply a common notation in mathematics to represent a particular function or measure, in this case, the measure that helps define the irreducibility of the chain. The choice of the letter is more convention than anything else.
GPT: If you’re working in a more rigorous setting with measure theory, a precise definition of ϕ-irreducibility for a time-homogeneous Markov chain {X_n} on R^N with respect to a measure ϕ on the Borel σ-algebra is as follows:
A Markov chain {X_n} with transition kernel P is called ϕ-irreducible if for every Borel set B ⊂ R^N with ϕ(B) > 0 and every x ∈ R^N, there exists a positive integer n such that
P^n(x,B) > 0.
Here, P^n(x,B) represents the n-step transition probability from the state x to the set B, and ϕ is a σ-finite measure on the Borel σ-algebra of R^N that gives positive measure to non-empty open sets.
In this definition, the kernel P is a way of expressing the transition probabilities in a form suitable for continuous state spaces. For each point x in the state space and each measurable set B, P(x,B) gives the probability that the next state will be in B given that the current state is x.
You might also find it helpful to think of this definition in terms of the distribution of the Markov chain at future times. Essentially, it’s saying that no matter where the chain starts, there’s a positive probability that after some number of steps, the chain will enter any region of the state space that has positive ϕ measure.
Note that this is a fairly general definition of irreducibility, and in practice, one often works with the special case where ϕ is Lebesgue measure (or counting measure, for discrete state spaces), because this corresponds to the usual notion of irreducibility: that every state can be reached from any other state. But the ϕ-irreducibility definition allows for the possibility of more exotic measures ϕ, which can be useful in some situations.
BC: OK, can you please give the me the same level of explanation for the concept of aperiodicity in a Markov chain. The context is that I’m setting up the conditions for a stationary distribution to exist.
GPT: Sure, aperiodicity is another crucial concept when studying the behavior of Markov chains. Here’s a formal definition followed by a simplified explanation:
Definition: A state i in a Markov chain is said to have period k if any return to state i must occur in multiples of k steps. Formally, the period of a state i, denoted by d(i), is defined as:
d(i) = gcd{n > 0 : P^n(i,i) > 0}
where gcd denotes the greatest common divisor, P^n(i,i) represents the n-step transition probability from the state i back to itself.
If d(i) = 1, then the state i is said to be aperiodic. A Markov chain is said to be aperiodic if all of its states are aperiodic.
Now, let’s try to simplify this:
Imagine you’re in a state i of a Markov chain. If there’s some number k such that you can only return to state i every k steps (and not on steps that aren’t multiples of k), then the state i has period k. For instance, if you find yourself returning to state i every 3 steps (and never in 1, 2, 4, 5, etc. steps), then state i has period 3.
However, if it’s possible to return to state i in 1 step, 2 steps, 3 steps, etc., then the greatest common divisor of these step numbers is 1. In such case, we say that the state is aperiodic.
If every state in the Markov chain is aperiodic (i.e., you can return to it in a number of steps with no common divisor greater than 1), then we say that the entire Markov chain is aperiodic.
In the context of continuous-time Markov chains or Markov chains on continuous state spaces, the notion of aperiodicity often needs to be modified or replaced with other conditions to ensure the chain doesn’t get “stuck” oscillating between a few states in a periodic manner.
For a Markov chain to have a unique stationary distribution, it needs to be both irreducible (every state can be reached from any other state) and aperiodic (the chain doesn’t get stuck in cycles). If these conditions are satisfied, then according to the Markov chain convergence theorem, the chain has a unique stationary distribution to which it converges as time goes to infinity, regardless of the initial state.
BC: I need the definition for a continuous Markov chain. Measure theoretic language is OK as long as it’s simple.
ChatGPT: A continuous-state Markov chain is a sequence of random variables {X_n} defined on a probability space that takes values in a continuous state space S ⊂ R^N, often equipped with the Borel σ-algebra.
The Markov property, which stipulates “memorylessness”, is typically defined as follows:
P(X_{n+1} ∈ B | X_n, X_{n-1}, …, X_1, X_0) = P(X_{n+1} ∈ B | X_n)
for all B in the Borel σ-algebra of S and all n. This means the probability that the next state X_{n+1} is in a given set B depends only on the current state X_n and not on the history of the process. This property should hold for all n and for every sequence of states the chain can pass through.
The transition probabilities of the chain … [BC stops output]
BC: Sorry, I meant the definition of aperiodicity. You gave me the typical definition for discrete chains originally.
GPT: I apologize for misunderstanding your question earlier. In the continuous state space setting, a Markov chain being aperiodic can be a bit more complex to define due to the lack of a natural notion of a “period” of a state. Here, aperiodicity is often replaced with the notion of Harris recurrence or positive recurrence, which ensure the chain doesn’t get “stuck” oscillating between a few states in a periodic manner.
However, one can still define an analogue of aperiodicity for continuous-state Markov chains using the concept of the spectral radius of the transition operator. Here’s a simple definition:
A continuous-state Markov chain is said to be aperiodic if the spectral radius of its transition operator is 1.
The transition operator of a Markov chain is a linear operator that maps one function of the state space to another, by averaging the function over the possible next states of the chain. Its spectral radius is the largest absolute value of its eigenvalues.
This definition captures a similar idea to aperiodicity in the discrete case: the chain doesn’t favor any particular “frequency” of transition between states. However, this is a somewhat technical definition, and in practice it’s often more useful to work with the notions of recurrence mentioned above when dealing with continuous-state chains.
BC: is there a standard notation for total variational distance between two measures over the same sigma-algebra?
GPT: Yes, the total variation distance between two probability measures P and Q on the same measurable space (X, Σ), is often denoted as ||P – Q|| or D(P, Q) and defined as follows:
||P – Q|| = 1/2 ∫ |dP – dQ|
or equivalently,
||P – Q|| = sup{ |P(A) – Q(A)| : A ∈ Σ }
where the supremum is taken over all measurable sets A in the σ-algebra Σ. The factor of 1/2 is sometimes included so that the total variation distance is a metric on the space of probability measures, i.e., it satisfies the triangle inequality.
This quantity measures the “distance” between the two measures in a sense, by summing up the absolute differences in the probabilities they assign to all possible events.
Note that while ||P – Q|| is the most standard notation, the actual notation may vary slightly depending on the author or context. Some authors may use D(P, Q) or TV(P, Q) (where TV stands for “total variation”), or other similar notations.
BC: what is the precise definition of a metric and is it just a proper distance measure?
GPT: In mathematics, a metric is a function that defines a concept of distance between any two members of a set, known as a metric space. The formal definition of a metric on a set X is as follows:
A metric d on a set X is a function (also called distance function or metric) d : X × X → R (where R denotes the real numbers) such that for all x, y, z in X, the following conditions are satisfied:
Non-negativity: d(x, y) ≥ 0 (distance is always non-negative)
Identity of indiscernibles: d(x, y) = 0 if and only if x = y (distance from a point to itself is zero, and only identical points have zero distance)
Symmetry: d(x, y) = d(y, x) (distance from x to y is the same as distance from y to x)
Triangle Inequality: d(x, z) ≤ d(x, y) + d(y, z) (the direct distance from x to z is no more than the sum of the distance from x to y and the distance from y to z)
If a function satisfies these properties, then it is a metric and (X, d) is a metric space.
In terms of your question about the relationship between a metric and a “distance measure”: In everyday language, we often use “distance” to refer to a particular kind of metric—the Euclidean distance, which corresponds to the usual idea of straight-line distance in space. However, in mathematics, a metric is a more general concept that can encompass many other kinds of “distance,” including some that may not correspond to any physical notion of distance. For example, the total variation distance that we discussed earlier is a kind of metric on the space of probability measures, but it doesn’t correspond to any physical distance. It’s just a mathematical tool for measuring the “difference” between two probability measures.
User
are there other common properties of general binary relations in addition to symmetry and transitivity?
ChatGPT
Yes, there are several other common properties of binary relations:
Reflexivity: A binary relation R on a set X is reflexive if for every element x in X, it holds that xRx (every element is related to itself).
Antisymmetry: A binary relation R on a set X is antisymmetric if for any two elements x and y in X, if xRy and yRx then x = y. This means that if a relation holds in both directions, then the elements must be identical.
Totality (or connexity): A binary relation R on a set X is total or connex if for all x and y in X, either xRy or yRx or both. This property is commonly used to define total orders, such as the usual order on the real numbers.
Euclidean: A binary relation R on a set X is Euclidean if for all x, y, and z in X, if xRy and xRz, then yRz. This property is typically used in the context of equivalence relations.
Serial: A binary relation R on a set X is serial if for every x in X, there exists a y in X such that xRy.
Preorder: A binary relation R on a set X is a preorder if it is reflexive and transitive.
Equivalence Relation: A binary relation R on a set X is an equivalence relation if it is reflexive, symmetric, and transitive.
Partial Order: A binary relation R on a set X is a partial order if it is reflexive, antisymmetric, and transitive.
Total Order: A binary relation R on a set X is a total order if it is a partial order and total.
Each of these properties corresponds to a different kind of binary relation, with different uses in mathematics. For instance, equivalence relations are used to define partitions of a set, while orders are used to arrange elements in a hierarchy.
User
how do you prove that the transitive closure of a set exists (i.e., there is a minimum transitive relation containing any relation)?
ChatGPT
The transitive closure of a relation R on a set X is the smallest relation R* that contains R and is transitive. It includes all pairs (a,b) such that there is a “chain” from a to b in the original relation R. The transitive closure of a relation always exists, and we can prove this by construction.
Here’s a sketch of the proof, based on defining the transitive closure in terms of paths in the relation:
For each pair (a, b) in the relation R, we can consider it as an “edge” in a directed graph, with the elements of X as the “vertices” of the graph.
For each pair of vertices a and b, we say that a is related to b in the transitive closure R* if and only if there is a (directed) path from a to b in this graph. This path could just be a single edge (if (a, b) is in R), or it could be a longer path involving multiple edges.
This gives a well-defined relation R* on X, because for any pair of elements a, b in X, it’s a well-defined question whether or not there’s a path from a to b in the graph.
By definition of a path, the relation R* is transitive: if there’s a path from a to b and a path from b to c, then we can just combine these paths to get a path from a to c.
Also by definition, R* contains R: if (a, b) is an edge in the graph, then there’s a path (of length
User
can’t we do this more simply by induction and taking limits of stepsize transitive closures?
ChatGPT
Yes, you’re correct. That’s a more elegant and mathematically rigorous way of demonstrating it. The transitive closure can indeed be constructed iteratively, which will also establish its existence. Here is a simplified sketch of the proof:
Let’s start with a relation R on a set X. We’ll define a sequence of relations {R_n} as follows:
R_0 = R (i.e., the 0th relation in the sequence is just the original relation R)
R_{n+1} = R_n ∪ {(x, z) : there exists a y such that (x, y) ∈ R_n and (y, z) ∈ R_n} (i.e., for each subsequent relation, we add in any pairs that can be connected by a pair already in the relation)
What we’re doing here is iteratively adding pairs (x, z) whenever there’s a “two-step path” from x to z via some y. After one step, this adds all pairs that can be connected in two steps via the original relation, after two steps it adds all pairs that can be connected in three steps, and so on.
The transitive closure of R is then defined to be the union of all these relations:
R* = ⋃_{n=0}^∞ R_n
By definition, R* contains R (since R = R_0 is the first term in the union), and it is transitive (since we’ve added in all “paths” of all lengths).
And it’s the smallest such relation, because any transitive relation containing R must also contain all the R_n’s (because any path in R must also be a path in any transitive relation containing R), and hence must contain their union R*.
Therefore, the transitive closure R* exists, and it’s the smallest transitive relation containing R. This approach avoids any need for graph theory and can be carried out entirely within the framework of set theory.
User
how do I define the stationary distribution of a Markov chain over a real-valued state space R^N? I’m OK with having the chain be a sequence of random variables X_0, X_1, … over a measure P and having the stationary distribution Qr be another measure over R^N.
ChatGPT
Sure, let’s denote by {X_n} the Markov chain, which is a sequence of random variables defined on some probability space and taking values in R^N. Let’s denote by P the transition kernel of the chain, which gives the conditional distribution of X_{n+1} given X_n for each n.
The stationary distribution of this chain, if it exists, would be a probability measure π on R^N with the property that “moving according to the transition kernel P doesn’t change the distribution”. In formal terms, this can be written as:
π(B) = ∫ P(x, B) π(dx) for all Borel sets B ⊂ R^N
Here, the integral is taken with respect to the measure π, and P(x, B) is the conditional probability that X_{n+1} is in the set B given that X_n = x, under the transition kernel P. Intuitively, this equation says that if we start with the distribution π and then make one step according to the transition probabilities P, we end up with the same distribution π.
It’s important to note that not all Markov chains have a stationary distribution, and some chains may have multiple stationary distributions. Certain conditions, such as irreducibility and positive recurrence (or aperiodicity in the discrete state space case), can ensure the existence of a unique stationary distribution.
When a unique stationary distribution π exists and the chain is ergodic (which means that starting from any initial state, the chain’s distribution converges to π as time goes to infinity), the chain is said to be “stationary” or “invariant” under π, and π is called an “equilibrium” or “invariant” measure.
User
Can you help me understand what π(B) = ∫ P(x, B) π(dx) means? I understand how to interpret p(x, B) where B is some element of the Borel algebra. What I don’t understand is the π(dx) notation. If pi is a measure, I think of it as mapping events in the Borel algebra to probabilities in [0, 1]. If I assume a density corresponding to my measure over the Borel algebram does that make it easier to write the integral for me?
ChatGPT
The notation π(dx) is often used to denote that we’re integrating with respect to the measure π. When we’re dealing with a measure that has a density (like the Lebesgue measure on R^N or a probability measure with respect to Lebesgue measure), we often write this in the “dx” notation that you’re likely familiar with from calculus, like ∫ f(x) dx.
If π is absolutely continuous with respect to the Lebesgue measure (i.e., it has a density), let’s denote its density by p(x). Then, you can think of π(dx) as p(x) dx, and the integral ∫ P(x, B) π(dx) would become ∫ P(x, B) p(x) dx, where now the integral is a standard Lebesgue integral over R^N.
The equation for the stationary distribution then reads:
π(B) = ∫ P(x, B) p(x) dx for all Borel sets B ⊂ R^N.
Here, the left-hand side π(B) is the measure of the set B under the stationary distribution, and the right-hand side is the expected measure of the set B after one step, under the transition kernel P, when the chain is initially distributed according to π.
Remember, though, that not all measures have densities. Measures that don’t have a density (with respect to Lebesgue measure) are often called singular measures, and they can be a bit trickier to work with because we can’t represent them with a density function p(x). In those cases, we have to use the π(dx) notation to denote integration with respect to the measure π, as we can’t reduce it to a standard Lebesgue integral.
User
is there a way to make a slightly larger strut than \strut in LaTeX?
ChatGPT
In LaTeX, \strut is a command that inserts a vertical space the height and depth of the parenthesis in the current font size. There’s not a built-in command for a larger strut, but you can easily create a custom command that provides a larger strut. Here’s an example:
latex
Copy code
\newcommand{\bigstrut}[1][1]{\vrule width0pt height#1\baselineskip depth#1\baselineskip}
This \bigstrut command takes an optional argument which is the size of the strut in units of the current \baselineskip (the normal distance between lines). If you don’t provide an argument, it defaults to 1, so \bigstrut is the same size as a regular \strut. But you can provide a different argument to make a bigger strut, like \bigstrut[1.5] for a strut 1.5 times the normal size.
Remember to add this custom command in the preamble of your LaTeX document. That is, put it somewhere between \documentclass{…} and \begin{document}.
Note: Be cautious when using \bigstrut. If you use it excessively, it can lead to inconsistent line spacing in your document, which can make it harder to read. Generally, it’s best to stick with the standard \strut unless you have a specific reason for needing a larger strut.
User
what does it mean when a result holds for pi-almost every x in X where X is the state space of a Markov chain and pi is a measure over X.
ChatGPT
The phrase “a result holds for π-almost every x in X” is a way of saying that the result holds for all elements in the state space X, except possibly for a set of elements that has measure zero with respect to the measure π.
To make this more concrete, consider the real numbers R with the standard Lebesgue measure (where the measure of an interval is just its length). A property holds for “almost every” x in R if the set of x’s for which it doesn’t hold has measure zero. For instance, the function f(x) = 1/x is defined for “almost every” x in R, because the only x for which it’s not defined is x = 0, and the set {0} has measure zero.
When we say that a result holds for π-almost every x in X, we mean something similar, but with respect to the measure π rather than the Lebesgue measure. For example, if X is the state space of a Markov chain and π is its stationary distribution, then a property that holds for π-almost every x is one that holds for all states except possibly a set of states that has total stationary probability zero.
One place where this comes up is in the statement of the ergodic theorem for Markov chains, which says that under certain conditions, the time-average behavior of the chain converges to its space-average behavior for π-almost every initial state. This means that for any initial state, except possibly a set of states with total stationary probability zero, the time average and space average behavior will be the same.
User
Are the conditions for the ergodic theorem just phi-irreducibility and aperiodicity and having a stationary distribution?
ChatGPT
In the context of Markov chains, particularly those with a countable (or finite) state space, the typical conditions required for the Ergodic Theorem to hold are indeed irreducibility, aperiodicity, and the existence of a stationary distribution.
Irreducibility ensures that every state can be reached from every other state, aperiodicity ensures there are no deterministic cycles in the chain, and the existence of a stationary distribution provides a long-term equilibrium distribution to which the chain converges.
However, in the context of continuous state spaces or more complex scenarios, the conditions might vary and could be more complicated. The phi-irreducibility you mentioned is one of those more general conditions used for Markov chains over continuous state spaces to ensure the chain is irreducible with respect to some measure.
Furthermore, the existence of a stationary distribution does not automatically imply that the chain will converge to this distribution, this is where the concept of ergodicity comes in, and it often requires additional conditions.
Finally, the specific conditions can also depend on what exactly you mean by the Ergodic Theorem: some versions talk about the convergence in distribution of the chain to its stationary distribution, others about the almost sure convergence of time averages to space averages (these are not exactly the same!).
Therefore, while irreducibility, aperiodicity (or their suitable counterparts in more general contexts), and existence of a stationary distribution are often important conditions, the exact conditions can depend on the precise context and version of the Ergodic Theorem being considered.
User
I’m trying to write out a statement of at least one form of the ergodic theorem. This is what I have. Do you have suggestions for fixing this or even just tightening up the prose?
Suppose $X = X_0, X_1, \ldots$ is a Markov chain on the state space
$\mathbb{R}^N$ with measure $\Pr.$ Suppose $Q$ is a second
measure over the Borel algebra of $\mathbb{R}^N.$
If the chain $X$ is $Q$-irreducible and aperiodic,
then for almost every $x \in \mathbb{R}^N,$
$$
\lim_{n \rightarrow \infty}
\left|\left| \, \strut
\Pr[X_n \in A] – Q[A]
\, \right|\right|
\rightarrow 0.
$$
ChatGPT
Your statement is on the right track but it seems to be a mix of two related concepts: the definition of a stationary distribution and the ergodic theorem.
A stationary distribution π of a Markov chain is often defined by the property that if the chain is in this distribution at one time point, it remains in this distribution at the next time point. In other words, for every measurable set A, π(A) = ∫ P(x, A) π(dx) where P is the transition kernel of the chain.
The ergodic theorem, on the other hand, is usually about the time averages of a function along the trajectory of the chain, and it says that under certain conditions (like irreducibility and aperiodicity), the time averages converge to the space averages almost surely.
Here’s an attempt to rephrase your statement to make it more in line with a typical statement of the ergodic theorem:
Suppose {X_n : n ≥ 0} is a Markov chain on the state space R^N with transition kernel P. Suppose further that the chain is φ-irreducible and aperiodic for some measure φ. If π is a stationary distribution of the chain, then for φ-almost every x in R^N and any function f : R^N → R that is integrable with respect to π, we have
1/n ∑_{k=0}^{n-1} f(X_k) → ∫ f dπ
as n → ∞, almost surely.
In words, this says that the time average of the function f along the trajectory of the chain converges to the space average of f with respect to the stationary distribution, for almost every initial state of the chain.
User
I’m reading a book by Jeff Rosenthal and he states the theorem in terms of total variation distance converging to zero almost everywhere:
If a discrete-time Markov chain on a general state space is phi-irreducible and aperiodic, and furthermore has a stationary distribution pi, the for pi-almost every x in X, we have that \lim_{n \rightarrow \infty} sup_{A \in F} | P^n(x, A) – pi(A) | \rightarrow 0.
Here P^n(x, A) is n steps of the transition function. I would like to just assume a Markov chain X_0, X_1, … and a standard measure for it so that one step is P(x, A) = Pr[X_{n + 1} \in A | X_n = x]. So should I just be setting X_0 = x and then stating the limit in terms of X_n?
ChatGPT
If you have a Markov chain {X_n : n ≥ 0} with X_0 = x and you’re interested in the behavior of the chain after n steps starting from x, you would indeed consider the transition function P^n(x, A), which gives the probability that X_n is in the set A given that X_0 = x.
However, the notation Pr[X_{n + 1} ∈ A | X_n = x] describes the transition probability P(x, A), which gives the probability that the chain is in the set A at the next step given that it’s currently at x. The “n + 1” here isn’t indicating n steps from x; it’s indicating one step from x, regardless of what n is.
To write the statement you’re referring to with the setup you’ve described, you might say something like this:
“Suppose {X_n : n ≥ 0} is a Markov chain on a state space X with transition probabilities P(x, A) = Pr[X_{n + 1} ∈ A | X_n = x]. If the chain is φ-irreducible and aperiodic and has a stationary distribution π, then for π-almost every initial state x in X, we have
lim_{n → ∞} sup_{A ∈ F} | Pr[X_n ∈ A | X_0 = x] – π(A) | → 0.
Here, Pr[X_n ∈ A | X_0 = x] = P^n(x, A) is the probability that X_n is in the set A given that the chain started at x. The limit statement says that as n goes to infinity, the maximum difference over all sets A in the sigma-algebra F between the actual probability that X_n is in A and the probability under the stationary distribution π goes to zero.”
This statement is essentially the one you quoted from Rosenthal, but with the explicit description of P^n(x, A) as Pr[X_n ∈ A | X_0 = x] to make clear that it’s referring to the chain’s distribution after n steps from the initial state x.
User
That’s a huge help. Thanks. Is there a standard name for this theorem?
ChatGPT
Yes, the theorem you described is a version of the Ergodic Theorem for Markov chains. The Ergodic Theorem is a fundamental result in the study of stochastic processes, including Markov chains, and it provides conditions under which long-run averages taken along a single realization (path) of the process can be used to describe the overall behavior of the process.
Remember, however, that there are different versions of the Ergodic Theorem that apply in different contexts (e.g., for deterministic dynamical systems, for stochastic processes like Markov chains, etc.), and even within the context of Markov chains, there are different versions of the theorem depending on the specific setup (e.g., countable state space, general state space, etc.).
The specific version you are looking at is sometimes referred to as the Ergodic Theorem for general state space Markov chains. In this version, the conditions of phi-irreducibility, aperiodicity, and the existence of a stationary distribution are used to ensure the convergence in total variation distance of the distribution of the Markov chain after n steps to the stationary distribution.
User
is there a reason people write sup rather than max?
ChatGPT
Yes, there is a specific reason for using the supremum (sup) instead of the maximum (max). The distinction comes from the context in which they are used: finite sets versus infinite sets.
The term “maximum” is used when dealing with a finite set of numbers, where you can definitively point to the largest number in the set. For example, the maximum of the set {1, 2, 3, 4, 5} is 5.
On the other hand, “supremum” is a concept used for possibly infinite sets, and it refers to the smallest upper bound of the set. An upper bound of a set is a value that is greater than or equal to every number in the set. The supremum is the least of these upper bounds. For some infinite sets, the supremum may not actually be in the set itself. For example, the supremum of the set of numbers less than 1 is 1, even though 1 is not in the set.
When dealing with sets in measure theory or functional analysis, which can be infinite, the supremum is the appropriate concept to use. So, in the context of the Ergodic theorem and similar results, we typically speak about the supremum over all measurable sets in a sigma-algebra, which is an infinite collection, hence the use of “sup” instead of “max”.
User
I’m reading more measure theoretic MCMC and found a statement of $\pi$ being the stationary distribution of a chain with transition $P(x, dy)$ and statespace $\mathcal{X}$ as $\int_{x \in \mathcal{X}} \pi(dx) P(x, dy) = \pi(dy)$. Can you translate that into something with ordinary Lebesgue integrals? Can it be done purely with density functions rather than $P(x, dy)$, which I think refers to the transition from a point $x$ to a probability mass $dy$ but I don’t quite understand the $dy$ notation.
ChatGPT
The integral equation you’ve written, ∫_{x ∈ X} π(dx) P(x, dy) = π(dy), is a way to state that π is a stationary distribution of the Markov chain in a measure-theoretic context. The “dx” and “dy” in this context are differential forms of measures, and the integral is with respect to the measure π.
To understand this, let’s start with a simpler case where the state space X is a subset of the real numbers, and both the transition probabilities P and the stationary distribution π have density functions p(x, y) and π(y), respectively, with respect to the Lebesgue measure. Then, we can write the integral equation in terms of ordinary Lebesgue integrals as follows:
∫_{x ∈ X} p(x, y) π(x) dx = π(y)
for every y in X. This equation says that if you start from a state distributed according to π, then transition according to P, the resulting distribution of the new state is still π.
When the state space X is not a subset of the real numbers, or when the measures P(x, ·) or π do not have density functions with respect to a common reference measure, we might not be able to write the integral equation in terms of ordinary Lebesgue integrals. In these cases, the differential forms dx and dy are used to indicate that we are integrating with respect to the measures π and P(x, ·) themselves, not with respect to a separate reference measure. The expression P(x, dy) is a way to denote the measure of the set dy when you transition from state x according to the transition probabilities P.
So in the more general context, the integral equation ∫_{x ∈ X} π(dx) P(x, dy) = π(dy) can be understood as a generalization of the equation ∫_{x ∈ X} p(x, y) π(x) dx = π(y) in which we don’t assume the existence of density functions p and π.
And I went on for several more pages. I’m using it to shore up the intro to probability theory and stats using simulation and Stan that I’m writing.
Bob, how do you interface with GPT-4 to generate useful code? I have been trying to tap into it using a paid version of chatgpt but it can be quite irritating to communicate with it about code, and it often makes quite basic errors/doesn’t properly implement things when trying to generate R code – but clearly there is a lot of potential. If you could share any brief tips/best practices/general approach to get the most out of it, I’d really appreciate it.
I’d also be curious in learning any tips/approaches. Personally I’ve been using GPT-4 to speed up my chart creation and data cleaning in Python, for myself some things I’ve noticed that have helped its performance are:
– Tell it to use specific libraries. Otherwise it too often makes errors while trying to apply methods for objects from one library to objects for another. This might be less of an issue in R, this aspect of Python personally drives me nuts
– Break down the task into smaller chunks. It always seems to err on the side of trying to do something it can’t actually do. So if you keep the asks small, and just do a series of prompts instead of one large prompt it’s less likely to make a mistake
– Just keep iterating. It’ll make an error, just plug in the error and let it fix it. Tell it to keep explanations brief to reduce the amount of time you spend waiting for tokens to generate
There are also MOOCs on Prompt Engineering offered on sites like Deeplearning/Coursera, they have some good tips there too. In general though everyone is still learning, so I’d expect the best practices to change over time. For me it is still unreliable enough that I don’t trust it to do anything I can’t easily verify/I don’t understand well myself. Generating LaTeX slides is a great application of GPT4, because LaTeX is very cumbersome and the output is easily verifiable. The same goes with creating charts/figures in Python.
I basically just tell it what I want and it gives me the code. The more precise you can be in what you are giving as inputs and what you want as outputs, the better the result. Here are some examples:
BC: how can I get a display of test coverage of a pytest run in python?
BC: In Python with NumPy, if I have an input variable chains : list[numpy.typing.ArrayLike]. I want to replace each value in this structure with its rank (starting from 1). So if the list chains is of size 4 and each entry has 100 entries, I want the ranks to range from 1 to 400.
BC [follow up]: array.size doesn’t work here—it says AttributeError: ‘list’ object has no attribute ‘size’. How do I get the size of a list?
BC [following up again]: same problem for array.shape
BC: Is there an inverse cdf implemented for the standard normal in numpy? And if not, is the inverse error function (inverse erf) implemented?
BC: Can I apply norm.ppf() to the entire list chains : list[numpy.typing.ArrayLike] or transform the list of arrays somehow?
BC: if i’m generating doc for python with sphinx is there a way to cross-reference another function in the package?
BC: how can you convert a wide form matrix to a long form matrix in pandas
BC: how do I divide a pandas data frame into two parts randomly where one part has 10% of the data and the other part has 90% (rounded).
BC: I am writing a python library that calls into a C DLL using `ctypes`. How can I create a callback to check for Control-C interrupts?
BC: how can I add space between math and the fraction bar in LaTeX? When I type \frac{a}{b}, the a and b are too close to the horizontal bar.
BC: I want to generate a Tikz diagram in LaTeX. I’m going to describe it to you layer by layer from the top down. The arrows should all be aligned and the parameters should all be aligned and the boxes should all be aligned and the same width.
Row 1: 2 arrows pointing down, parallel to each other, with $\textrm{tok}_1$ and $\textrm{tok}_N$ as labels to the right and $\cdots$ between them.
Row 2: A circled $\alpha$ with an arrow to the right to a wide rectangular box with text “position \& lexical embed”. The text should be sans serif and the boxes should be thicker than the usual default.
Row 3: 2 arrows pointing down, aligned with those in Row 1. They are labeld $x_^0_1$ and $x^0_N$ to the right and there are $\cdots$ in between aligned with those in row 1.
Row 4. A circled $\beta^1$ with an arrow to the right to a rectangular box labeled “attention layer 1”.
Row 5: Two arrows going down, labeled $x^1_1$ and $x^1_N$ to the right, with $\cdots$ in between.
Row 6: Just $\cdots$ below the two arrows in Row 5.
Row 7: Two arrows going down, labeled $x^{K-1}_1$ and $x^{K-1}_N$ to the right with $\cdots$ in between. Aligned with row 5.
Row 8: A circled $\beta^K$ with a right arrow to a box labeleed “attention layer $K$”.
Row 9: Two arrows going down, labeled $x^K_1$ and $x^K_N$ to the right, with $\cdots$ in between. Aligngned with row 7.
Row 10: A circled $\gamma$ witha right arrow to a box labeled “logistic regression”.
Row 11: Two arrows going down, labeled $\textrm{prob}_1$ and $\textrm{prob}_T$ to the right, with $\cdots$ in between.
Question. On the slide “Loss vs. tokens, model size”, the leftmost plot says one of these models with more parameters achieves better test loss on a fixed size dataset than one with less parameters.
Should I read the x-axis as:
* We hold the dataset this constant size, and run the training for a really long time
* or, We consume X many tokens — the models with more parameters take more time to train
There are a couple results that matter. One is that for a given compute budget (in flops), there’s an optimal number of training tokens and model parameters. Another is that at a given training set size, there’s a maximum number of parameters beyond which it’s not helpful to grow the model.
Andrew and I were talking about this abstractly (as were many other people) in terms of how big of a model can you fit with a given data size. With very little data, you can’t fit a complex model because you can’t estimate all the parameters. With too much data, a complex model becomes computationally intractable.
Hi Bob, is there a link to the recording of the talk?
the talk was not recorded.
I fed ChatGPT some relatively simple Python problems. Each code produced had an error. Particularly watch out for how it deals (or doesn’t deal) with NaNs and the like. The code produced were relatively short, but imagine a longer more complicated code where stuff like this is hidden.
Roy:
This is related to Gary Smith’s point that the big risk of AI is not that it’s so smart, but that people will fool themselves (or get fooled) by attributing to AI abilities that it does not have.