pal.k: Yeah. So like, David said, I'm a 1st year. Phd student. So my background was I did an undergrad in neuroscience and chemistry and philosophy minors. And then I did a master's in biomedical engineering, and during my master's I worked in connectomics. Which is this subfield of neuroscience that's all about mapping connections between brain regions.
pal.k: And so it's this sort of growing subfield and a big focus in neuroscience right now and
pal.k: So when I was done with my master's, I worked in industry for 2 years. I did. I worked at a startup that was doing machine learning for drug development. So we did.
pal.k: We we built tools for precision medicine. So better if anyone knows what an oligonucleotide is. Oligonucleotide therapies. And so then I got really interested in interpretability, and, you know, started reading a bunch of papers in this field on the side and sort of getting to know, you know, who's publishing where and stuff. And so that's how I ended up
pal.k: reaching out to David. And joining the lab and starting. Phd, so yeah. So so today I'm gonna be talking about something a little bit out of distribution for our meetings. Which is I'm calling it a whirlwind tour of statistical learning on graphs.
pal.k: so so the background for this. So for anyone who doesn't know this is a textbook that we just finished in like early September, right? As I was starting. My Phd, we have a publishing contract with Cambridge University Press, and so it's out for copy editing with with Cambridge right now, and so it should be in full book form in
pal.k: I don't know how long. It's pretty unclear, maybe, like 8 months a year. They they've been pretty, you know, high variance about when it's actually when it's actually happening. But
pal.k: so. But the background behind this book was basically
pal.k: so like, I said, I was in this, this field of neuroscience called connectomics. This field sort of got started in the eighties. When you have these little roundworms called C elegans, and they have tiny little nervous systems with only about 300 ish neurons, 305.
pal.k: And so they were the 1st animal to have their entire nervous system fully mapped out. So all of the which neurons connect to which other neurons is fully traced. Where the neurons are is completely mapped out. You can go online, you can browse all the different neurons and look at their connections and all this other stuff.
pal.k: And so that sort of spawned this growing movement to like move up the you know animal tech tree. So recently, there's been this big effort to map out the fly brain. And so that's you know, way harder than 300 neurons. It spurred all the development of techniques in connectomics for
pal.k: you know, automating the process of tracing neurons in 3D. So there's all this kind of research coming out of this area in service of this effort. And then one of the research areas is, you know, can you? Once you have a brain mapped out and you can you view it as a graph. Right? So you have a bunch of neurons. They have connections with other neurons.
pal.k: And so that's just naturally lends itself to like a graph structure right where neurons are nodes and white matter connections are edges. And so the group that I worked on
pal.k: oops, the the group that I worked with
pal.k: was really not involved in the biology side of things at all. It was really involved in the developing statistical techniques to work with graphs. You know once once you have a connectome that's usable. And so, you know, sort of the surrounding group. This was a Johns Hopkins, and we worked with
pal.k: you know, the statisticians in the math department and in the computer science department. And so it was this joint effort. For, like 10 years, we also had a University of Chicago and University of Illinois, someone at Ut Austin, a lot of people sort of co-publishing for for many years. And so it created this body of research that became big enough that it was worth turning into a textbook. So this idea of
pal.k: writing a textbook was sort of floating around the lab, and then me and one of the Phd. Students in the lab at the time Eric Bridgeford just said, like, you know, let's do it. Let's just like, sit down and start writing it. And so that became my master's thesis.
pal.k: Eric and I kept working on it. After I graduated I stopped for like 6 or 7 months. And Eric just kept going and then I hopped back on it. And and we got our publishing contracts. And and yeah, so that's the background behind. How this.
pal.k: how this happened. So I I just want to start out. So the the structure of this talk is going to be I'm just going to pull out this sort of like really central concept.
pal.k: that we developed throughout the 1st half of the textbook, and just sort of explain it in in the 1st half of this talk, and then the second half is going to be. How can you take this and apply it in in lots of different application areas and sort of expand on it? And what other techniques can you can you find to learn stuff about about networks.
pal.k: and and we also made the decision to call graphs networks instead of graphs, because we didn't want people getting confused with plots. I didn't like the word graph, because, you know. But then we also have the problem that a network is also a neural network. So you know, it's the same boat, anyway. So but but yeah, so I just want to start out by you know, defining a little bit what I mean when I say network. So here's an example of
pal.k: sort of a pretty standard network. And there's a few questions that you can ask about it, right? So you have nodes here and you have edges between notes. But this network has a little bit of structure. So you have 2 communities in this example. It's 2 schools. And
pal.k: and so so and it's, it's Facebook friend connections between with 2 schools. And it's just like a subgraph of that. And so so you can see here that most of this friend group in the 1st school they're part of this 1st community. There's another friend group in the second community. And then there's this outlier note here. So you know.
pal.k: in our example. Maybe you know, this is northeastern, and this is Mit, and then, you know, there's someone who likes to go to the I don't know. This is Harvard, and there's someone who likes to go to the Harvard AI safety, you know thing. And so then they make friends with a bunch of the Harvard AI Safety people. Right? So so some questions you could ask is, you know, if you didn't know this community structure in advance, how could you find it right? Or another question you could ask is, you know? How do I?
pal.k: How do I find out what this outlier node is? And how do I even discover that this is an outlier node without knowing the community structure in advance.
pal.k: And so there's other questions that you can ask once you have more than one network. Right? So, for instance, if you had a bunch of different brain networks of musicians, you could say, can I classify brain networks into musician brains and non-musician brains? So in this case it's a classification task.
pal.k: and you give a binary node label to each network. And so there's some interesting work in connectomics that shows that if you have MRI scans, and you build networks out of those MRI scans you can predict some properties with with, you know, non chance accuracy. So, for instance, you can predict gender with.
pal.k: you know, not 100 accuracy, but certainly far, far beyond chance. So there's there's a lot of you know, sort of promising work in this. There's another you know. In another situation you might have node features. So you know you have your network. It has its topology. But then you also might have for every node. You might have a vector of features. Right? So if it's our school example, each person might be associated with like.
pal.k: I don't know their height and their age, and whatever right and and so you, you would like some ways to incorporate these node features into your learning methods. So that's another situation that can pop up. There's a lot more situations. So you can have directed networks. You can have edge weights. You can have nodes with edges to themselves. You can have, like multiple connected components.
pal.k: You can go crazy and say that like nodes can have multiple edges with each other. Whatever. But we're just going to focus on like the really simple case of you have an unweighted, undirected network. You know, there's no self loops, there's nothing weird. It's just like a really standard network. And so
pal.k: the way that you represent this usually is with this adjacency matrix. So just, you know, so that we're comprehensive. The way that an adjacency matrix works is you have this network here and you give an index to every node, and then for pairs of nodes that have an edge in them. You put a
pal.k: a 1 in the row and column corresponding to that edge. So here you have. Row one and column 2, and there's an edge there, so there's a 1 in in Sorry. Yeah. In row in row 2 and column one. So I actually had that reversed. But
pal.k: yeah. So that's how the adjacency matrix works. The the
pal.k: the issue that you run into in real life. A lot of the time is that the network that you see isn't actually a perfect representation of the network that you would like to see. So you know, this is sort of what statistics is all about. You get this noisy draw from the distribution that you actually care about, and so
pal.k: So you might have missing nodes. You might have missing edges. You know. If you're getting multiple networks, you might be missing like an entire one of the networks right?
pal.k: and so so so the way that we want to frame investigation is we have this this network that we see. And it's just a sample from the distribution that we actually care about and so
pal.k: so we're going to view networks as random variables. And so for anybody who hasn't taken probability, a random variable is essentially just a variable, whose value depends on some probability distribution. That's like a pretty decent way to think about it. And so when I say networks
pal.k: are random variables, what I mean is that so? There's a case where you could say that the number of nodes is random. But let's just ignore that case, and let's say that the number of nodes is fixed. But the edge probabilities between pairs of nodes is not fixed. Or it's it's yeah that it's not fixed. And so so when we see a network, what we're actually seeing is that every edge is sampled with the probability. And so
pal.k: So the way that you define this rigorously is, you have this probability matrix, that's the same size as your adjacency matrix. But instead of there being ones and zeros in each place.
pal.k: there's probabilities between 0 and one. And then you just sample from this probability matrix to observe a network. And so the object that you really care about is this probability matrix? And that's sort of what you're trying to, what you're trying to get at. And one way of
pal.k: viewing this, that's sort of nice is that if you got really really sure about what your probabilities were, so you kind of took the limit. And you said, I'm 100% sure in my observation that every edge is going to be there every single time. If I observed a new network.
pal.k: then the probability matrix just collapses into being the adjacency matrix, because every edge probability is just one. And so you know, that's in the we're ignoring edge weights right now. But so you know. So that's like kind of a good way to think about it. So there's
pal.k: There's a lot of different probability distributions that you can define on network valued random variables. So the most rain dead simple one is, you can just say every edge is going to be sampled with some probability, and they're all going to be sampled with the same probability. So this is called an network. And so in this case all you're saying is, you know.
pal.k: every edge is sampled with a 30% probability and and then you have the symmetry right? Because, because you're you're you have undirected networks. And so you know, you 30% probability here, here, you could say that every edge is sampled with a 70% probability.
pal.k: whatever. This case, isn't that interesting? Because there's no structure to a graph that's sampled in this way. And so you want to get a little bit more interesting. And so, taking our school example from before we could say that instead of every edge being sampled independently with the same probability.
pal.k: we have a community structure. And so we're going to assign every node a community. And so we're going to have this vector of community assignments for each node. And then we're going to have this matrix that says for community one, any node, any pair of nodes that's that are both in community. One are going to have the same probability, and any pair of nodes that are in community. 2 are also going to have the same probability. And for nodes that are
pal.k: in different communities, they're gonna have a lower probability. Right? So here, you know, students between different schools are gonna have a probability of of 10% of being friends. And in the 1st school, 60% in the second school, 40%. So you know. And so now, that's kind of nice. We're getting a little bit more. we're building a bit more structure,
pal.k: and and there's there's there's more stuff that you can do here right? You can get pretty complicated with the types of distributions that you define on networks. So so you know, for instance, you could say that. What if we want to say that there's a bunch of popular kids in like school, one or like, there's 1 popular kid who has like on average, like way more friends than than all the other kids. So you know, you could define networks. That account for that. You can do all kinds of crazy stuff.
pal.k: I'm not going to talk about any other network valued random variables, except that I'm going to be focusing the rest of this talk on this
pal.k: network valued, random, variable, that's called a random dot product graph. And so
pal.k: these things are really useful. And so a lot of the theory that's been built around these types of network value probability distributions is built around these random dot product graphs. And so the way that this works and this is going to actually be familiar to a lot of deep learning people is, every node is associated with a vector
pal.k: and so you have this, basically, it's just an embedding matrix. That's the same as any embedding matrix that you would see where the the rows are nodes and and they live in some d dimensional Euclidean space and and and so the way that we're going to define our probability. Matrix.
pal.k: is, we're going to define an inner product space on this on this latent position matrix. And so we're going to say that the
pal.k: edge probability for any given pair of nodes is defined by their dot product. And so, you know, there's a few constrictions that you need to make on the types of vectors that you can have. Right? So their dot products need to be positive values.
pal.k: and they need to be between 0 and one. But as long as you've constricted your space, such that nodes in the space can only live in that part of the space, then you have a fully defined probability matrix by taking the Xx transpose right? So the dot product between every pair of rows.
pal.k: And you know. So so now we're like kind of in business, because now we have this like embedding space that we can use to like. Try to understand networks. And it's it's it's it's the probability matrix is fully defined by this embedding space and so
pal.k: so, so.
pal.k: so just rolling with this. Say, we have a real network.
pal.k: Well, actually, there's 1 more thing I wanted to say. So. A really nice thing is that if you view
pal.k: the magnitudes, if you just put every node on the unit sphere so that they have magnitude one, then the dot product is just the cosine of their angle right? And the cosine function is bound between negative one and one. And so if you restrict where, in the space they're allowed to be, then the cosine function is bound between 0 and one.
pal.k: So you can think of the probabilities as just the cosine of their angle, if you you know, if you want to view it like that. So that's sort of like, just a really nice way to think about it.
pal.k: And so one result of that is that if you have high edge probabilities between pairs of nodes, then they're going to be closer together in this latent space, because the cosine of their angle is their angle is higher, and so the cosine of their angle is, they have a smaller angle with each other. Right? So that's sort of like a really nice property of viewing things in this way.
pal.k: So just to recap we
pal.k: want to understand things about networks. We want to understand things about the way that the probability distribution of networks works, the way that the distribution they're sampled from
pal.k: works. In order to do that, we've defined a probability matrix p. Such that every the Ij entry of P is the probability between pairs of nodes. And then we said, the way that we want to define P is by giving each node a vector and saying that the dot product between vectors defines edge probabilities. Right?
pal.k: So
pal.k: the big problem here is that if I have a real network, I don't know how to estimate this X thing right? Like, I'm given an adjacency matrix 1st of all, not a probability matrix. And I want to figure out where in the embedding space these nodes live with just this adjacency matrix. And so what do I do?
pal.k: And so so it turns out that that you can do eigen decompositions, and you can estimate you can estimate the this latent space matrix. And so ignoring the adjacency matrix. Let's stay on the probability matrix for a second.
pal.k: Let's say we take the eigendecomposition of the probability matrix, right? So so that's Q. Lambda. Q transpose where lambda is just a diagonal matrix of eigenvalues right? And Q has columns that are the Eigenvectors of the matrix. So for anyone who's like, you know, not, you know, linear algebra was like a long time ago, or whatever. This really nice property of symmetric matrices.
pal.k: which, remember, is what P. Is, because we're in the undirected situation. A nice property of symmetric matrices is that if you take their eigendecomposition, all of the Eigenvectors are orthogonal to each other. And so that means that the matrix of Eigenvectors is just a rotation matrix right? And so you can take P. You can rotate it into the and it turns into a matrix of Eigenvectors.
pal.k: Another thing that you can do, because lambda is a diagonal matrix
pal.k: is, you can break it up
pal.k: into square roots, so you can say lambda is lambda to the one half times, lambda to the one half right. There's, you know, a few other light assumptions that you have to make about P here to make this fully defined. But they're very light. And that's okay. And then what we can do is we can just say, Hey, I can use this property of of matrix multiplication. And if I take the transpose
pal.k: of this thing. Then. Well, this thing is just equal to to this thing. Right?
pal.k: they're the same. They're the same object. And so if I just move this, transpose to the outside here and then flip them, which is just a basic property of matrices. Then you have this Q. Lambda to the one half times. Q. Lambda to the one half.
pal.k: Look, these things are the same value inside. Let's just call that x right. And so I have this nice Xx transpose here. And so now, I've taken the Eigendecomposition and used it to find this embedding matrix that we cared about? Yeah, Sheridan. So didn't you say that we just have the adjacency? Or where did we get the probability? Yeah. So I'm getting to that. Yeah. Yeah. So so we're just like hallucinating that we had the probability matrix right now.
pal.k: And so because we're like, How do we get? X? Well, okay, if I had the probability matrix. This is how I would do it. And then we're going to get into well, I don't have the probability matrix. But you know, what can we do anyway? But this is how we would get X if we had the probability matrix right?
pal.k: and so the problem that Sheridan just brought up is that we don't actually have the probability matrix. We only have the adjacency matrix. And so what do we do?
pal.k: Well, you can still take decompositions so you can. You know, A is still symmetric. It still has this orthogonal set of eigenvectors. And it turns out there's some other nice properties of matrix. That shows that if you that says that if you have a symmetric matrix
pal.k: and you decompose it, the set of singular vectors and singular values are almost the same as the set of Eigenvectors and Eigenvalues, except that you have this nice property of the singular value decomposition that everything is positive. So you have all positive eigenvalues. You have all positive
pal.k: you know everything is positive. And so you've sort of constrained your space so that so that it's nice in the way that we want, which is, you're not going to accidentally get negative probabilities. You're not going to. Actually, you're not going to have like. You know, negative
pal.k: eigenvalues, because the singular values are always positive they're the absolute value of the eigenvalues. And so we're going to switch to using the singular value decomposition, which is basically the same. The Eigenvectors are exactly the same, except there's just some flips of signs in various situations, and so
pal.k: what you can do now
pal.k: is you can take a and you can just say A is actually an estimate of the probability distribution, right? Like we said before that in the limit A was equal to the probability distribution. And so it turns out that you can actually always view it as being an estimate of the probability distribution, an estimate of the probability matrix.
pal.k: And there's a bunch of like statisticians who approved a bunch of limit theorems and a bunch of like, you know, as as you increase the number of nodes, how close you are of an estimate to P increases. And so there's all this theory around this that shows that you can do this. And so we're just going to take a we're just going to take its singular value decomposition. And then we're going to just say,
pal.k: we're gonna say that our estimate of X is this,
pal.k: left singular vector, times, the square root of its singular values. And, by the way, we're gonna because we don't think that X is actually in a space that's equal to the number of nodes. Once we do that, we can just chop off the last few columns as many columns as we want, and say that it lives in a d dimensional space.
pal.k: That was kind of a lot. But does anyone have questions? Yeah, as practical example, the problem that you try to solve here is, you want to find some general properties of the brain, some probability distribution of how the neurons are connected. But you only have one sample, which is a yeah. And now you want to generalize this one sample
pal.k: to a
pal.k: yeah. So it's it's not quite that. The real thing that we care about turns out to actually be x, because if you look at
pal.k: If you look at like. Here's an example of the nodes all plotted when you look at the nodes, and I'll show you why it's useful to just try to find X directly, but when you I mean it has all the same usefulness as having embeddings does. There's a reason that we turn sentences into embeddings, and we try to find embeddings for everything right. Finding X is sort of the you do it for the same reasons. Right? You can find community structures. You can run
pal.k: all these traditional algorithms on them. You can just do a lot more with objects that live in Euclidean space than you can with objects that live in like graph valued space. So that's the real point is where we actually care about finding this thing so that so that we can do downstream stuff. Yeah, yeah, you're finding X based on just one draw of a right? Yeah, like, how costly is to just take multiple draws of a
pal.k: well, you don't have the probability matrix. If you if you draw multiple draws of a, then you have the probability matrix right? But
pal.k: it. Well, it depends on the setting right. If a is found by painstakingly going through, you know a fly brain and and getting every single neuron over the course of 5 years. Then it's a lot harder to draw multiple A's. But if A is like.
pal.k: you know, an attention head that you've symmetrized, then it's pretty easy, so you only need to do this analysis. If drawing A is super costly.
pal.k: right? Otherwise you just draw like 10,000 days, and then you have the probability matrix. And then you have the X,
pal.k: yeah. But you would. You would do this. Yeah. But you would do the same thing either way right? Because with the probability matrix under the assumptions that I'm making, the assumption I'm making is called you're assuming that the probability matrix is a positive semidefinite matrix, meaning that all the Eigenvalues are positive. So if you under that assumption, the Svd is the same thing as the eigenvalue decomposition. So you do the same thing either way.
pal.k: You would always just find its singular vectors if you only have one. A. There are like certain values like you have either ones or zeros in emergency. Right? Yeah, yeah. So literally, 2 nodes. If they have, if they have an edge, they're literally the same because their top product is one?
pal.k: No, because
pal.k: wait. Sorry. What do you mean? 2 nodes are the same. If they because you have to look at the whole, you have to look at all of the net, the nodes that okay, okay, right? So like one, node isn't just connected to one other node. It's connected to like, however, many others. Yes.
pal.k: if you had 2 isolated nodes, then they would have the exact same latent position.
pal.k: And and it turns out that you know, if if you have, you know this, this community structure that I talked about before. If 2 nodes are are pulled from the same community. Then, if you had the probability matrix, their latent positions would be the same. In that case, right? Because all of the edge relationships between them and other nodes. All have the same probabilities.
pal.k: Does that make sense? Yeah.
pal.k: Yeah. And and so, you're not actually in the like. I only have one sample situation that you would imagine that you are, because it take turns out that if you increase the number of nodes in your adjacency matrices, you get better estimations. So so so it's like, yes, the adjacency matrix is just one object. But if you have a bunch of nodes, then, you're in, you're in better shape. So
pal.k: yeah. So I've got nerdy technical questions. Yeah, can you go back to your Svd, yeah. So so there's, I guess I have 2 questions. So one's conceptual and the other's technical. So the one isn't. We'll go to the next one
pal.k: which one, this one? Which one? Yeah, yeah, sure. So, okay, so one of them is, what happened to the V
pal.k: cause. That's just a technical question, yeah, and then and then and then the more conceptual question is.
pal.k: so if you have, if you have this embedding does it? Does it totally capture the original? A like you? Can you recover the A from it? Or have you lost something? And then and then or another another way of looking at it is.
pal.k: You know you have this nice embedding.
pal.k: like, you know. If if you
pal.k: I think David's in this situation right, if you have 2 different.
pal.k: You know, networks where you might have shuffled the nodes.
pal.k: Yeah, I'm going to do that. I have a method for helping that. But the X thing, it would happen to the B. So remember that A is always going to be symmetric. And so you're always going to have orthogonal singular vectors and orthogonal singular values, and the only difference between the spd of a and the eigenvalue. Decomposition of A is the signs on the singular values. So the V is the same as the U. Except for some signs. Exactly. Yeah. So we could do the same thing with B instead of U,
pal.k: I see. But and but then does it is, is XX transpose equal to a
pal.k: or is it Xx transpose is equal to a but but you see, what we're doing here is we're saying
pal.k: So we let u Epsilon be u sigma v transpose be the left. Singular vectors, the singular values and the right singular vectors. And so we're going to say, Ud isn't the original U, but it's the matrix whose rows are the 1st d left. Singular vectors and the diagonal matrix whose entries are the 1st d singular values. So so we're deleting some of the singular vectors
pal.k: right the same way you would in Pca. And so you can't fully reconstruct. But if you delete the singular vectors corresponding to the lowest singular values, you lose provably as little information by mean squared error, loss as you can possibly lose, I see. But if you set d equals to N, then you can, then you can totally recover it. Yeah, I see. Okay, yeah.
pal.k: Yup, and then wait. What was your second question again? That's it. Okay, great. Oh, I have a question. Yeah. So
pal.k: in an essence, you're trying to find a X
pal.k: that's basically estimate. X, yeah, yeah, the estimated X is.
pal.k: you're trying to form a basis directions that would
pal.k: map all your connections, such that
pal.k: anywhere you have a connection, they're all
pal.k: cluster together, aligned in the same direction, and the nodes that are not aligned should be perpendicular to each other.
pal.k: Yes, yeah. Yeah.
pal.k: What's the motivation for that? Why, why are you going for that? Like, I think this is this all started when you said, I want my probability to be an inner product of my ex.
pal.k: Why? Why? Why that motivation?
pal.k: The motivation, is actually the reverse of that. So the motivation is. Actually, I want to turn my network into vectors in Euclidean space.
pal.k: So so that's the real motivation. And it turns out that that that
pal.k: going in the direction of starting from your X and defining an inner product space on it to be the probability matrix.
pal.k: It turns out to be the way to go in reverse and start with an adjacency matrix and get an estimate of X, and because it turns out that the estimate of X is just really useful, and if it's in and of itself to for a lot of downstream applications, because now you've gone from a network that's really hard to deal with. And you have all these dependencies between nodes, and you have like, no one really knows how to like. You know, there's some weird like, you know, you can like, do algorithms that involve like
pal.k: walking along the graph and other stuff. But like it's
pal.k: it's like, you're you're very limited. Whereas if you take the whole thing, and you just
pal.k: put it into Euclidean space and and you have, like some strong theoretical reason to do so. Then there's all these things that you can do with nodes that live in Euclidean space.
pal.k: So so that's your motivation, is you? You actually just want to get X.
pal.k: So it's like, you want a semantic structure of your leads. Yeah, yeah.
pal.k: right? Yeah, yeah, you're trying to find node structure. And I'll I'll give a bunch of examples in the second half of the presentation for for
pal.k: why this is useful to do?
pal.k: Yeah? Oh, oh, sorry! And the size of your embedding will be the number of nodes
pal.k: the number of of rows in the embedding. Yeah, so d oh, d no, no! So so if you were to set d equal to N, then the embedding would just be a square matrix. But in practice what you do is the same as you do in Pca, where you, where you pick some number of low, singular vectors to just delete, because you don't care about them, because they don't give you any information. But D is the size of your embedding. D is the size of your embedding. Yeah, okay.
pal.k: yeah. And you you pick D, there's methods to pick. D right? So you can look at the screen plot right? Of of singular values, and you can look at the elbow point where it drops off a lot. But but yeah, DD is the size of your embedding?
pal.k: Yeah. Yeah. So for the embedding. So you I I kind of forgot what? What like. So if they have an inner product of, or like a dot product of one versus 0,
pal.k: what's like an in-between value. So does 0 mean, they're like, not connected. 0 means there's a 0% probability of there being an edge between those 2 nodes. So if the so, if in your inner product space, or sorry if in your embedding space, then the the 2 nodes.
pal.k: You know. So think of them as points in Euclidean space. Now, if in your embedding space the new 2 nodes are fully orthogonal to each other, then that means that they have an edge probability of 0, and if the 2 nodes are exactly on top of each other, then that means that they have an edge probability of one. And so they're guaranteed to have an edge with each other right? And so, as they rotate away from each other in Euclidean space, their edge probability drops until you hit Orthogonality.
pal.k: Does that make sense? Yeah, yeah, how much does magnitude matter in that space? I guess if we go to high dimensions and cosine similarity? Like.
pal.k: yeah. So I mean, it's you're you're always using the dot product right? So so you're always using
pal.k: right? You know, you're always taking the magnitude of the 1st times, the magnitude of the second times, the cosine of their angle. There's there's
pal.k: people who study the what this space has to look like to guarantee that the dot product is one. It's called the probability Simplex. And you get to a pretty limited space as you increase the number of dimensions. But yeah, you, you basically just define it so that so that vectors can only live in the space where they're guaranteed to have
pal.k: an inner product with each other between 0 and one. So in the general case, you don't constrain yourself to like only the unit sphere. What do you mean by the general case
pal.k: like the like, your algorithm doesn't output X's that are on a unit sphere. Oh, yeah, that's true. Yeah. But but there's there's
pal.k: There's
pal.k: because of all of the
pal.k: because of the theory that shows that as you increase the number of nodes of an adjacency matrix, it gets closer to the probability matrix. You actually, they get, they get closer and closer to that. So so they get closer to the probability simplex. As you increase the number of nodes. It turns out so. So so you end up being fine, and it also turns out that if you like, loosen that restriction a little bit right, and they're like a bit off the probability. Simplex. It's fine like you can still
pal.k: do a bunch of useful stuff with X like it's fine, so you know.
pal.k: you could be anal about it, or you could just say we have a good way to get embeddings right?
pal.k: So.
pal.k: Alex, last question, yeah, is that.
pal.k: can you go back to your envelope? Yeah.
pal.k: it seems like the
pal.k: Your X approximate is perpendicular.
pal.k: There. It's an orthogonal matrix. Right? They're all orthogonal to each other.
pal.k: That's what you're saying. The columns are the ex. Exactly. So does that mean
pal.k: you've mapped all your points into record space.
pal.k: You've mapped the.
pal.k: You've mapped the axes into an orthogonal space, so the axes of the space are orthogonal, but the points themselves are the rows
pal.k: and the rows aren't, aren't, aren't orthogonal.
pal.k: They're not. The rows aren't guaranteed to be orthogonal, only the columns
pal.k: so u 1 and u 2 should be perpendicular to each other right in the the left.
pal.k: Svd matrix.
pal.k: the columns yeah. u, 1 and U, 2 are perpendicularly to it to each other. Yeah, yeah, all the columns are associated.
pal.k: But the embeddings are the rows. Yeah, the embeddings are the rows.
pal.k: Make sense
pal.k: cool. Okay?
pal.k: oof, yeah. Okay, wow, wow, yeah, okay, I have like way, more presentation. I've I'm only in like the 1st 3.rd But it's it's 1050. So so we're gonna skip to some applications
pal.k: but okay. So one application is uncovering a human trafficking network. Right? So let's imagine that. Actually, that's that's cheating. You guys are, gonna see what happens. So let's imagine that you have a bunch of web pages.
pal.k: And those web pages are advertisements and and in each of those advertisements there's like a like a phone number. And there's like, you know, like an address.
pal.k: And then there's some other stuff, right. But you you have some way to define like connection between web pages, and you know that some of the web pages are human traffickers, and you're the police, and you want to find all the other human traffickers. So
pal.k: what do you do? One thing that you can do is
pal.k: you can set up your adjacency matrix the way that I just described do your Svd. The way that I just described and then you can say for my human trafficker. Nodes.
pal.k: I'm going to take their locations and average all the locations. And so then this star is the average human trafficker location in my embedding space, and so to find other human traffickers. I'm going to look for other notes, other web pages that are close to this little star, and I'm going to find their nearest neighbors, and then the ones that are closest to the star. Those ones are the most suspicious. So I'm going to go investigate those people because
pal.k: I want to find more human traffickers. And so you can run like K-means or Gaussian mixture model to find communities right? And so you know you could find human traffickers in this way, if you have features for each node. The situation I talked about before.
pal.k: So say we're in a situation where? We have a network. Right? It's this. We have Wikipedia pages, and we have a have a graph of
pal.k: computer science and statistics. Wikipedia pages, and there's an edge between them if they link to each other and let's just ignore directedness like normal. So you have an undirected network. But there's this problem, which is that there's a few computer science pages and a few statistics pages that are really really highly connected with everything.
pal.k: And so you have this core periphery structure where you have, like a few web pages, a few Wikipedia pages that are like
pal.k: not that high edge weights with anything, and a few that are like really dense. And what you want to do is you want to. You want 4 communities. You want the dense and not dense community. And then you want the computer science and statistics community. And so you have these covariates. Right? So for each web for each Wikipedia page, you also have whether it's a statistics or a computer science page.
pal.k: And so what you can do is you can just take its adjacency matrix and take these covariants. Take the Yy transpose of these covariants scale that in practice you actually turn a into this other structure called the Laplacian. It's just a function of the adjacency matrix
pal.k: and and then they look like this. You can take their weighted sum. And then, as you change the weight, you see here, you only have the core periphery structure. Here you only have the computer science versus statistics, but as you increase the edge weight you can find a weight that divides them into 4 groups. So you know. So that's sort of like. And then you can classify. And and that's sort of like a nice thing. There's ways to automatically find the edge weight.
pal.k: So there's other methods. So if I have a lot of different networks, then
pal.k: what I would like is to put them all into the same space, because I want to be able to directly compare all of their notes, and so
pal.k: The the reason why you can't just take them all and and do this adjacency matrix thing separately, and then just compare it like that is that you run into this problem of rotation. So if you have a bunch of points
pal.k: and you rotate them all, and then you take the inner product of those points, then it's the same. So if I have these 2 points and and they have some dot product, and then I rotate the 2 points. Their dot product is is invariant to that rotation.
pal.k: And so that means that there's actually a lot of different X's that can make a single probability matrix because you can rotate. And so you can show this algebraically by just sticking an identity matrix inside here, expanding it into 2 orthogonal matrices. Doing that transpose trick that I did before. And look, it's like a totally new set of 2 matrices. So this is called rotational invariance.
pal.k: And so one way that you can fix that
pal.k: is, you can take each network and put them as block diagonals into this big matrix, and then you can on the odd diagonals. You put their averages. And so there's a bunch of theory that was built around. What happens if you do this, and it turns out that if you do this, you get a bunch of stacked latent positions
pal.k: right in this Svd of this big block matrix that you've made. And if you just take a bunch of rows out. Then. Now you have a bunch of embeddings that are all rotationally on top of each other. So you have this sort of like nice. You can compare them directly now. So another thing that you can do if you have multiple networks is, you can say, Hey, I have this central latent structure. But I still want to preserve some distance some differences between
pal.k: between networks, right? Like they're different in some fundamental way, but they they have this common shared structure, and the same number of nodes and whatever. And so for that, you can say, instead of my probability, matrix being Xx transpose, you can say, my probability, matrix is going to define be defined by Ss, transpose
pal.k: this single shared matrix that's shared between all of them. But each network is going to get its own little matrix R, that defines how it's different from all the other matrix. So you have this shared structure. But then you also have some. It's called a score matrix that makes each network different from each other network.
pal.k: And you can define P like this. And I'm going to. This is some intuition, but I'm going to skip it, and you can estimate this by taking a bunch of adjacency matrices running Svd on them.
pal.k: Concatenating all of those, and then running Svd again, and and then what you get is
pal.k: an estimate of this
pal.k: of this
pal.k: you get an estimate of this of this
pal.k: s, and then you can find R, and you have your estimate of of P, and you can find R by by by just doing some some simple algebra on it for each, for each network.
pal.k: So yeah, so there are ways to deal with multiple networks. You can also, if you have rotations, there's this classic algorithm called the orthogonal procrustige that just takes 2 embeddings. And this is just true in general, you can take 2 embeddings, and then you can run this minimization where you find the rotation matrix that best
pal.k: puts them on top of each other. Right? So the you find the the best rotation matrix. And so there's this iterative method to to find this
pal.k: and so the situation you just you mentioned is so so a lot of the time. If I have multiple adjacency matrices, if I have the same set of nodes on each adjacency matrix. The indices that you give each node is like completely arbitrary a lot of the time.
pal.k: And so what will happen is, you have like 2 networks, but you don't know the correspondence between the nodes, because the index that you came up with is like arbitrary, and you've like measured them, and you don't know which nodes connect, which nodes correspond to which other nodes. So this is a very classic problem. It's called graph matching. Right? So if I take this adjacency matrix and I scramble it. I just scramble the indices. Then.
pal.k: you know, it still has this community structure, and it turns out, if you take the Svd. And you, you estimate this X, you would still find the community structure in this one. So that's really important. It's another reason why, why, it's useful to do this Svd thing. But just looking at the adjacency matrix, you get like nothing out of this. And so this is a classic problem called graph matching.
pal.k: It works by getting estimations of these permutation matrices, permutation matrix just shuffles around rows and columns, so you can shuffle around both the rows and the columns with this. So this is a symmetry transformation. It preserves eigenvalues, but just moves everything into a new basis. So this is just permuting the adjacency matrix.
pal.k: And so you can set up this minimization problem where you say, I have this adjacency matrix. I have this other adjacency matrix. I want to find the permutation matrix that best maps the 2 matrices onto each other. And the restriction is the P is a permutation matrix. And so there's this
pal.k: method called fast quadratic approximation, that does this in this iterative way, and I won't get into the details because it's a bit complicated. But there's nice functions set up to do that.
pal.k: And then, you know, another example. Situation is
pal.k: Say, I have 2 networks, and what I want to say, the only thing that's different about these 2 networks. They have different probability matrices, but those probability matrices are almost the same. But there's some subgraph in the probability matrix, and that subgraph is the only place that defines the differences. So most of the edge connections are drawn from the same distribution. But there's the subgraph. That's a different distribution.
pal.k: And so that's called a signal sub network. And so there's ways to estimate what that signal subnetwork is. I'm using hypothesis, testing methods. And
pal.k: yeah. So there's there's an easy way with you. Have a bunch of networks. You can do a hypothesis test on each edge. Because you have a lot of them, you get P values. And then you rank the p-values. The problem with that is that you're not actually using the structure of the adjacency matrix. And so you can do this sort of iterative thing where you find the p-values.
pal.k: you delete the the nodes that connect to edges with low P values, and then you run the thing again. And now you're you're you're finding signal nodes, and you're only running the thing on signal nodes. And so now you're taking advantage of graph structure. And so there's an algorithm to do that. And there's a lot of other stuff.
pal.k: That we cover. So you know, we have an end to end project in the second chapter. There's all kinds of properties that nodes can have right their degree, which is the number of connections with other nodes, summary statistics on networks.
pal.k: preprocessing techniques. You can do a lot of other statistical models that I didn't talk about. What the Laplacian matrix that I mentioned is, and why it would be useful to use that sometimes, instead of the adjacency matrix sparsity properties. This is a situation where, if you get an embedding.
pal.k: it's pretty computationally intense to do Svd a single time. So you might not want to do that. If you have just one new node that you want to add to your graph, so you can estimate where that node should be in the embedding space.
pal.k: and yeah, if you have like a bunch of networks and you find want to find an anomalous one, you can use hypothesis testing methods to do that. And then we have a chapter on graph neural networks and on random walk methods.
pal.k: yeah. So
pal.k: yeah, I kind of had to speed up a little bit there at the end. But that's okay. And
pal.k: yeah. So that's kind of like, I think the finding finding finding a some. Some estimate of X is like kind of one of the core ideas. And then there's like a lot of theory built around like stuff that you could do once you've done that
pal.k: And
pal.k: yeah. So
pal.k: yeah, anyone have any any questions.
pal.k: Okay, cool. Yeah. So the other thing that David mentioned is I should probably bring up since I have everybody in the room.
pal.k: we break. David and I have been brainstorming. You know, project ideas. And so you know, he brought up that I should probably talk about project ideas. I didn't want to bring bring up like, you know what the potential ideas are for projects, because it's pretty half baked and like, I haven't actually, you know, done much yet. But but yeah, I mean, so the idea right now is is to kind of build off of
pal.k: these. This idea of influence functions. So you, you have you know. You want some method that that
pal.k: tells you how how much influence a single training data point has on on the output of like some language model and and so we've sort of been investigating that. there's this paper that
pal.k: that shen you at Carnegie Mellon came out with that can do this with
pal.k: that uses like this. This unlearning, based based method to to, you know, kind of get at this problem from another way. But that's sort of like what we're starting on. And so yeah, I don't really know what to what to say about it. So you know. So this is so I yeah, I love people's feedback on on this. So you'll be because you know Alex and I have been brainstorming about this project one on one.
pal.k: And and you know, you guys
pal.k: generally know what each other are doing in research. But nobody knows what Alex is doing yet, because it's just started 1st year welcome. And so
pal.k: yeah, so so there's a there's sort of a little bit of a blind spot in our in our research in the in this area. And it seemed like something that Alex, potentially interested in
pal.k: which is, you know, just this training data attribution
pal.k: problem. And it's this, it's this Holy Grail
pal.k: of machine learning because it's really not well solved.
pal.k: There's only been a few papers that have really taken it on seriously.
pal.k: And
pal.k: it! Which is is just generally the question of
pal.k: you have some output behavior of your network.
pal.k: You know. What? What did it come from? You know what? What training data
pal.k: explains this behavior. The most people some people have noticed that.
pal.k: You know, large language models will memorize their output. They'll regurgitate
pal.k: articles from the New York Times, and it seems obvious that oh, well, I must have learned it from reading that article in New York Times.
pal.k: but but you know often
pal.k: you'll have a network. Do something clever.
pal.k: and you wonder.
pal.k: you know, where did it learn that clever thing from
pal.k: and
pal.k: And so, you know, some people are worried about this for copyright reasons and things like this. But you know, so there's a there's like sort of 2 or 3
pal.k: questions. Well, we came up with this problem setting
pal.k: which I don't know if you guys think is compelling or not. Do you want to explain the possible problem setting? Yeah. So so we were thinking of looking at like Code Llms, and so you know. So we were. We were thinking, you know. Say, you you know, have an Llm generate some code and you know, and it it has a bug, and you get some attribute error. And so you know one thing that you would kind of like
pal.k: is to explain. You know why, in the, if you could go back to the training data and figure out why you know why this bug is happening right another. You know, potentially useful thing that you could do is
pal.k: is like, you know, you. You generate some code. It it you know it has some error, or whatever. And then you you can go into the documentation that is most similar to the code that it wrote. And so then you can just immediately go into documentation from wherever you are. And it's documentation that it was in was in its training data. So then, you have this sort of like extra
pal.k: layer of information on top that lets you kind of understand what's going on so I'm I'm sort of into this into this setting, because it's
pal.k: you know, there's this theme of like human learning.
pal.k: right? You know, like the models are doing things that people
pal.k: are learning from.
pal.k: And the Code Llms is like sort of sort of one of these settings, like where people are like
pal.k: using the coded Llms to try to navigate technical
pal.k: abilities that they're trying to learn
pal.k: from the things like they might be trying to learn a new programming language, or something like that.
pal.k: and
pal.k: and so they're always faced with the situation of like, well, it did this clever thing. I don't know if I should believe it or not.
pal.k: you know. Is there something else I can read about it?
pal.k: It's like the citation problem, right? It's like, Oh, you know. Maybe
pal.k: you'd like to know where it is that the code Llm got this idea that it's trying to
pal.k: tell you to do, and you can go read the original sources and and get some some more context.
pal.k: you know, maybe as a way of connecting to the original human beings
pal.k: that gave the Llm. The idea. In the 1st place, right?
pal.k: And so I I kind of. So this is the setting that we've
pal.k: we. We're brainstorming. I think that, like, maybe Code Llms is where one of the situations where it comes up cleanest. I don't know if anybody else has a setting
pal.k: where where data attribution.
pal.k: you know, might work really? Well, yeah, does this sound like modeling version that acts in computer vision
pal.k: model inversion, correct?
pal.k: Oh, model inversion attack? Oh, like model, yeah, or or or mia like, or also known as membership inference attack.
pal.k: Yes.
pal.k: yes. So this is this is a more general. You could argue harder, maybe easier problem.
pal.k: membership inference attack
pal.k: is asking the question.
pal.k: You know, can I tell
pal.k: if a particular piece of training data was present in training
pal.k: or not
pal.k: so like, that's that's it's usually the obsession of privacy people
pal.k: right like, Oh.
pal.k: I wanna know if my private data was in there. You know, I have this secret piece of
pal.k: medical record history that I don't want anybody to know my medical secret, and I want to know. I want to go back to this medical birth that they just released on the Internet and see if they trained on my secret data that I don't want them to know
pal.k: And so that's so. That's is is right closely related.
pal.k: But this is different. This is more like, hey? The model said something.
pal.k: Maybe I know what all the training data was. Maybe the training data is public. Maybe it's like all the code in the world or something. Maybe all the code in Github. But I want to know, like, where the model got this idea that.
pal.k: you know, does that make sense
pal.k: so? Code Llms does not learn to quote by looking at the documentations it learns to code. By looking at the codes. Right?
pal.k: So how much about this?
pal.k: I mean codes like code contains a lot of comments and things like that. So
pal.k: one question is, what if there does not exist documentation that relates to the particular code? What would your
pal.k: project spit out in that instance? Would it just be like a 404? Would it try to generate documentation, or Oh, well, you would want, like a ranking of what the most similar training. Okay? So so in that case, if there's no exact, you know, I mean, there might not be exact documentation. But there might be code that was written that's pulled from Github. That's like really similar to the code that it wrote. Yeah. So then it might pop out that. And then
pal.k: one.
pal.k: I don't know if this is
pal.k: yeah. I'm fairly naive to this, but I guess another setting I can. Envision is in reinforcement learning like, why did the car turn left? Or like, is there any sort of training data or video? That sort of explains an agent's actions?
pal.k: Basically.
pal.k: yeah, maybe maybe like, reinforcement learning could be an interesting
pal.k: setting. You could add, and why? Why, yeah, that's another area. That's pretty interesting.
pal.k: Yeah. I mean, I don't know what all the self driving companies are doing now under the hood. I don't know if they're still doing a lot of reinforcement learning, or if everything is just transformers now, and the tokens that the things that they're trying to predict are like actions based on claims or something. I gave self-driving cars as an example. But from my understanding, or, like the FDA, is sort of looking into AI as a potential area for pharmaceutical innovation. And
pal.k: if we're going to train models on like how a drug is manufactured like we have to be able to understand why
pal.k: the a model sort of made the decision to stir faster like a beaker or or something
pal.k: to make sure that it doesn't have an impact on product quality. So I was thinking more from the manufacturing side of things, but like self driving is sort of more. That's right. I think that you know the one of the motivations for the project is, you know, our theme is explainability, right? Interpretability of AI, a lot of the like. A very, very common question. When people ask you, why did the AI do this.
pal.k: They sort of want to know. What was it in the training data that made it do this right? This is like one of the forms that people. And and the answer up to now that machine learning has presented is, we don't know why, or you can run influence functions, but it would take 700 years for you to compute the
pal.k: the Hessians, or something like that. And then you still, you're not really sure if it's very good right? Now, yeah.
pal.k: one natural setting. Whether this arises just
pal.k: official or judge decisions. Yeah, because they often refer to precedent, maybe legal texts, right? Legal text. And they often refer to the previous decisions. Right? Yeah, yeah, because because you have like a really strong goal there, like, you want the court decisions to refer to like if it comes up with a court decision, you want it to refer to all of the relevant cases.
pal.k: Yeah. Yeah. And oftentimes a court decision just says, Oh, we're we're very exactly to the same thing. 10 years ago, and
pal.k: 10 years ago they made that decision. That's why, like the AI Court decisions are not so relevant because they will be the 1st ones that will inform future decisions. Yeah, yeah, it's very interesting. Yeah, legal tax might be a good side.
pal.k: So yeah, I mean, 1 1 thing that David and I were were thinking about is that you know, if this ended up looking like some vector, search thing right? Where you have like a vector, data database. And then you have some method to to figure out the most influential vectors. Given the text that you just spit out. There's a bunch of companies all working on like vector databases and like retrieval. And that kind of thing. So there's a lot of infrastructure being built up for it right now. So
pal.k: you know. So that's sort of a nice to have kind of thing right?
pal.k: Yeah, if you like, I want to build up on the legal thing. There were like workshops on in the same about the legal evaluation thing. There were like tasks about it that they like give the public data. And there were one of the tasks was actually to
pal.k: give give the reasons on why the
pal.k: why they made the explanation. So there's like already, like some build up code on that workshop. So
pal.k: that might be useful. Cool? Cool. Okay, yeah.
pal.k: So that I don't think I have like a suggestion on
pal.k: a setup. Something which I'd be careful about your designing this
pal.k: of.
pal.k: Like most of the data attribution methods right now, at least in equation models
pal.k: would give some sort of a function, or like a score saying, this could be the reason why like this. This is the training sample
pal.k: which influence my output right.
pal.k: But if you use the same function
pal.k: on an on an image which was not in the training data set, but which is very closely related to the output, it will still give like a very high attribution to it. Yeah, right? So
pal.k: like, my question is, would that
pal.k: is that really attributing
pal.k: training sample? Or is it really looking at like similarity sports? Yeah.
pal.k: yeah, I mean, that's a good. That's a good question, because because then
pal.k: I mean, it's very easy for it to just collapse into a similarity metric which there's already a lot of. Yeah. So probably I'd put more thought in, yeah, like, how do I separate those 2 things? Yeah, yeah, that's a good point. Yeah.
pal.k: yeah.
pal.k: no, you you. But now you've you've read Chinese work. Right? Yeah. So like they're they're they're.
pal.k: you know, sort of where they've landed
pal.k: is if this is
pal.k: this is like the practical
pal.k: framing. Right? So like, you know, they're trying to predict
pal.k: the ground truth of how much training influence you have. But in a practical way.
pal.k: yeah, I mean. So that's how I mean, you know, that's how they're measuring their
pal.k: right, their accuracy. Yeah. So I'm I. I don't think
pal.k: you don't totally believe it. Yeah, I don't think I'm convinced that it's training attribution. I think
pal.k: you think it's just another type of similarity.
pal.k: Yeah, it physically is which it is. Yeah. I guess, like I I would wait for that one more experiment that says.
pal.k: Oh, it is actually connected to the training
pal.k: know
pal.k: which is currently like, I think the reason it's not there is, because I think it's still hard to
pal.k: make it a practical design like experiment on how you would test that. It's just expensive. Yeah, it is very expensive. You need to train a model. Yeah. And I, I'm not sure if what we have right now is the multi approximation for finding the training influence
pal.k: in compared to like, is it just a similarity?
pal.k: Right?
pal.k: Right? Yeah, that's interesting.
pal.k: Yeah.
pal.k: You know, there's a there. So there's a what do you think of?
pal.k: since you're you know you're branching is what? What do you think of the the feasibility
pal.k: of this? Even as a goal.
pal.k: right as a goal like like, is it? Is it feasible to really deconvolve the embedding and see? Yeah, to, to say, to say, you know, to to actually answer the question.
pal.k: You know, this was this was the most influential
pal.k: training data in the entire data set.
pal.k: You know, you trained, you trained Gpt for for 6 months
pal.k: on all the world's information.
pal.k: and you've compressed it down to.
pal.k: you know, a tiny fraction of the amount of data
pal.k: that you consumed in this, even after suppresses, you know, a terabyte of weights.
pal.k: And and then now now it did something surprising it. It output some piece of
pal.k: poetry
pal.k: in in a weird style, and I want to know where it got this idea.
pal.k: Do you think that it's even feasible
pal.k: to
pal.k: to identify
pal.k: accurately.
pal.k: I mean. So let's the so like doing the doing the test
pal.k: of is it correct?
pal.k: Isn't really possible to test right? Because
pal.k: at least at large scale.
pal.k: right? Because you know it would
pal.k: you? You've got to re rerun your training about 10 times that would cost about a trillion dollars or something, you know, it's like, you know, nobody's gonna do that right?
pal.k: And so.
pal.k: yeah, so does that mean, this is outside of what we can do scientifically.
pal.k: But I haven't thought about data attribution as much. But my current opinion is, yeah, maybe not. Maybe it's outside.
pal.k: But maybe you don't have to be as precise. Maybe it's fine enough to like. Have a set of like 2 or 3 papers that that were the most relevant, or you have, like
pal.k: a direct comparison metric of saying, Okay, this legal text was more important than this legal text when doing the final decision
pal.k: right, you know, like, my opinion is that
pal.k: you know, we're sort of in the same situation as like economists are when they're trying to give advice, right? You know, like, Oh, we can't like rerun the entire economy. But we're trying to give advice about counterfactual situations of what would happen if you raise taxes like this? Right? And so, you know, we can. We can come up with our models that we can validate
pal.k: on smaller settings. We can retrain and test.
pal.k: you know, true data attribution on smaller settings where we can do the training, and then and then we just have to extrapolate and say, Well.
pal.k: you know, our best guess is, if these methods continue to work on the large settings.
pal.k: right events, type of events, you know.
pal.k: And then we just have to
pal.k: present, you know, like, when we get there, we'll have to present it with the right caveats. I think, like some of the current data, attribution methods test that they do it on a small setup. They retrain and check how the scores are turned out. Yes,
pal.k: The my only
pal.k: point on that is that I don't think we are really disentangling
pal.k: what is like what has been learned versus what? How similar
pal.k: that is. Like, how similar is the output to that current example.
pal.k: You you! But you don't think that naturally those are
pal.k: like
pal.k: like one would.
pal.k: There's a relationship between those 2 things right?
pal.k: Like like what what you learned is probably to copy the sample.
pal.k: And so if the output is similar to the sample, then it's probably
pal.k: most similar to the things that right or that's probably most likely that's the case. But, like, how would we disprove basically that it actually is spitting out a relevance or an attribution? How would we basically go about proving? No, this is actually incorrect, and this is not an attribution.
pal.k: Well, so you can only do this in some of the controlled settings, right where you have a small
pal.k: a network that you can retrain without that training data. And then if you do it and you pull the training data out. And it didn't actually influence.
pal.k: You know the output as much as you thought it would. Then then your then you know your method is wrong. Yeah, okay, right?
pal.k: Like a canary injection. Maybe with that training data as well.
pal.k: How does a canary injection work like you? I don't know. Let's say, add some like special token or something with that data, and just see whether, like.
pal.k: if, for instance.
pal.k: that particular data point like
pal.k: is what was used. Yeah, like, you put in something really weird, like a hash code like a big hash code or something. And you can you see, like, yeah, like, the extent to which that hash code can be rediscovered. Yeah. So that's more like the security approach. Right? There's the Mia community worrying about these things. Yes, yeah.
pal.k: But is it of value to demonstrate that it is not a feasible task.
pal.k: Is it a valued as as in basically like, if you can demonstrate that this actually isn't something that can fruitfully occur like, you can't actually
pal.k: extract things. If you can't actually attribute a particular training data to an output. Is that still worth it to sort of like. Look at and and see if
pal.k: you know, I think that if
pal.k: if you were to be able to prove an impossibility, theorem, or something like that that would be a good exactly. That's sort of what I was thinking. But I'm not sure that
pal.k: people believe. Yes, that's 1 of the questions, because.
pal.k: you know, there's there's there's a bunch of literature that suggests, oh, here's
pal.k: the the influence function literature, right? Suggests. Oh, here's what an idealized
pal.k: solution would be but it's just very expensive to compute it involves something like the square, you know.
pal.k: A single step of the iteration involves, you know, computations on the order of solving matrix problems, where the matrix is the size of the square, of
pal.k: the number of parameters and models. So if you have a
pal.k: you know, trillion parameter model. Then that's a trillion trillion that you can't solve these problems. Okay?
pal.k: And so, so
pal.k: so. But but because this, you know this. This is sort of these formulations out there that are sort of unsolvable. Then, like, I'm not sure that you can prove an impossibility there, it just might be infeasible
pal.k: to. Just to yeah. Just to add to that, like again, I guess in the privacy world there's like these data extraction attacks where, like you prompt some. You prompt something to the model, and then they are able to get give out like, let's say, 100 plus so tokens up clearly, match like a
pal.k: data training data point that they were able to get so like, at least for those cases you can like easily show that it's document.
pal.k: And I think so. The other thing, I think, is probably gonna happen is, I think people are
pal.k: people are gonna become become comfortable with
pal.k: an estimate on attribution. Right? So
pal.k: you know, like that, your your internship company adobe
pal.k: and other companies like this are, they're they're gonna start selling this as a product. Right? Yeah. So they're they're gonna socialize the world into the idea that, yeah, we can estimate. Yeah, even though it's not a guarantee. We can estimate attribution in different settings. And so
pal.k: so I feel like
pal.k: it's it's an area that's worth
pal.k: study academically, instead of just letting people, you know, sell products making claims.
pal.k: Right? So yeah, so the thing that comes to my mind when I was pitching this is, there's been some work on like grounding language model outputs with citations or something like that. So that might be like relevant for like code, like, maybe you don't care that it's actually coming from the training data. Yeah. But like, here's some similar codes. May. Maybe it is like some kind of like, semi fuzzy matching to attribution like.
pal.k: like, here's some code that was similar. This is helpful for thinking about why this element output this code or something. Yeah, I agree. Like, instead of calling it. Here's us attributing this to training data. We could like, be more
pal.k: like, like, similarly, like, if you look at like this, neuron fires on a bunch of these kinds of texts, you're like, okay, well, I can kind of look at these texts and figure out, okay, yeah, it's firing on, or whatever
pal.k: you can maybe pick out the pattern that way, or something
pal.k: I mean, like so like perplexity has, you know, when you do like a search and perplexity. For instance, it like cites a bunch of, you know, like this is where I got this from. I have no idea how it's doing that.
Dmitrii Troitskii: Perplexity does work.
pal.k: It's some kind of vector database search. It seems like most of the citation. Yeah, I mean, the easiest way to do would just be have a vector database of like Google. And then you just like find the the most similar, like the closest vectors in your in your vector space, to the
pal.k: to the, to the like sentence that the language model produced right
pal.k: and and like
pal.k: we were saying before, like
pal.k: that would be easy to fall into. And that doesn't feel to me like
pal.k: research, like I mean, like, like, that's that's more of an engineering thing I feel like than like a research question.
pal.k: like how to do that. So
pal.k: can I? Yeah, I'll just give you a practical example of it. So adobe did
pal.k: try to include this data attribution into their pipeline to give artists royalties based on how much firefly is outputting art examples. The reason they couldn't do it is because an artist wasn't there in the training data?
pal.k: Oh, and then, yeah, I see, yeah.
pal.k: And it's so. They were confused. Like, how do we separate? Is this a learned training artifact? Or is this something that
pal.k: the model is just thinking could be.
pal.k: you know, the influential? Yeah.
pal.k: So I like what Eric said right? Instead of narrowing it down to this is training data attribution. You could be more open about it and say, Oh, these are probably grounding the output to these particular examples. Inspiration.
pal.k: So does it make sense to use attribution as the objective as the framing. So like, I kind of feel like you've got. You've you've got 2 possible goals. Right? One is
pal.k: you know. One goal is to answer the question.
pal.k: You know, what what citations should we provide that are most helpful
pal.k: to a user?
pal.k: Which is which is
pal.k: interesting, but that I feel like that is
pal.k: a whole that that brings us down the whole path of user studies.
pal.k: and understanding. You know human. You know, human perceptions, human behavior, human learning.
pal.k: right and then, or or the other possibility is to say, Hey, we're going to
pal.k: give you the citations that
pal.k: our estimate for what what we think was the most informative for the model during its training.
pal.k: right? Yeah, I I don't think, yeah, yeah.
pal.k: that's that's a statement we can make. So the second thing, yeah.
pal.k: because if I give you a sample which is not in the training. But but no, I understand. But like. But you can say that that's what we're modeling that that's that's the goal.
pal.k: Right? No, no, I'm saying, if a new sample which is not on the training highest score. Yes. Does that mean? Your method is really looking at the training influence, or is it looking at something else? No, but it's but you know it's it's it's you know. But you're but you can say that you're modeling
pal.k: you're modeling the.
pal.k: If it had been included it would have been influential. Right?
pal.k: So
pal.k: right? You you know what I mean.
pal.k: that that it that it's an estimate. Yeah, thanks. Thanks, ladies, for coming. By the way.
pal.k: yeah. But I mean, you certainly couldn't use that for royalties, which is what adobe ran into. I guess right? It's you can't use it for money, right? But there's this sort of 2 interesting objectives
pal.k: right there. Yeah.
pal.k: yeah.
pal.k: Anyway, it's interesting.
pal.k: because I feel I feel like if you're on the other side and you're trying to
pal.k: optimize usability.
pal.k: Then it's like, you say, it's a little bit of engineering, I mean. So it can also be scientific. But we don't have access to a lot of this stuff like, I feel like, if you're
pal.k: if you're city sitting on Google, then you can estimate usability by monitoring click streams and doing, you know, a accessing. These other data sources that as as an academic lab, we don't have access to right? Yeah.
pal.k: right?
pal.k: Right?
pal.k: Okay.
pal.k: that's interesting.
pal.k: Hot.
pal.k: Okay, that's food for thought.
pal.k: Yeah, thanks. Guys.
pal.k: thank you. Alex.
pal.k: yeah. So that's great.
pal.k: So
pal.k: let's see. So next week is what what's next week is that is, that is, next week.
pal.k: November first.st
pal.k: Oh, my bad! Never mind, he's November 8, th right? So November first.st Actually, I'm out of town.
pal.k: right? Cause I'm I'm I'm speaking at Nyu.
pal.k: And
pal.k: so you, you. But you guys should meet anyway, just to right. But you know. But I just let you know.
pal.k: Oh, yeah. So next week we just have, like India talk. Just Fe, like the feature updates. Next to next week, we have our November.
pal.k: Okay, cool. I mean, our yeah.
pal.k: Alright cool.
pal.k: Is there a talk coming up today.
pal.k: No, I think not. Yeah. We were. We didn't have anything on the schedule that while it was a day where you don't have a talk at 10 Am. Noon was not able to. I don't think so. I so I can. I can check my my my chat here. I think that.
pal.k: And it ended up the Ra.
pal.k: We didn't. We didn't get
pal.k: no problem that could be some other day. Yeah, no, no one else at the moment right now. So all good
pal.k: for today. Okay, okay.
pal.k: yeah.
pal.k: Yeah. So let's so we'll figure it out. So,
pal.k: yeah. So something for the students to think about so like and on end, if
pal.k: we're sort of trying to make a plan for what we're going to be doing for the next, you know few years on the end of infrastructure project. And we have this spreadsheet. That's in the end of, you know, Chat Channel.
pal.k: which is all these
pal.k: interpretability methods that we're going to make sure that. And if supports really well on large networks.
pal.k: And so
pal.k: so yeah, so you know, I can put the link to the spreadsheet out. But if you're interested in in like, what end? If is.
pal.k: gonna try to be good at, and you have objections to that. And you think, oh, no, I I think that end up should really be good at something different.
pal.k: Then it's a good time
pal.k: to let us know, and you know, share your thoughts and that kind of thing. Because, you know, we're really gonna
pal.k: we're really gonna manage a project. You know, with these goals in mind.
pal.k: Right? We're trying to figure that out.
pal.k: Okay, thanks, everybody.
pal.k: What's the workshop or something like that?
pal.k: You can write 70. Now, I think that's scm.