Start with an Example

When I first gave a talk on how to give a talk, I actually called it “How Not to Give a Talk”. This was back in the days before Powerpoint, when talks were prepared on acetate transparencies placed on overhead projectors, and I started my talk with the most awful initial transparency I could conjure up. It was crammed with tiny writing, it started with the dictionary definition of “talk”, … And to top it off, I began by placing the slide on the projector upside down and backwards. When I finally got the placement right, I proceeded to turn my back on the audience and read the contents of the slide off the screen, in a low monotone. Eventually I took pity on the audience and explained that this was an example of how not to give a talk.

There was a time when I was often attending talks by aspirants seeking a position as a new assistant professor. This was again before Powerpoint slide decks, when candidates came with their stacks of physical acetate sheets to use with an overhead projector. My reaction to their talks was generally that they would have done better to turn their stack of sheets upside down before starting. In particular, they might end their talk with an example, when I thought they should start with one.

I realize people have different learning styles. Some of you may approach a new subject better if first provided with some mathematical notation, and then a set of abstract definitions, followed by a very general theorem … and then eventually a concrete example. Despite having a very respectable undergraduate degree in mathematics from a very respectable institution, my mind does not work that way. I find it easier to approach a new subject by way of a simple, concrete example. I do think I’m in the majority. 🙂

It is easy to say “start with a simple, concrete example”. It is much harder to do it.

If I critique a student talk by suggesting they start with an example, they may nod and come back with an example moved up to the middle of the talk. My response would be “no, start with an example”. They may then come back with an example close to the beginning. My response would be “no, I really mean start with an example”.

I go through a similar process with my own talks. I get part way through a first draft of the talk and I realize I’ve broken my own rule: I haven’t started with an example. So I begin to negotiate with myself: “I could insert an example, near the beginning, but I really need/want to start by …”. Ultimately I capitulate and find a way to place an example at the very start. Which makes for a much better talk.

I went through a similar process with this blog post. Part way through writing it I thought “well, I should really treat this like a short talk and start with an example”. The best I could do was … well you just read it.

It is also difficult to come up with a concrete example. Not “this method is good for scheduling problems”, or for “nurse scheduling” problems; but here is the method applied to this nurse scheduling problem. And finally, it is very difficult to come up with a sufficiently simple example. Not “I used this to schedule the 563 nurses at our National Hospital” — that’s fine for demonstrating later how effective your method was in practice — but “suppose we have 3 nurses, need 2 for this shift, and these two refuse to work with each other”. Ok, that’s too simple. What we need is a “Goldilocks” example, not so easy that it doesn’t illustrate your contribution, not so hard that it doesn’t allow your listeners to understand your contribution, but “just right”. The trick is to come up with the simplest possible example that can still make your point. That in itself is very difficult.

It is very easy, however, to overestimate your audience’s ability to follow the example. I often encounter a talk that presents an example early on and think “kudos to you, speaker”, only to quickly find that the example becomes too complex for me to fully follow. You have been working with the material for months or even years. What seems obvious to you, will not seem obvious to your listeners. It is difficult, but you must try to put yourself in their place.

You may fear that if you make the example too simple, people won’t understand what a difficult, deep, wonderful contribution you have made. Don’t fear. It won’t seem that simple to your audience, and anyway the best ideas are often “beautifully simple” at heart. Plus you’ll have plenty of time later in the talk to demonstrate how really complicated what you’ve done is, and how clever you had to be to come up with it. Ideally you can use your example as a running example, adding to it as you proceed to flesh out your talk. And if your listeners are like me, they’ll appreciate how really clever you had to be to come up with that initial, simple, introductory example.

Recursive Visualizing

Ok, having just written a blog post on stats and visualization, I’m going recursive here, and posting a Cirrus word cloud visualization of my blog page (prior to this post):

I did this with Voyant Tools, which provide all kinds of textual analysis. For example, when I feed it the CP2021 URL it tells me that “Montpellier” has a .6666667 correlation with “October” with a significance of 0.035265204. Well, perhaps not the best example. 🙂 Let’s go back to word clouds again with the list of accepted papers for CP 2020:

(which, for a small fee, I can make available to Professor Stuckey, suitable for framing).

Compare with a word cloud for the accepted papers at CP 2010:

“Learning” doesn’t appear in 2010, but is fairly prominent in 2020. (It may have helped that the call for papers included a thematic track on “CP, Data science and Machine Learning”.) I think there are some other interesting differences, but I’ll leave that as an exercise for the reader — you can post answers in the comments (“reply”). Of course, these word clouds are only snapshots; it would be interesting to visualize trending terms over the full span of the conference. Are there any potential Hans Roslings among us?

Stats and Views

I’ve been playing with Microsoft Academic Entity Analytics. It provides an interesting variety of statistics and views. I looked up “constraint satisfaction problem“. Turns out the “top author” is Berk Hess. If that surprises you, you’ll be even more surprised to learn that Professor Hess achieved this distinction with only three “constraint satisfaction problem” papers. Understanding dawns when we see that the top-cited of the three, with 13,445 citations, is:

GROMACS 4: Algorithms for highly efficient, load-balanced, and scalable molecular simulation
2008 JOURNAL OF CHEMICAL THEORY AND COMPUTATION
Berk Hess, Carsten Kutzner, David van der Spoel, Erik Lindahl

In fact, Hess, Kutzner, van der Spoel and Lindahl are the top four authors listed for “constraint satisfaction problem”. I doubt that the Constraint Programming community has anything to offer here, but it might be worth checking out; could do wonders for your citation count.

So some caution needs to be exercised in viewing these stats, but they are still interesting. Another thing that stood out to me: the total number of “constraint satisfaction problem” publications reached its peak in 2013 with 478, and has declined to 256 in 2020. On the other hand, the number of “constraint optimization problem” publications went from 18 in 2013 to 34 in 2020. And in case you were wondering, the top five authors for “constraint optimization problem” are the authors of this paper (which has 337 citations and actually uses Integer Linear Programming):

Collective Generation of Natural Image Descriptions
2012 MEETING OF THE ASSOCIATION FOR COMPUTATIONAL LINGUISTICS
Polina Kuznetsova, Vicente Ordonez, Alexander Berg, Tamara Berg, Yejin Choi

There are many other ways to play with Microsoft Academic’s stats and graphs. An example. Another example.

Or perhaps you want to use the Microsoft Academic Graph software to create a bespoke tool for the constraints community? An example of the kind of thing that can be done.

And there are many other tools that might be used to produce many types of statistics or visualizations for the constraints community. Perhaps you have additional suggestions — for tools to use or statistics/visualizations that you’d like to see?


Configuration

I just received a notification from Google Scholar that Automated Configuration and Selection of SAT Solvers by Holger Hoos, Frank Hutter, and Kevin Leyton-Brown provided the 100th citation of my paper with Susan Epstein, Richard Wallace, Anton Morozov, and Bruce Samuels on The Adaptive Constraint Engine. Which is cool, but the funny thing is that when I was scanning my mailbox, “configuration” caught my eye, and I thought that the citation would be to my work on configuration.

There has been a long series of configuration workshops, going back to one organized by Boi Faltings, Gerhard Friedrich and myself in 1999. To quote from the call for papers for the 2020 workshop: “Configuration is as a special type of design approach where the product being configured is composed from instances of a set of predefined component types that can be combined in ways defined by a set of constraints.”

Configuration provides a great example of the practical application of constraint satisfaction. A good place to see this is a 2016 paper in AI Magazine by Andreas Falkner, Gerhard Friedrich, Alois HaselbĂśck, Gottfried Schenner, and Herwig Schreiner on Twenty-Five Years of Successful Application of Constraint Technologies at Siemens.

The Fastest Way to Put Your Audience to Sleep

The fastest way to put your audience to sleep is to speak in a monotone. The second fastest is to modulate your speaking, but only in a persistent, repetitive pattern.

(Actually, I lied, the really fastest way to put your audience to sleep is to read your talk. There are three people in the world who can do that successfully, all actors of whom everyone says “I would pay to see them read the phone book”. I’m assuming they aren’t reading my blog.)

You must modulate your voice. You can speak faster and s l o w e r. LOUDER and softer. (Sometime speaking more softly even serves better for emphasis than speaking more loudly.) You can pitch your voice higher and lower. You can — pause — for emphasis. Can you ask rhetorical questions? Yes, you can.

You can even have fun with your voice. I once gave a talk in which I (briefly) imitated the Queen in Alice in Wonderland. (“Why, sometimes I’ve believed as many as six impossible things before breakfast.”) In a high, squeaky voice. If anyone remembers anything from that talk, I guarantee you that it is my imitation of the Queen.

Quantum-accelerated constraint programming

Quantum-accelerated constraint programming

“This work suggests that CP is a promising candidate application for early fault-tolerant quantum computers and beyond.”

Reassuring, maybe we’ll continue to be relevant when everyone has a quantum computer in their pocket. 🙂

Note also that “Contrary to myth, quantum computers are not known to be able to solve efficiently the very hard class called NP-complete problems.

CP and quantum computing has a long history. See Tad Hogg’s Exploiting the Deep Structure of Constraint Satisfaction Problems with Quantum Computers from 1997.

Alter Ego

Check out the AI Foundation. Subbarao Kambhampati, a former president of AAAI, is the Chief AI Officer. “The AI Foundation’s mission is to responsibly move the world forward by giving each of us our own AI that shares our personal values and goals.”

I’ve had a notion of an AI “avatar” or “alter ego” for a long time, though I’ve never taken it very far. It appeals to me in part because it seems a natural application of constraints. Of course, everything does 🙂 but we each have our own likes, dislikes, etc., which might be modeled as (hard or soft) constraints. I’ve alluded to this briefly in these ‘grand challenge’ papers:

The One Word Secret of an Effective Presentation

The secret of an effective presentation can be revealed in one word: enthusiasm!

How can your audience be enthusiastic about your talk if you aren’t? The funny thing is you almost certainly are, but, like me, you may have difficulty showing it. I’ve recorded practice videos (a good idea by the way!) in which I felt that I was emoting energetically, and when I’ve played the videos back I looked like I was auditioning for a part in a zombie movie. The last time I gave a talk on how to give a talk a nice young fellow asked me afterwards why, when I was discussing enthusiasm, I didn’t appear more enthusiastic! Think how deadly it would be if I wasn’t at least trying to convey my enthusiasm! I’m sure most of you can do even better.

You may feel that a scientific presentation must be very serious. Not so. You may worry about overdoing the enthusism and appearing undignified. The fact is that it is almost impossible to overdo your enthusiasm. If you are a young person, older audience members are delighted to see an enthusiastic young person working in their field. If you are an older person, younger audience members are pleased to see an older colleague who still retains enthusiasm for their work.

You may be worrying so much about what you are saying that it gets in the way of a natural, enthusiastic presentation. Let me tell you a dirty little secret: most of what you say your audience will soon forget. Quick, how many details can you remember from the last talk you heard? You’ll be lucky if your audience remembers anything that you say, especially at a conference where they are going from one talk to another. Being enthusiastic can help with that!

You also may simply be nervous when public speaking. There are ways to address this, which I plan to discuss in a separate post; in fact, getting in touch with the enthusiasm you have for your work could help with this too.

Of course, extroverts have an advantage here. But Carl Jung said that there is no such thing as a pure introvert or extrovert, that such a person would be in a lunatic asylum. So use your inner extrovert!

Resource Controllability of Business Processes Under Conditional Uncertainty

Resource Controllability of Business Processes Under Conditional Uncertainty Matteo Zavatteri, Carlo Combi & Luca Viganò. Journal on Data Semantics (2021)

This paper proposes “conditional constraint networks with decisions (CCNDs) as a model to encode business processes that involve access control and conditional branches that may be both controllable and uncontrollable”. So it both provides a new extension of the CSP paradigm and a real-world motivation for it. The main citation to my work is to a paper with Mihaela Sabin on conditional constraint satisfaction.

I’m particularly happy to draw attention to this paper, as constraints researchers are perhaps unlikely to subscribe to the Journal on Data Semantics. Moreover, it appears that the journal will be ceasing publication this year. I’ve had the experience myself a few times of publishing in a journal that died shortly afterward; I’ve told myself that I was not culpable. I see that Zavatteri has a paper on Dynamic Controllability and (J,K)-Resiliency in Generalized Constraint Networks with Uncertainty in ICAPS 2020. Hope to see him publishing at the CP conference.

MCS Extraction with Sublinear Oracle Queries

Carlos Mencía, Alexey Ignatiev, Alessandro Previti, Joao Marques-Silva:
MCS Extraction with Sublinear Oracle Queries. SAT 2016: 342-360

Abstract. Given an inconsistent set of constraints, an often studied problem is to compute an irreducible subset of the constraints which, if relaxed, enable the remaining constraints to be consistent. In the case of unsatisfiable propositional formulas in conjunctive normal form, such irreducible sets of constraints are referred to as Minimal Correction Subsets (MCSes). MCSes find a growing number of applications, including the approximation of maximum satisfiability and as an intermediate step in the enumeration of minimal unsatisfiability. A number of efficient algorithms have been proposed in recent years, which exploit a wide range of insights into the MCS extraction problem. One open question is to find the best worst-case number of calls to a SAT oracle, when the calls to the oracle are kept simple, and given reasonable definitions of simple SAT oracle calls. This paper develops novel algorithms for computing MCSes which, in specific settings, are guaranteed to require asymptotically fewer than linear calls to a SAT oracle, where the oracle calls can be viewed as simple. The experimental results, obtained on existing problem instances, demonstrate that the new algorithms contribute to improving the state of the art.

Relating as it does to explanation, this is a timely citation. The authors have made numerous contributions to this area.

The citation is to:

Barry O’Callaghan, Barry O’Sullivan, Eugene C. Freuder: Generating Corrective Explanations for Interactive Constraint Satisfaction. CP 2005: 445-459

Abstract
Interactive tasks such as online configuration and e-commerce can be modelled as constraint satisfaction problems (CSPs). These can be solved interactively by a user assigning values to variables. The user may require advice and explanations from a system to help him/her find a satisfactory solution. Explanations of failure in constraint programming tend to focus on conflict. However, what is really desirable is an explanation that is corrective in the sense that it provides the basis for moving forward in the problem-solving process. More specifically, when faced with a dead-end, or when a desirable value has been removed from a domain, we need to compute alternative assignments for a subset of the assigned variables that enables the user to move forward. This paper defines this notion of corrective explanation, and proposes an algorithm to generate such explanations. The approach is shown to perform well on both real-world configuration benchmarks and randomly generated problems.