Mobile Recommenders and current challenges

Hi all,

It has been a while that I've been studying about recommendation engines and how can they be applied on mobile apps.   More and more data is exchanged between those platforms. Great examples of mobile apps that are using recommender engines are Google Hotpot  and Foursquare. They not only connect people to each other, but help users discover places around them.

Bizzy: A mobile recommender for Places

However, they only scratch the surface in this field, which is considered a novel research area in recommender systems. There are  several topics to be explored such as:

•  The location-based recommenders suggest items based on how far away we are from them (sometimes this can be manually changed). This could be a problem, if you consider the distance as the main factor for your recommender. Let me explain with an example. Imagine that you receive music concerts recommendations from your app around your in radius of 2km. When you're looking for live music, there's a band playing 1 km which will be recommended, but your favorite band, which is playing 2.1 km aways, will be out of the final list. And worst, if my  favorite band will play tomorrow and I am at home looking for recommendations, it won't be suggested in this case because of the distance.  It is necessary those systems to consider our habits in order to provide recommendations based on the most checked-in places that I visit (one possibility).

• The mobile recommenders must consider the context where the users are inserted. However the recommenders currently must receive what people are looking for, before receiving the suggestions. Wouldn't be interesting to consider the time events or even the historical habits ? Are those factors enough ?

•  The information about the location and place (content) is also important in the recommendation computation. Imagine you exploring places around you at Foursquare and there are trending places around you (lot's of people there). This recommendation will be received considering only distance ? It is necessary to consider the temporal information associated to the place.

• Just because I've been many times at the Nipon's Sushi , it doesn't mean that I don't want to receive the recommendation again. The process of discovery and re-discovery is important either. The current systems, in general, don't consider the user's familiarity with the locations the user frequent.

• Venues are venues. Events are the "main" item interested by the user, not the venue. Ok, I like receiving a recommendation of a place, but sometimes I'd like to know what's happening there. Furthermore, the current check-ins and rating systems reflect what's happening now, but not what I am planning in the future. The discovery process and prediction decision are main important issues when you're designing a mobile recommender, specially dealing with temporal short-life like events.

• Noisy data. Recommendations of "my apartment", "my mother house". Recommendations can suffer with those types of places.

•  How do we collect the data ? It will be by check-ins, 5 *scale ? Or passive using GPS ? This brings issues about the recommendation interface and how the data will be influenced by the social-signalling noise.

• Some systems use the user's search history to recommend places. This can be noisy, considering that sometimes that what the user searches online often do not match what the user needs when he wants to go out. Just because I looked for information about the Recife airport, it does mean that I'd like to receive airport recommendations.  The point is: the relevance of places that you search for online doesn't match places that you would like to discover in the real world.

Those are some of several challenges faced by mobile recommenders. Mobile recommender systems are still growing and there's lots of research around it.  But one important observation to make is that the best techniques for recommenders in the web sometimes are not suited for mobile recommenders. It's required that the recommendation designer be able to balance between the distance and the preferences from the user and the related items, understand the context where the user is inserted and help him to discover and re-find places and events hidden in his city!

There will be a workshop during the ACM Recommender Systems 2011 about mobile recommenders. Unfortunately this year I won't be attending , but it is on my plans! By the way, you still can submit your paper until July's 25th!

PS: I've found this great blog about mobile recommendations and mobile data mining : Urban Mining. I recommend!

PS2: Recommended reading about why people check-in. An interesting research about why people are interested in checking-in mobile applications.

I hope you enjoyed this article,

Marcel Caraciolo

DiagnostiCar (3) - Question & Answer Interface

This post aims to explain how to create an interactive shell so that users may answer questions when the reasoning system need user information. The reasoning engine will access the ask engine by an predicate (I will call it ask). An naive implementation of the ask predicate could be:

ask(X) :-
 write(X), write(' is true?'), nl,
 read(yes).

It works, but askable predicates will be asked every time the reasoner will need an information, even if it was previously answered. Another specific problem from DiagnostiCar constraints, was how to separate which information is from which user, considering we're at an web application environment. The simultaneous users access to the reasoning engine couldn't simply be locked while an user was giving an answer back, so we must find a smarter way to ask.

To remember info in Prolog, we will need to use dynamic relations to store the asked questions, for those who don't know about dynamic relations I will give a short explanation. If you want to know more, read the "Building Expert Systems in Prolog"[1] book.

Dynamic relations works similarly as a relational table in a relational database [2], but without a type scheme (although it's strongly recommended to make a convention). The informations required to create a dynamic relation are just it's name and arity. To declare a dynamic predicate you just need to run dynamic(Predicate). Once the relation is a dynamic one, you can store information (assert/1 or asserta/1) or delete information (use retract/1 and retractall/1) eg.: assert(foo(bar)). To query a dynamic predicate you just have to call it (it allows unification!) eg.: ?- foo(bar).  -> true. I made the following basic but illustrative example about Prolog DB:

create_account(Id, Ammount) :-
    assert(account(Id, Ammount)).
    
deposit(Id, Ammount) :-
    retract(account(Id, PrevAmmount)),
    NewAmmount is Ammount + PrevAmmount,
    assert(account(Id, NewAmmount)).
    
withdraw(Id, Ammount) :-
    account(Id, PrevAmmount),
    PrevAmmount >= Ammount,
    retract(account(Id, PrevAmmount)),
    NewAmmount is PrevAmmount - Ammount,
    assert(account(Id, NewAmmount)).

To test the predicates do some queries:

?- create_account(1, 1000).
true.

?- deposit(1, 200).
true.

?- account(Id, Ammount).
Id = 1,
Ammount = 1200.

?- withdraw(1, 400).
true.

?- withdraw(1, 20000).
false.

?- account(Id, Ammount).
Id = 1,
Ammount = 800.

The best solution found, to solve the concurrence and the question tracking, was to create predicates to read and write, so the webapp could obtain such information from the expert system. To avoid repeating the same questions, we will have to maintain a table with questions made, one with the answered questions and another to keep the answers from the users. Note that each relation needs to keep an user id to know from which user each information belongs to. The expert system question interface is the following:

% asked: UserId | Question
:- dynamic asked/2.
% asked: UserId | Question
:- dynamic askfor/2.
% known: UserId | Question | Fact
:- dynamic known/3.

% Predicate used by the expert system to ask.
ask(Uid, Question, Answer) :-
    known(Uid, Question, Answer).
ask(Uid, Question, _ ) :-
    not(asked(Uid,Question)),
    not(askfor(Uid,Question)),
    assert(askfor(Uid, Question)),
    fail.

% Predicate used by the web app to input users answers for a given qeustion.
answer(Uid, Question, [Answer | Answers]) :-
    assert(known(Uid, Question, Answer)),
    answer(Uid, Question, Answers).
answer(Uid, Question, []) :-
    assert(asked(Uid, Question)),
    retractall(askfor(Uid,Question)).

% Routine called by the webapp to clean the data from a user whose 
% session was expired.
cleanup(Uid) :-
    retractall(askfor(Uid,_)),
    retractall(known(Uid,_,_)),
    retractall(asked(Uid,_)).

Not that hard! I will try to tell all about the abductive reasoning on the next post.

[1] "Building Expert Systems in Prolog"

[2] SWI Database

Keynote about Recommender Systems at CIN- UFPE

Hi all,

I'dl like to share my presentation about recommender systems that I lectured at the Federal University of Pernambuco (UFPE) .  It was an introduction for who wants to know more about this machine learning research field as also my contributions to this area.

Sistemas de Recomendação e Inteligência Coletiva

View more presentations from Marcel Caraciolo

One of them is the development of the framework for building recommender engines written in Python called Crab.  Soon I will release more information and a paper that I wrote about the framework to submit to Scipy 2011 Conference.

Stay tuned!

Regards,

Marcel Caraciolo

DiagnostiCar (2) - Knowledge Representation Language

I'm giving sequence to the last post about the DiagnostiCar expert system. Today I'm going to specify the predicates to represent some domain specific knowledge.

Prolog has a helpful and clean syntax [1] (at least when you're used to :P) and it's easy to define new operators syntax in SWI [2]. Such feature improves the readability of the knowledge base.

To make an abductive reasoning we will need at least the logic operators 'and','or' and 'implies' to represent knowledge and chain it.

Our simple language will have the following syntax:

• known X. - Says that the sentence X must be true;
• X <- Y - X is caused by Y;
• X & Y - Is true if X and Y are true;
• X v Y - Is true if X or Y are true ('|' is already used by Prolog);
• assumable X - X can be assumed to prove something;
• askable X - X can be asked to the user;

Note that I'm not using the negation, because some dangerous particularities of Prolog negation as failure.

It's interesting to note the similarity if we represented with the defaul prefixed notation of Prolog predicades:

- known(X)
- <-(X,Y)
- &(X,Y)
- v(X,Y)
- assumable(X)
- askable(X)

Defining opertors increases the readabilty of the knowledge representation significantly. To redefine operators we will use the SWI predicate op/3 [2]. We can only run this predicate like:

:- op(910, xfy, &).

The op predicate has three fields op(+Precedence, +Type, :Name). The first one says the precendence of the operator (a number between 0 and 1200). The second is how the functor will be placed within it's "children nodes", for example: xfy let the functor between the arguments while xf let the functor after it's argument (remembering that you can only create unary or binary operators). For our representation language we will have:

:- discontiguous(     known/1 ). % The discontiguous predicate tells Prolog
:- discontiguous( assumable/1 ). % that the given predicate can be declared
:- discontiguous(   askable/1 ). % unsorted.

:- op(910, xfy,      &    ). % a higher priority with an infix notation
:- op(920, xfy,      v    ). % infix notation and lower priority than &
:- op(930, xfy,     <-    ). % infix notation
:- op(940,  fx,   known   ). % prefixed notation and lowest priority
:- op(940,  fx, assumable ). % prefixed notation and lowest priority
:- op(940,  fx,   askable ). % prefixed notation and lowest priority

Now let's model the car problems knowledge into our language (remember that Upper names are variables):

%
% DiagnostiCar - Knowledge Base
%

% Observe that implication is seen as the real sense of consequence <- cause.
known problem(crank_case_damaged) <- crank_case_damaged.
known problem(hydraulic_res_damaged) <- hydraulic_res_damaged.
known problem(brakes_res_damaged) <- brakes_res_damaged.
known problem(old_engine_oil) <- old_engine_oil & leak_color(black).

known leak(engine_oil) <- crank_case_damaged.
known leak(hydraulic_oil) <- hydraulic_res_damaged.
known leak(brakes_oil) <- brakes_res_damaged.

% Implications in false can be seen as constraints.
known oil(Oil) <- exists_leak(true) & leak(Oil).
known false <- oil(brakes_oil) & leak_color(Color) & Color \= green. 
known false <- oil(engine_oil) & leak_color(Color) & Color \= brown & Color \= black.
known false <- oil(hydraulic_oil) & leak_color(Color) & Color \= red.

% The assumable predicate asserts what will be can be suposed 
assumable crank_case_damaged.    
assumable hydraulic_res_damaged. % to prove something e else.
assumable brakes_res_damaged.
assumable old_engine_oil.

askable leak_color(Color). % Askable predicate asserts which information will be asked for the user.
askable exists_leak(TrueOrFalse). % The argument of the predicate will be unified with the answer.

known goal(X) <- problem(X). % The goal predicate is what we want to prove with the expert system.

That's all for now. On the next post I will explain the question and answer interface using the dynamic Prolog predicates.

[1] Prolog Syntax

[2] Prolog 'operator/3' documentation

DiagnostiCar (1) - Introduction

I'm here today to tell my expirience with logic programming on a graduation project - DiagnostiCar.

The DiagnostiCar core feature was an expert system for giving hints to laypeople about their cars symptoms and their causes and consequences to avoid being deceived by mechanics (an habit of the job). Communication between the system and the users was conceived to happen with multiple choice questions forms and at the end the system gives the possible causes for the observed car characteristics.

This is a video of the DiagnostiCar expert system interface working:



Although there are many other interesting aspects about the DiagnostiCar, let's focus on the shell system. The expert system reasoning system used was abductive reasoning which is a kind of reasoning that tries to find a plausible cause (or a set of them) for a given fact occurrence [1][2]. Find the causes for a given observation is exactly what we need for diagnose car problems (the cause of the observable symptoms).

I choose to use Prolog not only because it's default support to first-order logic (although some logic limitations on negation [3]), but it has a nice support for pattern matching and syntax operator definition (most of the Prolog implementations). From the Prolog implementations I've picked SWI Prolog due to it's multi-thread support (necessary for a system running on a multiple user environment), stability and speed (not as fast as the YAP) [4].

To illustrate the process of development of the expert system we will restrict our diagnosis to the problems consisting of some oil leaks problem. Here are some of the knowledge about car diagnosis I will use as example in the next sections:

• A crank case, hydraulic oil reservoir and brakes fluid reservoir damaged are problems;
• The crank case damaged provokes leak of engine oil;
• The hydraulic reservoir damaged provokes leak of hydraulic system oil;
• The brakes fluid reservoir damaged provokes leak of engine oil; 
• If an oil is leaking it dirts the garage's floor.
• The brakes fluid is green.
• The hydraulic oil is red.
• The engine oil is black or brown.
• If the engine oil is black, then it needs to be changed.

For the next parts, it's good to know the basic about Prolog. A VERY good material about Prolog, it's a the book "Building Expert Systems in Prolog"[5] which guided through the realms of logic programming and the nasty api's documentations. It is also very pratical and full of examples to follow. It's also good see the SWI reference to check some SWI particularities[6].

[1] Abductive Logic Programming
[2] Abducive Reasoning
[3] Prolog Negation as Failure
[4] Prologs Implementation Comparisons
[5] "Building Expert Systems in Prolog"
[6] SWI Manual