My thesis []

I'm done. The master in AI is complete. I finished the thesis about adding `Jungian personality in a chatbot'. In this blog post I will give a summery and some comments from a programmers' perspective that just don't fit in a thesis. For example, the implementation are not at all important, but I like talking about using Java in a functional programming style and the pains this caused.

The source is available here, for anyone interested. The full text is available here (and thesis source). The presentation I did can be found here (and it's source).

I start by discussing what the thesis was about in a summery (for those who don't want to read about 80 pages). after that I'll talk about the implementation details (I just want to lay my egg). Finally I will give an overview of the experience, including the defence (for those who didn't do a master, it maybe interesting),

1 What did I do?

I build a very fancy chatbot called Gaia, which is not based upon ALICE. The core is a business rule engine called Drools 1. Once the scenario described by YAML files are read, everything chatbot related happens in Drools. This means you can make it as smart as you want, for example you can make a rule that detects when a user is starting to repeat himself (and deal with that), or use timers that are native to drools to create a bot that acts impatiently. Pattern matching also happens inside drools, which means your not stuck to the regex system I provided. Unlike the ALICE chatbot where you have to use the ALICE patterns (which are less power full than regular expressions).

That was made to just to get started with personality. The issue with the ALICE chatbot was that it already predefined a response before any deliberation could happen. What I did was simply separating the `figure out what user said' step from the `this needs to happen next' steps. To make this separation more clear lets look at the syntax of both systems. AIML, which is the core of the ALICE chatbot looks like source block 1. A diagram representation of this block can be seen in figure 1.

<aiml>
    <categroy>
	<pattern>
	    Hello
	</pattern>
	<template>
	    Hi
	</template>
    </categroy>
    <category>
	<pattern>
	    How are you
	</pattern>
	<template>
	    Not doing too well today.
	</template>
    </category>
    <category>
	<pattern>
	    How * you
	</pattern>
	<template>
	    <srai>How are you</srai>
	</template>
    </category>
</aiml>

dep:aimlcats.svg

Figure 1: Deployment diagram of AIML example

Now let's look at the new representation I came up with in source blocks 2, 3, 4 and 5. Of which I made a diagram in figure 2.

literals:
  - Hi
  - Hello
literals:
  - How are you?
patterns:
  - How * you
  - How are you *
literals:
  - Not doing too well today.
regexes:
  - doing (*.) badly
from:
 - greeting
to:
 - symbol: greeting
 - symbol: status_inquery
---
from:
 - status_inquery
to:
 - symbol: reply_bad
 - restricted_to: patient

dep:aimlsyms.svg

Figure 2: Patterns to symbols

The new representation looks quite verbose too, but it does much more modelling than the original. Additionally, we separated the concerns of legal connections, from pattern matching. Modelling the scenario now almost entirely happens in the _connections file, and while doing that you don't have to deal with pattern matching. Using the file names as identifies guarantees uniqueness.

We can model complicated examples such as in source block 6. This can be seen as a diagram in figure 3. Trying to put such an example in AIML is basically impossible. First of all the concept of actors doesn't exist, secondly categories can't model the availability of choice. There are if statements, but that's making the decision in place. Aside from the fact you shouldn't do conditionals in xml structurally.

from:
 - greeting
to:
 - symbol: greeting
 - symbol: ask_reason_here
   restricted_to: doctor
---
from:
 - ask_reason_here
to:
 - restricted_to: patient
   symbol: need_medicine
 - restricted_to: patient
   symbol: broken_arms
 - restricted_to: patient
   symbol: feel_sick
---
from:
 - need_medicine
 - greeting
to:
 - restricted_to: doctor         
   symbol: why_need
 - symbol: status_inquery

dep:filedconns.svg

Figure 3: Symbol graph of connections grouped in file

1.1 The personality stuff

With the availability of choice in place, I could do the personality stuff. Jung's theory is used for personality to decide what the algorithm should use, this is also the core theory of for example MBTI. Jung said that each function has an attitude, either introversion or extroversion. Introversion deals with the inside world, memories and ideas. Extroversion deals with the outside world, which can be seen. An overview of the function can be seen here: \[\mathcal{J} = \{ T_e, T_i, F_e, F_i, S_e, S_i, N_e, N_i\} \] Each of these does something different, for the entire description I refer to the thesis or this source 2.

What we wanted is that these functions would plan ahead in cooperation with each other. This would be personality as a process rather than value based 3, this was a requirement by my teacher. To do this we introduced the dialogue tree data structure: \[ u = (a,s) \] \[ D = (u, [D])\]

Table 1: Description of symbols
\(u\) Utterance
\(a\) Actor
\(s\) Symbol
\(D\) Dialogue Tree

Where \(u\) is an utterance, \(a\) an actor, \(s\) a symbol and \(D\) the dialogue tree (see table 1). With this data structure we can plan ahead, each node is an utterance made that can have multiple possible responses (see figure 4). What we then pass this dialogue tree trough the functions either growing or sorting on preference. Each function in the personality can do modification, but the order of execution determines their `strength'.

dialoguetree.svg

Figure 4: Object diagram of a dialogue tree, at the leaves deliberation stopped.

We assumed that Jung meant that action generation was done by irrational functions, and preference ordering by rationale. What we did was giving all these functions the same type signature and then putting them into an order. This looked with the Haskell notation like the following: \[ \left (\overset{next}{B \to D \to (B, D)}\right ) \to B \to D \overset{f_a}{\to} (B, D) \] The next argument allows us to encode a sequence of functions, however this was problematic because I was asked to make operation in between functions available to the drools rule engine 4,1. We ended up with a hybrid approach where the functions were stored in a list and drools parsed them, but they could also be composed. Actually if I could change anything of the thesis it would be this part, it's kind-off messy right now, but I simply didn't have any more time left to figure this out properly.

jungjavaclass.svg

Figure 5: Jung in Java

How this looked in java can be seen in figure 5. The core is the enumeration of Jungian Functions, they all have the same type signature with JungFuncArgs as argument and result. These arguments can be modified by the functions and they can use apply next to apply the next function in the sequence to the arguments. This is only part of the story, not telling about how drools rules deal with the functions in order, but they are simply functions with as input JungFuncArgs and as output. Which means they are endomorphisms. I was tempted to put that in the title, because it sounds impressive, but then I realized it's just a minor part of my thesis, and I think that part is messy.

1.1.1 Steering

To steer dialogue two major methods are used. Feeling functions use perlocutionary values as directions, which is based upon speech act theory 5, and as an example can be seen in source block 7. The numbers used per perlocutionary value can differ per agent, their names can be attached to connections, see source block 8.

values:
  enthusiasm: 8
  polite: 5
from:
 - greeting
to:
 - symbol: greeting 
   values:
   - Polite
 - symbol: status
   restricted_to: patient
   values:
   - Polite
   - Enthusiasm

Thinking functions go primarily towards goals and can be seen in source block 9. What we do is marking that we want certain symbols to be uttered by a particular actor. In the example the patient want the doctor to utter "Have some painkillers". Goals are entirely encoded in the believes.

goals:
  - actor: doctor
    scene: diagnoses
    symbol: have_painkillers
  - actor: patient
    scene: information_gathering
    symbol: back_pain

To encode the personality we simply specify which Jungian functions we want in what order, see source block 10. In the thesis we specifically used MBTI 6 as a guide line, but the PPSDQ 7,8 and SL-TDI 9can also be represented like this. Although some work needs to be done to add scalar values they require.

# ENFP
personality: [Ne, Fi, Te, Si]

Finally we need to specify all actors, in case a connection didn't specify which actors are available, and we need to specify which actor the agent is. We need to do this because we model both sides of the conversation, so actors need to be specified explicitly, an example can be seen in source block 11.

self: patient
actors:
  - patient
  - doctor

With all of this in place the varied personalities can go over different modeled paths. Which is sort of what my thesis was about I guess. We did not specified values (unless you count perlocutionary values and goals), and the personality process will figure out what paths to take.

2 Crazy programming stuff

Ok ok, so now we have some context we can go to some of the more interesting parts (to me at least). I wasn't allowed to go into the details of the programming techniques I applied, but boy did I do some interesting things.

To bring you in the mood let's sketch the environment, I've been doing a lot of Scala, some Haskell and Rust before I started working on the thesis. The Salve game was written in Java, so guess what style I used for this typical Object Oriented programming language? Pure Functional! By this I mean that aside from local scope mutations, the entire structure was immutable. Take for example source block 12. We need to make the collections private because Java collections are mutable. There is no need for the name and scene attributes to become private because they are already immutable, so they will never change. We made hash_value private, even though it's immutable, because code shouldn't depend on that. This is a core principal of the code base, make everything immutable even though Java doesn't really cooperate with that.

@Immutable
public class Symbol {
	public final String name; // filename
	public final Scene scene;

	private final List<String> literals;
	private final Set<TemplateAttribute> requiredTemplateVars;

	private final int hash_value;
    ...
}

Ironically enough I undo this with the builder pattern in the unit tests. The issue is that immutability in Java is quite verbose to do, and I wanted a nice api to setup my the current dialogue on which I wanted to test the functions.

I also wanted to have a good api for modeling the scenario from java code in the unit tests, and especially for this one I think I've succeeded (see figure 13). We either connect up with any actor, or a restricted actor, however as you may see the result of these functions both go trough the same method connect. We do this by using an Either type, which allows us to treat the same information kind off similarly for a while, and eventually on the right place we treat the cases separately. It's kind off a delayed if statement. We can see the expansion of the if statement in figure 14, this happens with help of the fold method, which receives a lambda per either path. Of course there are other ways to do this1, but at the time of writing, I thought this was a really neat construct, because it's precise and terse. I'm not sure if it's a good or bad practice, but I think it looks interesting.

public class MockBelievesFactory {
	...
	public static final String hellos = "hellos";
	public static final String whyhere = "whyhere";
	public static final String maybeimsick = "maybeimsick";
	public static final String ilikevistingyou = "likevisitingyou";

	public static final String needmedicine= "needmedicine";
	public static final String imthedoctor= "imthedoctor";

	public final Believes createTestBelieves(){
		connect(hellos,
			any(whyhere, "Angry"),
			any(hellos, "Happy"),
			any(needmedicine, "Persuading", "Scary")
		);
		connect(whyhere,
			restricted(needmedicine, actor_patient, "Enlightening"),
			restricted(imthedoctor, actor_doctor, "Angry"),
			restricted(maybeimsick, actor_patient, "Angry"),
			restricted(ilikevistingyou, actor_patient, "Happy")
		);
		...
	}
	...
}
public class MockBelievesFactory {
	@SafeVarargs
	public final void connect(
		String one,
		Either<
			Pair<String, PerlocutionaryValueSet>, 
			Triplet<String, Actor, PerlocutionaryValueSet>
		>... values
	){
		Set<Connection> connections = createConnections(values);
		setconnect(one, connections);
	}

	@SafeVarargs
	public final Set<Connection> createConnections(
		Either<
			Pair<String, PerlocutionaryValueSet>, 
			Triplet<String, Actor, PerlocutionaryValueSet>
		>... values
	){
		return Arrays.asList(values).stream().map(tupple ->
			tupple.fold(
				pair ->
				createConnection(pair.getValue0(), actor_any, pair.getValue1()),

				tripple ->
				createConnection(tripple.getValue0(), tripple.getValue1(), 
				  tripple.getValue2())
			)
		).collect(Collectors.toSet());
	}
}

2.1 Fancy tree traversal

In many ways this structure was the core of deliberation. The Jungian functions needed to make modifications to this structure, but I wanted it to be immutable.

To modify an immutable tree we need to pass a function down to the node where we want to do the modification and then apply it, once this is done we can go back up the tree with the new modified tree as leaf passing as a result the new tree. The function that does this is withPrefferdIfAtHeight in source block 15. In this example we make heavy use of continuations to make a really terse tree traversal (at least for java). The copyWithAboveLeftMostLeaf and copyWithStartAtUntilLeaf are the main clients of this function, however they just fill in the continuations.

@Immutable
public class DialogueTree {
	public final Utterance utterance;
	public final Connection connectionUsed;
	private final List<DialogueTree> options;
	...
	/**
	 * If we have a preffered, execute withPrefferd on it, If we don't have,
	 * execute ifNoPrefferedWithThis on the current object.
	 */
	private DialogueTree mapPreffered(
		Function<DialogueTree, DialogueTree> withPreffered,
		Function<DialogueTree, DialogueTree> ifNoPreferedWithThis
	){
		final Optional<DialogueTree> prefferedOption = getOptions().findFirst();
		return prefferedOption.map(preffered -> {
			final List<DialogueTree> options =
				getOptions().collect(Collectors.toList());
			options.set(0, withPreffered.apply(preffered)); // 0 being preffered
			return replaceOptions(options);

		}).orElse(// there is no first option
			ifNoPreferedWithThis.apply(this)
		);
	}

	/**
	 * Generalization of 'copyWithStartAtUntilLeaf' and
	 * 'copyWithAboveLeftMostLeaf'
	 *
	 * You could very easily traverse the tree with this if you attach whenNot
	 * into the called function of the argument dialogueTree.
	 *
	 * Whenat will always be exeucted on the leaf.
	 */
	private DialogueTree withPrefferdIfAtHeight(
		int height,
		Function<DialogueTree, DialogueTree> whenNot,
		Function<DialogueTree, DialogueTree> whenAt
	){
		if(thisIsAtHeight(height)){ // in practice equal, but we just don't want stackoverflows
			// note return
			return whenAt.apply(this);
		}
		// we execute whenNot on preffered, because if we were at height the
		// previous condition woudl've been true
		// however if there is no prefered we are at leaf level.
		return mapPreffered(whenNot, whenAt);
	}

	/** go down until height, then keep applying function until leaf */
	public DialogueTree copyWithStartAtUntilLeaf(
		int height, 
		Function<DialogueTree, DialogueTree> function
	){
		if(height < leaf_height){
			return this;
		}
		return withPrefferdIfAtHeight(
			height,
			tree -> tree.copyWithStartAtUntilLeaf(height,function),
			tree -> {
				final DialogueTree result = function.apply(tree);
				return result.mapPreffered(
					prefferd -> prefferd.copyWithStartAtUntilLeaf(
						height, function),
					Function.identity()
				);
			}
		);
	}

	/** A more generalized form that can opperate on any height */
	public DialogueTree copyWithAboveLeftMostLeaf(
		int height, 
		Function<DialogueTree, DialogueTree> function
	){
		return withPrefferdIfAtHeight(
			height,
			tree -> tree.copyWithAboveLeftMostLeaf(height,function),
			function
		);
	}
	...
}

The tree traversal is extensively tested upon correctness by the unit tests aimed at the Jungian functions. This helped me a lot with coming with this design in the first place, because the unit tests would tell me if I did something different. I thought this example was interesting because of the use in continuations, I've never really done tree traversal like this aside from studying Haskell. I did find it really difficult to think of appropriate names for the continuation functions because they're so abstract. At this point I also started to wonder, are these kind off levels of abstractions even useful? I mean dialogue tree traversal became in my case really easy , I would say yes. This only happened after I implemented all the Jungian Functions and did a refactor round with the unit tests in place came I up with this design. I would imagine most code bases not really wanting to go this far.

2.2 Graph duality

This piece of code lingers on the point of madness..

Chatbot works modularized pattern matching called scenes. When a scene is active we only match upon patterns of symbols in that scene, if there are no such patterns we look at the connections going out to neighbouring scenes and match upon the patterns of the symbols leading to those.

To do this we have two pattern databases, the first one for within the scene and the second going out of the scene. The entire code that construct these databases can be seen in source block 16. We can see the first database be constructed in createSceneContained function. It just groups patterns based up their sybmols' scenes. The patterns then point to their respective symbol with help of PatternSymbol structure that is setup in the flatten function.

The second database is much more difficult. We need to go trough all the PatternSymbols and see if they came from any connections that transit scene, this is what the filter function does in the stream. To figure out in what scene to put this pattern symbol we create a different kind of connection database. This connection database has all the connections point in the opposite direction, we call this the dual. This idea just use a dual came from my geometric algorithm course, where they significantly reduced the complexity of an algorithm by converting points in lines and vice versa. The dual in this case does something similar, because if you call it twice you end up with the same structure.

The final step in both cases is constructing the hash map, this is used in a various places, therefore it was moved to the functions class.

public class PatternProcessing {
	public static PatternDatabase createSceneContained(
		Map<Symbol, Set<Pattern>> from
	){
		return new PatternDatabase(
			Functions.streamToHashMapSet(
				flatten(from),
				key -> key.symbol.scene,
				Function.identity()
			)
		);
	}

	public static PatternDatabase createSceneNextTo(
		Map<Symbol, Set<Pattern>> from, 
		ConnectionDatabase db
	){
		ConnectionDatabase dual = db.createDual();
		return new PatternDatabase(
			Functions.streamToHashMapSet(
				flatten(from)
				.flatMap(patternSymbol ->
					dual.getConnections(patternSymbol.symbol)
						.filter(connection ->
							!connection.to.scene.equals(
								patternSymbol.symbol.scene
							)
						)
						.map(connection -> 
							new Pair<>(connection.to.scene, patternSymbol)
						)
				),
				Pair::getValue0,
				Pair::getValue1
			)
		);
	}

	public static Stream<PatternSymbol> flatten(Map<Symbol, Set<Pattern>> from){
		return from.entrySet()
			.stream()
			.flatMap(entry ->
				entry.getValue().stream().map(
					pattern -> new PatternSymbol(pattern, entry.getKey())
				)
			);
	}
}

I really wanted to show the dual idea somewhere because I know this is a hard problem to solve, but it didn't take a lot of effort because of the dual idea. Not sure how readable this is though, this is a problem I have more often with functional programming.. How do you know what is a good or bad pattern? I guess I just need more experience or talk with other people about this.

2.3 Lazy hashing

The only reason I'm discussing this is because I worked with Java (Scala does the hashing stuff for you in case classes), and in some situations you did not want to calculate the hash code eagerly because the model object contained a collection (which could be a lot of work). I modified this stack overflow to work for hashing resulting in the code seen in source block 17. So what happens is as soon as the hashCode function is called we calculate it, and then replace the supplier hash with a new lambda that just returns the result. Note that this will never change because the model object is immutable.

@Immutable
public class Utterance {
	public final Informative informative;
	public final Instant when; // immutable
	public final CapturedMatchDB capturedDB;
	public final PerlocutionaryValueSet perlocutionaryValues;

	private Supplier<Integer> lazyHashValue;

	public Utterance(Informative informative, PerlocutionaryValueSet perlocutionaryValues, CapturedMatchDB capturedDB) {
		this.informative = informative;
		this.capturedDB = capturedDB;
		this.perlocutionaryValues = perlocutionaryValues;
		this.when = Instant.now();

		lazyHashValue = () -> {
			// since the class is immutable and we don't deal with collections,
			// we can calulate this now, if it every is required...
			final int hash_code =
				311 * informative.hashCode() -
				193 * this.perlocutionaryValues.hashCode() +
				701 * capturedDB.hashCode();
			lazyHashValue = () -> hash_code;
			return hash_code;
		};
	}

	@Override
	public int hashCode(){
		return lazyHashValue.get();
	}
	...
}

3 The experience

I specifically asked my teacher for getting a 'practical' assignment because I'm good at that. When he mentioned personality research I also opted into that, because I already knew a fair bit about MBTI. Finally, the personality as a process bit was all my teachers' suggestion, but I really liked that idea.

3.1 Doing research

When I started doing the thesis I was mostly on my own, my guiding teacher had left for Australia for 6 weeks, and I just started with what I think had to be done. I never had done before any research of this kind of scale so I just used common sense to decide what to do. However I made sure to keep my teacher up to date with weekly updates trough email.

The researching part consisted of several parts. First of all, the personality research with which I started, this was just ploughing trough papers on my own. Then came analyzing the chatbot, this was quite fun because it was just reverse engineering some poorly written code, which is challenging but also rewarding (I always get the idea I learn to know the author better by studying his code). Finally I needed to develop a theory of Jung and Dialogue, this was done mostly with the Haskell notation and giving my own interpretations of the Jungian functions. Then I also developed a way of combining them.

When my teacher came back I was mostly done with all of that. So he had a lot to catch-up with because I was writing my thesis while doing research. Even though I was thoroughly working for just six hours per day, he complemented me and said I had done a lot of work. I continued working just six hours per day.

3.2 Implementation

Once I was finished writing what I wanted to do in a functional design I started with the implementation. I quickly decided to not use the ALICE bot. It was poorly written, with for example many global mutable variables, frantic use of public mutable attributes and all the things you shouldn't do.

In the thesis I justify moving to the new system by saying that AIML doesn't offer the capability of providing choice, which is a much better reason that what made me look for alternatives in the first place. The first strike AIML got was by just being based upon XML, most programmers will know XML sucks (usually, there are good cases for XML). The reason I was pushed initially started looking for an alternative was because I didn't like the jury rigged combination of drools and AIML.

What I did was a quick implementation of how I envisioned the chatbot that could co-exist beside XML. I showed this to my programming guiding teacher after about two weeks of hacking, and he recommended me to just dump the old implementation and go with whatever I was making. He also pushed me to use drools much more intensively rather than java, which resulted in some good changes such as the pattern matching code becoming a drools rule, and some changes I like less such as the personality order being in both a list and the next function.

3.3 Presentation

I had way to much time to prepare for the preparation. Partly because one of the faculty members got a disease. But also because the primary guiding teacher was a very busy man and I had a long thesis.

I think I practiced the entire thing about 10 times in total. In the beginning I would often change the presentation after practicing but the presentation would become more final after each run. Each time I would be over time by a margin, however on presentation day itself I somehow managed to get exactly the right time. The difference probably is in stress level.

I don't remember giving the presentation, I know I stood there, said words, but I have barely any memories from the event. This usually happens to me when giving presentations, luckily my father filmed the entire thing. I was a little disappointed with the grade, but not too much, the criticism that I didn't add much theory was fair. However I think I couldn't do this much better because I just don't know how to develop theoretic foundations. This is partly because of my software engineering background, whereas the second judge was mostly from a mathematical background.

The questions I got were really quite though, firstly I was asked to describe precisely if a thinking function would be first in order, how would it still get to influence the result. The answer was that it just could inspect the result, because we have a two pass architecture, going deeper first. However because this is a very detailed question it took me a while to figure out what he meant by that. They also asked me about if the division between rational and irrational as action generation and sorting was a design decision, and yes it was. Then another question was about, can we extract the 'communicate!' game information from the GUI and encode it into the new game, what personality would the actor have in that game? I would say yes upon extraction (even automatic) but I didn't know what personality because I didn't study those dialogues (in fact I barely studied the communicate game). Finally a question was asked in which cases this would help doctors, I replied with the more emotional situations because it would be important to treat someone right under these cases.

4 Conclusion

I would say that I liked doing my thesis as a whole. In fact I would say I enjoyed the entire master, but I do know that I'm not an academic, my initial hasty assumption of "head in the clouds" was quite correct. The very notion of just always trying to do stuff in new approaches bothers me, I would rather just solve real world problem, with old approaches if they work, and do new approaches only when the use case demands it.

Then there is also the issue of neglecting to publish source code, I just think that is terrible for science as it creates a lot of double work and since I personally prefer digging around in source code I'm almost certain I work badly in academia. By which I mean it would just make me unhappy, I don't get excited by writing large bodies of text to the point of perfection. I just want to get out what is on my mind, release early release often rather than peer reviewed based academic releases. I choose the bazaar 10.

Bibliography

  1. Cimbora, Usability improvements of OptaPlanner Benchmarker, (2015).
  2. Hall & Nordby, A primer of Jungian psychology., Taplinger (1973).
  3. Campos, Dignum & Dignum, Modelling agent reasoning according to a pesonality type, , (2009).
  4. Drools documentation, (2016).
  5. Shoham & Leyton-Brown, Multiagent systems: Algorithmic, game-theoretic, and logical foundations, Cambridge University Press (2008).
  6. The Myers & Briggs Foundation -- Understanding MBTI Type Dynamics, (2016).
  7. Kier & Thompson, A New Measure of Jungian Psychological Types for Use in Counseling., , (), (1997).link. doi.
  8. King, Melancon & Thompson, Score Validation and Theory Elaboration of a Jungian Personality Measure., , (), (1999).link. doi.
  9. Arnau, Rosen & Thompson, Reliability and validity of scores from the Singer-Loomis Type Deployment Inventory, Journal of Analytical Psychology, 45(3), 409--426 (2000).link. doi.
  10. Raymond, The cathedral and the bazaar, Philosophy & Technology, 12(3), 23 (1999).link. doi.

Footnotes:

1
For example: let the any function also return the triplet but setting it to any actor
Liked this? Consider supporting me on patreon

Recent stuff

Tags