Latest / Strachey Lectures / Strachey Lecture: Integrating Logic, Probability and Neuro-Symbolic Reasoning using Probabilistic Soft Logic

Transcript

Strachey Lecture: Integrating Logic, Probability and Neuro-Symbolic Reasoning using Probabilistic Soft Logic · Strachey Lectures

• 0:00
  So welcome to this strategy lecture. This is a terribly serious of distinguished lectures named for Professor Christopher Strange Chris.
• 0:10
  The strategy founded Oxford Programming Research Group in 1965, and with Dana Scott,
• 0:17
  he founded the Field of Occasional Semantics, which provides a fun mathematical foundation to programming languages.
• 0:26
  Before introducing today, Speaker, I'd like to thank Oxford Asset Management for who generously support this great few lectures.
• 0:36
  I have been supporting this theory since 2015 and without the support we would be unable to host this series of exciting lectures.
• 0:46
  There'll be coffee and doughnuts after the talk,
• 0:48
  and this'll give students and researchers the opportunity to meet representatives of Oxford Asset Management.
• 0:57
  You'll be able to find you near the registration desk. Okay.
• 1:03
  So with respect to today's talk, it's my very great pleasure to introduce today's speaker, who is Professor Lisa Ghetto.
• 1:12
  Lisa Guitar is a distinguished professor in the University of California, Santa Cruz,
• 1:18
  Department of Computer Science and Engineering, and a founding director of the UCSC Data Science Research Centre.
• 1:27
  Lisa has been the recipient of many honours and awards in recognition of her distinguished research contributions,
• 1:34
  including fellowships of the ICI and I Triple A,
• 1:39
  Triple II, numerous paper awards and many invitations to give keynote talks and distinguished lectures such as this one today.
• 1:52
  Lisa is perhaps best known for her work on statistical relational learning,
• 1:57
  which is a subfield of II that combines logic and machine learning to deal with data that exhibits both complex structure and inherent uncertainty.
• 2:08
  She's also made important contributions in fields as diverse as data management,
• 2:13
  visual analytics and social network analysis, as well as being a passionate advocate for fairness.
• 2:19
  And I think in today's Cool Place that's going to tell us about her work on probabilistic Soft Logic,
• 2:26
  which is an SRO framework for large scale probabilistic reasoning and relational domains.
• 2:33
  So please join me and giving this a very warm welcome today.
• 2:43
  First. It's a huge honour to be here to give this talk.
• 2:48
  And Ian didn't give the back story that this talk has been in the making for quite a while.
• 2:56
  I think we first started talking in 2019 and I was supposed to give the talk in May of 2020.
• 3:03
  Just when things were kind of shutting down. And I'm really happy to be here and actually be here in 3D rather than 2D.
• 3:14
  And I'm hoping that my topic, which is about kind of mixing logic, probability and neural reasoning,
• 3:23
  I think is a really good fit to the kind of research that's being done and the computer science department here.
• 3:29
  So I hope you'll agree by the end. And then finally, I am going to talk about actually a programming language, a probabilistic programming language.
• 3:39
  So I hope that's kind of in honour of Christopher is fitting.
• 3:45
  But before I get into the kind of meat of the talk, I want to kind of pop things out a little bit and put a bigger picture on what I'm doing.
• 3:57
  And so, if you will, a subtitle or super title for my talk is The Power of Relational or Statistical Relational Thinking.
• 4:09
  And you know, what do I mean by relational thinking?
• 4:14
  And relational thinking is interesting because there's all these different fields that use the term,
• 4:21
  but they mean kind of different things in these different areas.
• 4:26
  So let's start with psychology.
• 4:28
  In psychology, there's this notion that it's about being able to talk about objects and attributes of objects and their relations,
• 4:40
  and that's part of intelligence. And within sociology, not surprisingly,
• 4:48
  it's about the ties between individuals and the memberships in organisations and those kinds of structures within mathematics.
• 5:01
  It's interesting, it has a kind of different interpretation and it's much more about the ability to go from the specific to the more abstract.
• 5:12
  So oftentimes the example given is a distinction between just doing calculations versus,
• 5:20
  you know, understanding how to manipulate things using algebra.
• 5:25
  And then finally, in philosophy A, the term is used in a lot of different ways.
• 5:33
  One of them is around a can of even notions of reality,
• 5:38
  of a relational ism around arguing against non duality between mind and body and subjectivity and objectivity.
• 5:55
  But. What does this mean from a perspective of computer science or machine learning?
• 6:02
  Ah, I, I'm going to argue that there's kind of two components.
• 6:08
  So one component is not surprisingly dealing with structure.
• 6:12
  So dealing with structure either in the inputs.
• 6:17
  So, you know, oftentimes in machine learning, you just have this flat attribute value vectors and you're trying to learn things from them.
• 6:26
  But, you know, so many things are much richer.
• 6:30
  Like even a graph or a multi relational graph and so on as common.
• 6:37
  And then also for the outputs, the outputs, the decision variables that one's trying to predict.
• 6:46
  Oftentimes there's a fair bit of structure in them and there's kind of dependencies between them, and you need to reason jointly about them.
• 6:55
  So the most obvious examples are natural language processing when you're doing something like parsing or computer vision,
• 7:03
  when you're doing scene understanding. So there's a structure that we want to be able to make use of.
• 7:11
  But then there's also uncertainty. And again, there's uncertainty in the inputs, you know, noise and uncertainty and the outputs,
• 7:21
  you know, quantifying the uncertainty over various different predictions that one's making.
• 7:29
  So what I argue is that we need Method Z are scalable and are able to deal with both structure and uncertainty.
• 7:42
  And in this talk, what I want to do is provide you with some kind of patterns and some methods for doing relational thinking.
• 7:57
  And these methods are going to use a mix of.
• 8:03
  Logic and probability or kind of hard and soft reasoning and also neural and symbolic reasoning.
• 8:14
  So the talk is divided into kind of three different components.
• 8:19
  The first part is I'm just going to go through some patterns, and these patterns are actually pretty basic,
• 8:27
  but we've found them over and over again to be super useful in building AI and machine learning systems.
• 8:38
  Then the bulk of the talk is going to be the tool section.
• 8:44
  It's going to go into a little more technical detail.
• 8:47
  And then, you know, we're computer scientists, so we always like to talk about scaling.
• 8:52
  So there'll be a section on getting this to work at scale.
• 8:56
  So for patterns, the way that I'm going to be representing these patterns is as logical rules.
• 9:06
  And so these have advantages. You know, they're good at representing structure.
• 9:12
  They tend to be interpretable.
• 9:15
  In about 10 minutes into the lecture, I'm going to back off on that and talk about also some probabilistic interpretations for them.
• 9:29
  And the. Canonical pattern said I'm going to go through are these structured prediction patterns that are super simple but still powerful.
• 9:43
  And the first ones, the simplest the simplest one is just collective classification.
• 9:52
  So you're doing classification problem where you're trying to predict labels for nodes in a graph.
• 9:59
  You know, you can't get much simpler than that. And, and the thing that I want to highlight is how to represent the reasoning pattern behind this.
• 10:11
  And the reasoning pattern is captured in these two simple rules.
• 10:16
  So one is, okay, I'm going to just use local information at the node.
• 10:22
  So attributes of the node to try and infer a label.
• 10:26
  But then I'm also going to use things about what the labels of its neighbours are.
• 10:32
  And the interesting thing to note here is the thing that I'm trying to infer label.
• 10:40
  You see this one rule where label is on both sides of the rule.
• 10:45
  So that's the thing that gets this dependence between the decision variables, the fact that I have unknowns potentially on both sides of the rule.
• 10:58
  So I need to give a little toy example of this.
• 11:03
  The one that I usually give is I have a social network and I'm trying to infer political parties.
• 11:12
  Okay, so these are the US political parties, so I'm going to switch them and keep the colours the same and the British parties.
• 11:24
  But so again, this is a toy example,
• 11:27
  but the idea is most often what happens is you're given a network where you observe the labels
• 11:39
  for some of the nodes and then it's just these other ones where you're trying to infer them.
• 11:46
  And so how do we instantiate that little pattern that I gave a minute or two ago?
• 11:53
  Well, I'm going to have a collection of local rules where the local rules say things like,
• 12:02
  oh, you know, if they donate to a particular party, they're likely to vote for that party.
• 12:09
  If they tweet about something, maybe this isn't a Labour thing that people tweet, but they're likely to be at that party.
• 12:19
  But then the more interesting rules are these collective rules where the collective rules take into account, you know, if.
• 12:31
  Their friends vote for a party. They're likely to vote for the party.
• 12:37
  If their spouse votes for a party, they're likely to vote for a party.
• 12:41
  And again, this is something that allows you to propagate the information.
• 12:47
  And using something like this, you can go through and end up doing a labelling.
• 12:53
  There's a bunch of different algorithms. I'm going to tell you one way that we do it at scale in the middle of the talk.
• 13:02
  Now, there is an important aside here, which is related to privacy.
• 13:10
  So it's exactly this issue that you can infer so much about an individual based on their network.
• 13:20
  That's important. I'm going to talk a little bit more about that towards the end of the lecture.
• 13:27
  So the next pattern again is that was about nodes.
• 13:33
  This is about edges. So inferring the existence of edges in a graph.
• 13:40
  And again, we have this super simple pattern that says if there's a edge between X and Y,
• 13:48
  there's a Z that's similar to Y, then there's an edge between X and Z.
• 13:54
  And because I have this thing that I'm going to infer, the link is what I'm trying to predict on both sides of the rule.
• 14:02
  That's the thing that's going to allow this dependence to happen.
• 14:06
  So what's a pattern for an example of this?
• 14:11
  Well, one of the things that there's a lot of work in is recommender systems.
• 14:18
  And recommender systems. Exactly. You're trying to predict what items someone will like.
• 14:25
  There's these kind of structural patterns that one can do where you can say, okay, if a user likes one item,
• 14:33
  there's another item that's similar to that item, then the user will like the second item.
• 14:42
  Also you can say, okay, if there's a user that likes an item,
• 14:46
  there's another user that's similar to that user, then the second user will like that item.
• 14:53
  And so, you know, this is a simple way of capturing what's done and a lot of recommender systems.
• 15:01
  The key challenge, not surprisingly, and note that these solid lines are the things that are observed.
• 15:09
  And then I'm making this prediction as a test. One of the challenges.
• 15:17
  How to represent the similarity. And then the kind of third important sub problem is entity resolution.
• 15:30
  And so what is entity resolution? This is something that's ubiquitous across computer science where you are essentially trying to
• 15:41
  determine when you have two references and they're really referring to the same underlying thing.
• 15:51
  Again, we can set this up where we use local information.
• 15:57
  So, you know, if they have similar names, they're likely to refer to the same, let's say, person, if they're similar, linked to similar things.
• 16:10
  But then the kind of collective pattern that is.
• 16:17
  Important is if X and Y are the same and Y and Z are the same, then Excellency are the same.
• 16:27
  So this is a transitivity that allows you to infer additional same as links.
• 16:36
  And this is important,
• 16:42
  but there are some domains where you actually have a different kind of rule and
• 16:48
  understanding your domain to know when you do this kind of clustering versus some domains.
• 16:55
  What happens is let's. What happens is it doesn't go black.
• 17:03
  You have a more of a linking kind of problem.
• 17:08
  So it's said if X and Y are the same.
• 17:12
  And Z is not the same as Y, then X can't link to Z.
• 17:18
  So think about this. When you have two databases that you're matching across and they've been duplicated and you're only allowed to match across one,
• 17:28
  and a distinction of knowing when you're in the clustering setting versus when you're in the mutual exclusion setting as important.
• 17:38
  But now those are all these kind of micro pattern that my favourite pattern is one where you do all of these at the same time.
• 17:50
  And so this is a problem of graph identification we first kind of introduces like ten years ago.
• 17:58
  And let me again kind of define it by example a.
• 18:05
  A setting where we have a kind of noisy input graph, but then we have to do all these different inferences to infer an output graph.
• 18:17
  And then this output graph is the thing that we then want to go on and do our analysis on or do our science on.
• 18:26
  And an example would be you have a communication network.
• 18:31
  In this case, it's an email communication network, but you have email addresses and the edges are communications and you have some.
• 18:41
  Content information. And then what you're trying to do is infer out an organisational network or social network and here the nodes are different,
• 18:54
  they're not email addresses, they're actual people. The edges have a different semantics there.
• 18:59
  Who's in charge of who and the node labels maybe are, you know, what are their roles in the company?
• 19:07
  And so, again, what does this problem look like?
• 19:12
  I have as input this graph I'm trying to get out this so I don't have this observed.
• 19:20
  What do I need to do? I need to, you know, first.
• 19:24
  Go through and do entity resolution where I figure out, you know, who are the people?
• 19:31
  Then I have to do the link prediction of, you know, who manages who.
• 19:39
  And then I have to do the inference of their kind of roles in the company.
• 19:45
  So I need to go through and do the labelling of this.
• 19:49
  The thing that's kind of interesting about this, in my view, is how there's all these interesting dependencies.
• 19:58
  And most of the time people look at these problems in isolation.
• 20:03
  So they either do collective classification or they do link prediction or entity resolution,
• 20:08
  but trying to do them all at once where there's dependencies between.
• 20:15
  You know, obviously on the observed graph.
• 20:18
  But there's also what I was emphasising before that in tread dependence across the predictions in each of the task.
• 20:30
  But then there's also this kind of. Interdependence across them.
• 20:37
  And it's really these kinds of complex reasonings with graphs that kind of motivates much of my work.
• 20:49
  So. Now let me get into methods for doing this.
• 20:55
  And I'm going to be talking about tools and.
• 21:02
  I'm first going to talk about tools that combine the statistical and relational, so the logic and probability.
• 21:10
  And then afterwards I'm going to talk about methods that combine the neural and symbolic.
• 21:17
  So for the statistical relational, you know, this is an area, sub research area,
• 21:26
  as you mentioned, that combines logical representations, handles uncertainty,
• 21:34
  and is especially designed to do these kind of collective problems where these rich
• 21:40
  dependencies and there's been a lot of different languages that have been proposed.
• 21:49
  And we're going to add one to the mix.
• 21:53
  PSL. PSL stands for probabilistic soft logic.
• 22:01
  It's an open source toolkit. There's a bunch of examples and tons of resources at this website.
• 22:11
  But at a high level, going back to the fact that I represented all these patterns as these logical rules.
• 22:20
  Well, logical rules have advantages, but they also have disadvantages.
• 22:25
  So in general, doing full reasoning with them is intractable.
• 22:33
  If there's inconsistencies, that's going to be a significant problem.
• 22:38
  And, you know, one of the things that I mentioned is dealing with similarity.
• 22:43
  You know, they're not great at representing similarities.
• 22:47
  So what we try and do with PSL is basically turn these disadvantages into advantages
• 22:57
  and have a tractable method that can handle the inconsistencies and can represent.
• 23:09
  Similarities are a degree of similarity.
• 23:13
  So what does this look like?
• 23:17
  It's a probabilistic programming language for these collective problems, and it is represented as weighted rules.
• 23:30
  The. Key thing with these weighted rules is the kind of ground atoms that we'll get to are going to be not standard zero one binary,
• 23:47
  but continuous value between zero and one.
• 23:51
  And a cell programme is just, you know, these rules plus some input data.
• 23:58
  So. We make reasoning scalable by converting this to a convex optimisation problem.
• 24:06
  And so what I want to do is show you how we come up with this particular optimisation problem.
• 24:15
  And this is work very much by my former Ph.D. student, Stephen Buck, and Bert Wang, a post-doc that worked with me.
• 24:26
  And I'm going to flash up the particular relaxation that we introduce.
• 24:35
  And then I'm going to show you how we get to it under three different ways.
• 24:39
  So for now, I'm going to unpack this in a minute, but kind of see if you can kind of memorise this pattern.
• 24:49
  And. This pattern. The interesting thing is it comes up under three different interpretations for this way to logic programmes.
• 25:00
  So one comes from randomised algorithms, theoretical computer science.
• 25:04
  One comes from probabilistic graphical models and one comes from soft logic.
• 25:11
  Let me do the first from randomised algorithms. So.
• 25:18
  We're going to take this way to logical rules, and I'm going to rewrite them so that we have non-negative weights.
• 25:29
  I'm going to write it in this normal form.
• 25:34
  And then I'm indexing over the positive literals and the negative literals.
• 25:40
  So it's a little. A messy bit.
• 25:46
  And then what I want to do is.
• 25:49
  I want to. Find that assignments to the x variables that maximises this weighted sum.
• 26:00
  And so, you know, all of you guys go back to your algorithms class and you say, Professor Gitau, I remember that.
• 26:10
  That is why you did Max that and that is amp hard.
• 26:15
  So that doesn't seem like you got anywhere so far.
• 26:20
  But now what we're going to do is take this MP hard problem and.
• 26:27
  We're going to convert it to a problem where we instead interpret the random variables as probabilities,
• 26:34
  rounding probabilities, so the probability they round up to one are down to zero.
• 26:40
  And doing this, we can make use of this old result of Gomez and Williamson.
• 26:47
  They actually have to really famous results from the same year.
• 26:51
  But this gives a way of bounding the expectation for that expression with a linear programme.
• 27:04
  And you can go further and say that this gives you this three quarters optimal rounding guarantee for this relaxation.
• 27:15
  And I know everybody remembers what I put two slides ago.
• 27:19
  If you look at this main part of the term here, it has the form that I showed a minute ago.
• 27:29
  So this is one interpretation where I get a relaxation that is nice and is basically a linear programme.
• 27:39
  Now there's a second interpretation. And the second interpretation comes from graphical models.
• 27:45
  And so what I can do with my weighted logical rules is I can basically form a big giant graphical
• 27:54
  model where I have my random variables and then I have these potential functions that are the rules.
• 28:04
  So the logical rules. And.
• 28:12
  They're kind of the potential functions in the graphical model.
• 28:17
  So they're kind of weird potential functions because they're just our logic.
• 28:24
  But still, I can do this.
• 28:26
  And then the standard thing that people do in graphical models is then define a distribution where the distribution is just over all of the rules,
• 28:40
  the sum of the weighted potentials. And the classic problem is to then find the assignment of variables, then maximises this exponent.
• 28:53
  It will be the most probable. So at this point I've done nothing rather than just rename weighted max that into graphical models.
• 29:03
  But we can go from here when one's trying to find the assignment to the variables.
• 29:13
  One of the things that one can do is to solve this is to find a globally consistent set of marginal distributions.
• 29:26
  Again. This is still hard because there's exponentially many constraints.
• 29:33
  So what people and graphical models have often done is to do these local consistency around relaxation.
• 29:42
  So rather than enforce all of the constraints, just enforce a few local ones.
• 29:49
  There's a whole cottage industry in different ways of doing this.
• 29:55
  We can make use of this in our setting and introduce some kind of pseudo marginals over some joint potential states, but not all of them.
• 30:10
  Then we can take. Our expression, put in these constraints for consistency with just the marginals and the pseudo marginals.
• 30:24
  And then, you know,
• 30:25
  do a little bit of not terribly complex analysis to kind of rewrite this and get rid of the pseudo marginals projected onto the mews.
• 30:42
  And we can get out this expression.
• 30:46
  And again, if you look at this expression, it has the same form as the max set relaxation.
• 30:55
  So we got to the same relaxation, but through to pretty significantly different interpretations.
• 31:04
  And this result actually between these two is interesting just in and of itself, because the people that were doing the local consistency,
• 31:16
  relaxations and graphical models would do them, but they didn't have any bounds.
• 31:20
  So now we can take this down from the max set relaxation and apply it.
• 31:26
  But that's two of the three interpretations.
• 31:30
  So the third interpretation comes from soft logic, and this is where we just start off and say, you know,
• 31:40
  the random variables are continuous between zero and one, you know, interpreted as either similarity or degree of truth.
• 31:52
  And, you know, there's different soft logics. We use Fukushima's logic and then through doing some manipulation to find the exact max solution.
• 32:08
  So no approximations happening here at all.
• 32:13
  You get this expression. And this expression.
• 32:17
  Now, you can kind of have a little bit of an interpretation for it of where it came from,
• 32:25
  because this is really like either the rule is satisfied so it's one or it's not satisfied.
• 32:32
  So I'm going to add up the truth values of the positive literals and the truth values of the negative literals.
• 32:39
  And talk about that is the degree of satisfaction.
• 32:43
  And again, if you look at this expression.
• 32:48
  It matches the other two. So we've gotten to.
• 32:54
  The same relaxation through three different interpretations, which always seemed like a good sign of consistency.
• 33:09
  With pencil, we actually ended up going further than this.
• 33:12
  So we introduced a notion that we called hinge loss mark of random fields.
• 33:17
  And so the hinge, less marka random fields have this kind of same general form.
• 33:27
  But now. Rather than this expression that we had before, we're going to allow kind of arbitrary linear expressions here.
• 33:39
  This allows us to add in constraints as well.
• 33:44
  And then, you know, what is a pencil programme?
• 33:47
  Well, a pencil programme, you know, this is an actual pencil programme.
• 33:52
  I guess you can't read it that well, but for that simple collective classification problem that we had before.
• 33:59
  So, you know, you have interpretable.
• 34:04
  And you have a cell programme, you have some data and you.
• 34:10
  Have a distribution, a conditional distribution that you can solve for.
• 34:15
  Now. How do you learn a cell programme from data?
• 34:21
  There's kind of two issues. One is where do you get the weights from and where do you get the structures of the rules?
• 34:27
  So if I had 2 hours for the talk, I would tell you all about that that I don't.
• 34:34
  So you guys will have to trust me or invite me back or talk to me after the lecture about ways of learning this.
• 34:41
  But there are ways of doing them. But. Let's talk instead about.
• 34:48
  Well. Does it work? Empirically.
• 34:53
  And I'm going to show some kind of simple examples of it working, but they're they're kind of representative.
• 35:02
  So the first example is an example of doing activity recognition in video.
• 35:09
  And in this setting, we compared with using some.
• 35:16
  Kind of different feature representations that at the time are commonly used.
• 35:21
  And then we'd add in these peers our rules to the features.
• 35:28
  And these rules were like super simple.
• 35:31
  So they just captured little teeny patterns analogous to the ones that I gave at the beginning.
• 35:38
  But you see over and over again that they kind of give you a significant bump in performance.
• 35:48
  Another collection of results for some collective classification problems and a link prediction problem.
• 35:56
  Here we're comparing to a discrete MRF.
• 36:01
  And we see that we do a little bit better.
• 36:05
  But even on these small problems, we're significantly faster.
• 36:10
  I'm going to drill and expand on that shortly.
• 36:16
  Then with a kind of state of the art approach that did a kind of similarity propagation
• 36:23
  so completely different kind of algorithm we were able to outperform them on.
• 36:33
  Kind of biological setting. And then a third setting where we're doing emotion recognition in dialogue,
• 36:45
  comparing to a variety of neural net approaches, including some pretty sophisticated neural net approaches.
• 36:52
  Even with a relatively simple PSR model, we were able to significantly outperform.
• 37:00
  So. This was about combining logic and probability.
• 37:08
  Now let's talk a little bit about combining neuro and symbolic reasoning.
• 37:14
  So for neuro and symbolic reasoning, similarly, there's a whole community, the NSC community,
• 37:23
  that works in this area where they want to make use of the advantages of sub symbolic
• 37:30
  representations and include symbolic reasoning and do this in a way that integrates them properly.
• 37:42
  And just like before.
• 37:47
  There's a ton of different languages out there that people have proposed and we're going to add one into the mix.
• 37:55
  New PSL. So. What is new.
• 38:01
  So neuro probabilistic, soft logic. And again,
• 38:08
  there are some foundations where the foundations I think one of our contributions
• 38:14
  here is to introduce a generalised form for a neuro symbolic reasoning.
• 38:24
  And then instantiate it in a particular way. So the we're going to do this by introducing neuro symbolic energy based models.
• 38:37
  And it's a general family of energy based models.
• 38:42
  And. They highlight the boundary for where the kind of neural reasoning and representation is and where the symbolic is.
• 38:55
  In a nice way, I'm going to kind of illustrated by kind of cartoon where, you know,
• 39:03
  a standard energy based model is just can be represented kind of generically like this.
• 39:12
  And what we're going to do for a neuro symbolic,
• 39:14
  energy based model is we're going to break it down where we have the wires, which are the output variables?
• 39:23
  We have the symbolic input variables.
• 39:29
  We have the neural input variables.
• 39:34
  We have the parameters of the symbolic system and we have the parameters of the neural system.
• 39:43
  So we're just kind of explaining the notation.
• 39:48
  And then for doing the integration, the boundary is really captured by this interface between the neural and the symbolic.
• 40:04
  And exactly how that feeds in will depend on the different language and interpretation.
• 40:12
  And, you know, this is pretty generic and it's able to represent.
• 40:21
  I think more than this. But the ones that we've gone through and looked at, you know, deep problem logic tensor networks, deep stock plug,
• 40:30
  neural answer, set programming, all of these can be fit into this neural symbolic energy based model framework.
• 40:42
  How did we then do new so well for new PISA?
• 40:49
  It is basically that.
• 40:54
  We had this from before.
• 40:58
  And we are going to.
• 41:03
  Kind of have this. Function, the potential function, the hinge loss have this form that matches the factorisation of across a neurone symbolic.
• 41:18
  So with this in mind we can go to our you know.
• 41:25
  Architecture. And, you know, the way that you do inference is you just kind of go feed.
• 41:32
  Forward through. These systems.
• 41:38
  If I point out the right thing to do that. Animation.
• 41:44
  And then to do learning. So to learn the parameters of both the symbolic and the.
• 41:54
  The Neuro you go through and you do the inference and then you calculate the loss, and then you can propagate the loss through the system.
• 42:07
  So the nice thing about New Pixel is that it gives us this kind of expressive language.
• 42:16
  It has all of the things from pencil.
• 42:21
  It's scalable and as a general. So, you know, you can use it with a variety of different neural packages and we have support for this.
• 42:31
  Again, this is kind of pretty fresh work.
• 42:36
  I'm going to show just a little experimental evaluation that I have a nicer one, but it takes longer to explain.
• 42:43
  So just a.
• 42:46
  It's one set of experiments where we were doing a collective classification and we're comparing to like a simple label propagation algorithm,
• 42:58
  existing NESI approaches and GCN.
• 43:04
  And we can clearly do way better than the other neuro symbolic approaches for the GCN.
• 43:12
  And yeah, we're doing a little bit better. But you know, the PSL model, the new PSL model is super simple.
• 43:22
  So the simplicity is part of the attraction.
• 43:30
  And. Let me now turn to a topic of scaling.
• 43:41
  So. We're interested in doing these big graft problems, but we want to make sure that we can do it in a reasonable amount of time.
• 43:53
  And they're key.
• 43:59
  Problem in this is we have our way to logical rules. We have some data.
• 44:04
  There's two processes that happen. One is the instantiation of the model, and then there's doing the inference in the model.
• 44:19
  So if we want to scale this, we can scale two aspects of it.
• 44:24
  One is the inference, which I'll talk about first, and the other is the grounding, which I also talk about.
• 44:32
  So inference. Remember, one of my claims was, you know, we went from a combinatorial optimisation problem to a convex optimisation problem.
• 44:42
  So already, yeah, that's pretty good in terms of scalability, but it's still potentially a huge linear programme.
• 44:53
  So what we can do is we can make use of the fine grained structure in these models and.
• 45:03
  We exploit this by decomposing, and we've looked at a bunch of optimisation techniques,
• 45:10
  but the first one that we looked at that was really beneficial was Adam's alternating direction multi method of multiplier.
• 45:18
  So it's something that's used a lot in computer science or in machine learning.
• 45:24
  And the simple idea, it's very simple idea, but you decompose it, you solve the problems, and then you do some message passing.
• 45:33
  And the nice thing for a convex problem is it's guaranteed to converge.
• 45:40
  The trick is how do you make sure the sub problems are fast?
• 45:45
  And this is the place where we have these hinge losses.
• 45:49
  And if you break it down and look at these hinges.
• 45:54
  A lot of them are just trivial. So you can just ignore them and you can get to a much smaller set of constraints and then solve that.
• 46:05
  And so the first set of results I'm going to show are just comparing to using an off the shelf convex optimiser.
• 46:17
  A commercial grade optimiser.
• 46:20
  And then our admin implementation.
• 46:24
  And the first thing you see is for something with 150,000 potentials, you know, the convex optimiser took 3 hours,
• 46:35
  the commercial grade one took 3 minutes and it took a few seconds for something that was even larger with 800 million potentials,
• 46:46
  you know, so it could do it in a minute. But the others just, you know, can even handle it.
• 46:52
  So that was good. However.
• 47:00
  Of the total time to solve so that 800 million potential one one minute was
• 47:07
  doing the optimisation and 5 minutes was doing the grounding of the problem.
• 47:14
  So. The next thing that we looked at was how do we speed up grounding?
• 47:21
  And this is very much work with my current Ph.D. student, Eric Augustine.
• 47:28
  And you can see why grounding is an issue. Because even.
• 47:35
  In the simplest case where I'm potentially doing pairwise similarity, you know,
• 47:41
  if I have n things that I'm comparing, I'm going to get and squared and you know, that's just a simple setting.
• 47:47
  It can get much worse than that. So. What can we do to speed this up?
• 47:55
  Well, the first thing that one can do, and it's done in a lot of different areas and of course, goes by a lot of different terms.
• 48:05
  But is blocking and blocking is the simple idea that if you have, you know, say,
• 48:13
  a simple case where you have the pairwise comparison to say, okay, I'm not going to do all comparisons.
• 48:19
  I'm going to somehow break it into blocks and only do the comparison across blocks.
• 48:25
  And, you know, within databases, there's approaches with in data mining,
• 48:32
  there's approaches within theoretical computer science, there's approaches, you know, we'll use these approaches.
• 48:40
  But then in the implementation with PSR, we can implement that blocking as a blocking predicate.
• 48:52
  We can form all of these rules as conjunctive queries.
• 48:58
  Give them to the database and give a kind of this as a hint to the database for optimising.
• 49:06
  And this can make a huge, huge difference in performance.
• 49:11
  So. Here's a couple of different settings.
• 49:17
  So first off, notice that this is a log scale where we're comparing performances and,
• 49:26
  you know, making use of this can give you, you know, significant speed ups.
• 49:32
  So this was the first thing that we looked at.
• 49:36
  And just to give you a little sense of the community and where the community
• 49:41
  and S.r.l. has been in terms of the scale of the problems that they've done,
• 49:46
  you know, some of the works from MLS ends in alchemy.
• 49:53
  In 2007, they were doing problems that had a million potentials and doing it.
• 49:59
  And, you know, 400 minutes Tuffy came along, which was an implementation that sped things up quite a bit and scaled things.
• 50:12
  2015 Fox Pixel, which was a distributed implementation of parcel, sped things up.
• 50:21
  And then, you know, in 2018 the results that use the admin were able to speed this up and do larger problems.
• 50:36
  This is version 2.1. Version 2.2 which this version the main thing was smarter memory management and
• 50:47
  kind of systems issues is able to do 150 million potentials in 10 minutes.
• 50:57
  But we can go further and so we can go further by being even smarter about how we do our query generation for grounding.
• 51:11
  And this is nice work that makes use of ideas in the database community on multi query optimisation.
• 51:20
  And this idea is, you know, we have all these different rules,
• 51:27
  we can generate potential query plans for them and then we can look for opportunities
• 51:33
  to reuse the queries and you know of the different set of queries that cover them,
• 51:41
  find the one that is expected to perform the best.
• 51:45
  Again, you know, finding that is a challenging computational problem.
• 51:51
  And here's some representative results. I know these are too small to see, but one of the things that's kind of interesting is,
• 52:01
  you know, we just added a bunch of overhead of searching over different query plans.
• 52:06
  You would think that you might pay a price for doing that.
• 52:11
  And it turns out that price isn't so much.
• 52:14
  And then on the larger data sets, you get a significant speed ups.
• 52:22
  And you know, this is going to depend on the problem. It could end up being even more so from this.
• 52:29
  We add a new line into our.
• 52:33
  You know, benchmarks. And we're able to do these 150 million potential problems in 2 minutes for grounding.
• 52:44
  But wait, there's more. So we can again make use of ideas from database theory to go beyond this and something that we called tandem inference and.
• 53:00
  Tandem inference. The idea is, you know, this picture that I showed.
• 53:05
  It really has this grounding problem that we're blocking on.
• 53:09
  It's like, first we have to ground it and then we start doing inference.
• 53:14
  Well, what if we. Due streaming, grounding and streaming in France.
• 53:21
  So as we start grounding, we start solving the problem.
• 53:28
  Well, we can do that. And this black line is a tandem in France.
• 53:35
  And then there's two different inference methods the admin that I showed before, and another one stochastic gradient descent,
• 53:42
  but across a bunch of different canonical data sets, you know,
• 53:48
  we're able to get solutions before they've even started completed the grounding process.
• 53:57
  So that's exciting. But in addition, we're to the point that we can now do problems that are too big to fit into main memory.
• 54:08
  So we're able to essentially take these huge problems.
• 54:13
  If you were to put it in two main memory, you give it a small blur amount of space.
• 54:23
  You page things in and out. And with this, we're able to now scale to things that have, you know, billions of potentials and do them in the same time,
• 54:38
  the things that were, you know, several orders of magnitude smaller or before.
• 54:45
  So this whole progression we find exciting and we're pretty sure we're the people that are doing the largest problems of this kind in this complexity.
• 55:00
  Through, you know, people that we've talked to at various companies as well.
• 55:05
  So I am not going to talk about online PSL.
• 55:11
  We also have methods for kind of changing the models on the fly.
• 55:17
  What I do want to talk about briefly is.
• 55:22
  Some of the applications that we've done,
• 55:24
  because I'm actually really proud of the work that my group has done using pencil on kind of a rich collection of problems.
• 55:37
  So we've done things on computational biology and health informatics.
• 55:45
  We have done a fair bit of work on natural language processing, not surprisingly, recommender systems.
• 55:54
  We've also done work in computer vision, energy and the environment.
• 56:01
  Computational social science. A fairness, which I'll mention a bit.
• 56:09
  Information integration and extraction. And predicting malicious behaviour.
• 56:17
  The one of these that I want to go into a bit is the information integration,
• 56:25
  because I think it's kind of connects with research being done here and in kind of interesting ways is knowledge graph construction.
• 56:37
  And Knowledge Graph Construction also connects with the original graph identification pattern that I showed earlier where the idea is.
• 56:50
  Then you have a bunch of facts from these facts.
• 56:55
  You're trying to extract out a knowledge graph.
• 56:58
  In order to do this, you need to perform a collective classification linked prediction entity resolution,
• 57:06
  but you also have to enforce ontological constraints.
• 57:10
  You potentially want to reason about the quality of the information and more.
• 57:17
  We've done this using KSL for a couple of different knowledge graph extraction problems, and the key takeaway from this is that we're able to do this.
• 57:33
  And all of the pieces of information are useful.
• 57:37
  So the statistical features and the semantic features kind of putting those together
• 57:43
  really helps in another kind of knowledge graph task where we're trying to do,
• 57:51
  um, knowledge completion.
• 57:55
  So you're kind of predicting links. Uh, the key takeaway from this is.
• 58:04
  Well, the approach is when you have a lot of clean data, a lot of data, and the data is clean work.
• 58:12
  But when you have noisy data and it's sparse, things like PSL can really help.
• 58:20
  So. I want to close by talking about kind of opportunities and challenges.
• 58:32
  And so. I'll start with the challenge.
• 58:37
  So. The perils of ignoring structure.
• 58:42
  And. I alluded to one of these before that privacy and privacy and growth.
• 58:50
  And I think this is a really important area.
• 58:55
  And a lot of the work in privacy still looks at this kind of independent setting.
• 59:00
  They're starting to be work more work in privacy and graphs.
• 59:04
  And some of the work this was work of my former Ph.D. student,
• 59:08
  Elena Leiva was some of the earliest to look at how much information is leaked by the groups that you're a member of.
• 59:18
  Not surprisingly, it's a lot actually more than friendship links.
• 59:25
  Another important area is fairness.
• 59:29
  And with my former post deck garnish for Noddy and colleagues, we're pretty sure we're the first to look at relational fairness.
• 59:41
  And because so much about fairness is taking into account structural inequities
• 59:49
  that if you don't have a fairness mechanism that can represent the structure,
• 59:55
  that's going to be problematic. And then finally, looking at causality and causality in graphs is important.
• 1:00:07
  And this is some joint work with colleagues in the database world where we developed a relational causal system.
• 1:00:22
  I really think that if this conjunction of all three.
• 1:00:27
  Privacy, fairness and causality and understanding how they relate is important for methods that are able to kind of mitigate these impacts.
• 1:00:43
  And it's important to have the background and the social theory to be able to do the interpretation.
• 1:00:53
  In terms of opportunities. Yeah, all of the things that we look at these days are systems.
• 1:01:00
  So you think biological systems, ecosystems, social systems, things that are all these things combined.
• 1:01:09
  And this idea of kind of going from observational data.
• 1:01:17
  Doing some sort of graph identification to infer out a structure, then doing, you know, metrograph ID or knowledge graph ID to infer something,
• 1:01:33
  but then to close the loop where you use that,
• 1:01:38
  to go back and extract more information out and potentially, you know, keep doing this is important and.
• 1:01:50
  To the extent that this ties to these four different interpretations that I had at the beginning.
• 1:01:56
  So I think from their reasoning about entities and relationships and social ties,
• 1:02:02
  it's kind of obvious then this ability to go from specific to abstract and learning these things.
• 1:02:10
  And yeah, the philosophy was a little bit dicier, but, you know, it is,
• 1:02:16
  I think, going from a certain perspective sometimes in AI and machine learning,
• 1:02:22
  which is very atomistic to a more kind of not quite multi-agent but a systems view is important and.
• 1:02:37
  The last thing is the most important acknowledgements.
• 1:02:43
  My students that's the best thing about being a professor is our awesome students get to work with.
• 1:02:51
  I also am fortunate to work with a variety of different companies and organisations and.
• 1:03:01
  Just to wrap it up to say, you know, I hope that somewhere between the more tutorial or technical part,
• 1:03:09
  you come away with some ideas and ideas for things that either integrate probabilistic
• 1:03:18
  and logical inference and are on symbolic or data driven and knowledge driven.
• 1:03:23
  And I think there's tons of opportunities and a space that I think.