Click Shaping to Optimize Multiple Objectives

by Deepak Agarwal, Bee-Chung Chen, Pradheep Elango and Xuanhui Wang

Some properties have quite different business requirement other than purely CTR, because e.g. portals may serve as traffic direction to other properties. Therefore we usually have several metrics in mind. In this paper,  there are three objectives in discussion: total clicks, total time spent, average time spent. The first one may be seen as the traditional way, which optimizes the current page while the other two are metrics for downstream pages.

Therefore we have several ways of combining them:

• linear combination, which may be seen as the linearization of the Pareto optimal
• goal programming, which maximizes downstream metrics while put a linear constraints on CTR (no worse than a given value, obtained a priori)
• localized multi-objective program, which maximizes the minimum ratio of downstream property loss (compared to CTR maximization scheme), subject to CTR constraints. This is convex but not differentiable. With some trick, it may be turned into a quasi-convex optimization problem and solved via be-section algorithm
• a relaxed version of localized multi-objective program, which maximizes the downstream metric, subject to the CTR constraint and downstream constraint (no less than the original)

The experiments can only be carried out on segments of users and some of the down stream properties must be estimated a priori. The result shows a slightly sacrifice of CTR may lead to comparatively higher increase in downstream properties.

Integer Programming for Multi-class Active Learning

by Dragomir Yankov, Suju Rajan and Adwait Ratnaparkhi

This paper proposed an integer programming based method for active learning in multiclass discriminative tasks. The idea is to select enough samples for each one-vs-rest SVM based on margin-distance uncertainty and we hope especially those may contributed to more classifiers are encouraged. That's for each sample we put an indicator saying whether it is selected as training. The constraints are for each classifier, the selected samples must be enough (according to the rank of uncertainty, we take a little more than required candidates so that this constraint may be satisfied). This is solved by feasibility pump (implemented by lpsolve).

Online Models for Content Optimization

by Deepak Agarwal, Bee-Chung Chen, Pradheep Elango, Nitin Motgi, Seung-Taek Park, Raghu Ramakrishnan, Scott Roy, Joe Zachariah

This is something very detailed for how Yahoo!'s today module is optimized for overall CTR. Internally the project was first named COKE but later rebranded as CORE (content optimization and relevence engine).

Here I only include some key points from the paper. Overall, the paper is written in a very succinct way and worth your time.

• mini batch learning in 5 minute segs;
• online models to track CTR including EMP, SS and OLR
• E&E setting with a random bucket

Let's take a look at the modelling part. Strangely still, I am very clear about the OLR part:

• it is a Bayesian version of logistic regression, Gaussian prior on parameters
• approximate inference with Laplace approximation scheme
• it may be simplified with uncorrelation assumption but the performance will suffer;

As for EMP and SS, SS is simply user-segmented EMP, i.e. building several EMP for each user segment. EMP looks like a Kalman filter (LDS) which I will take a detailed look soon.

Image Saliency: From Intrinsic to Extrinsic Context

by Meng Wang, Janusz Konrad, Prakash Ishwar and Kevin Jing, Henry Rowley

The method contains three steps:

• by kNN, the given image's saliency is computed from the images in the dictionary (global or patch by patch basis);
• a warping algorithm helps to align the kNN to the original image/patch
• the saliency is the reconstruction error

The idea is to find those part of the image that can't be explained by its neighbors (i.e. might be salient enough to catch your attention).

We may use an extra dictionary or we may simply split the image into patches.

Enhancing by Saliency-guided Decolorization

by Codruta Orniana Ancuti, Cosmin Ancuti and Phillipe Bekaert

This paper talks about a de-colorization method (maybe useful for de-saturating photos?). The basic idea is quite simple: the ultimate luminance is the original one multiplied by a coefficient that is defined by hue and saturation. There are certain tuning for the highlighted regions. I just got a simple experiment with OpenCV. But it doesn't work very well...

Frequency-tuned Salient Region Detection

by Radhakrishna Achanta, Sheila Hemami, Francisco Estrada, and Sabine Su ̈sstrunk

This is a very simple paper. The idea is to blur the image a little (with Gaussian) and compare the distance of each pixel to the mean. With this saliency map, DoG can be applied to extract the edges.

This method will fail if the object has many colors or the background is complex.

AppJoy: Personalized Mobile Application Discovery

by Bo Yan and Guanling Chen

This paper introduces the author's app AppJoy, which collects users' usage of apps on a mobile device, derives the similarity scores between apps based on the usage and recommend apps based on similarity scores. The idea is to utilize the time and spatial information along with the apps. Contrastive to other recommendation algorithm, based on ratings, the app usage may serve as a much better feature. I guess this shows a simpler model with strong feature might serve better than a complicated model with weak features.

It seems that, if we decide to move on to applications in mobile devices, we'd better get to know the details of the mobile platforms. E.g. IOS might not allow you to collect such usage information. So the experiments can only be done on Android.

DOT: A Matrix Model for Analyzing, Optimizing and Deploying Software for Big Data Analytics in Distributed Systems

by Yin Huai, Rubao Lee, Simon Zhang, Cathy H. Xia and Xiaodong Zhang

I heard the talk in HIC 2011 but hardly knew what this paper is about. After reading the paper for a while, I realized that the author just formulates the jobs in a distributed system with a so-called DOT expression, i.e. data (row vector), operator (several column vectors) and transformation (another function on aggregated output of operators). Therefore a matrix-like expression can be formulated this way. Apparently Map/Reduce and dryad jobs can be formulated with it.

The authour discussed a little bit about the property of DOT formulation but I think they are way behind math. I don't see any necessity in formulating those jobs with this strange expression. The algebra also doesn't reveal anything appealing. Maybe I am wrong. After all I am not in that field.

Dryad: Distributed Data-Parallel Programs from Sequential Building Blocks

by Michael Isard, Mihai Budiu, Yuan Yu, Andrew Birrell and Dennis Fetterly

Dryad is kind of lower-level computational model than MapReduce. The programmer has to write a DAG for a specific task. The programmer implements the job details on each vertex and defines what kinf of edges that connect the vertices. In this way, the programmer first decomposes the tasks into a DAG. The commonly seen parallelization of splitting data has to be done manually or by some library to read data from a GFS like distributed storage. There is no shuffling like in reduce step. So programmer has to build his own for this type of operation (or dryad's library has such implementation). The comminication (i.e. the edges) can be fine tuned by the programmer, like a TCP pipe or a temporary file.

On a whole dryad provides a lower level of computational model, on top of which other computational models (like Map/Reduce) can be built. But it also raises bar for its users. I don't think MS will open source for dryad and this is MS's style. Proprietary software, limited community...

Spark: Cluster Computing with Working Sets

by Matei Zaharia, Mosharaf Chowdhury, Michael J. Franklin, Scott Shenker and Ion Stoica

Spark uses a so-called RDD (resilient distributed dataset) for data intensive operations, like iterative machine learning algorithms, which reduces repeated IO of MapReduce. Similar parallel operations like map, reduce, collect and foreach are defined. Reduce is even simpler (only associative operator, like plus). The dataset will be held in memory as long as the job is not finished. Parameterized models, when parammeters can be stored in memory, will surely benefit from this design.

Swing or not to Swing: Learn When (not) to Advertise

by Andrei Broder, Massimiliano Ciaramita et al.

This paper talks about how to learn to show the ads or not in some cases. The basic idea is to learn a classification model based on candidate sets's features, like relevance feature, cohesiveness features. This is compared to a thresholding method, which can be trivially obtained via commonly used retrieval system of ads and proved more effective when our goal is not to maintain a high recall rate (therefore the more the better case).

Another idea is to train the model based on click feedbacks instead of editorial judgement. The paper mentioned to use online learning techniques, which is the reason that most online serving models has to take into account of the time-evolving property and allows the model to be trained in an incremental style.

Impedance Coupling in Content-Targeted Advertising

by Berthier Ribeiro-Neto, Marco Cristo, Paulo B. Golgher and Edleno Silva de Moura

This paper talks about an expansion of keywords in a webpages by using similar webpages. By this expansion, the retrieval of related ads can be improved. It is different from another idea, that is, the expansion set is mined from search engine.

The basic model is Bayesian belief net, where for each document D₀, we take its most similar pages D_k and create links from the doc to its related terms. Originally, the doc's related terms are sparse when used in retrieval (due to vocabulary impedance problem). But with similar pages, the candidate sets get enlarged but still we need to select which are good for the current page. Take Pr(D_i) as constant, and the conditional probabilities Pr(R | D_i) as some function related to the similarity to D₀ and Pr(T_j | D_i) as some normalized term frequencies. We may evaluate Pr(T_j | R) for each document as a ranking score to choose the corresponding term.

Review Spotlight: A User Interface for Summerizing User-Generated Reviews Using Adjective-Noun Word Pairs

by Koji Yatani, Michael Novati, Andrew Trusty and Khai N. Truong

This is an interesting HCI paper on showing interviews in the form of adj.+ n. form. The sentiment analysis shows the positiveness and negativeness of each mined structure, which renders the color of the phrases. The sizes can be determined by the popularity of the phrases. The interface helps the user get better impression on the product of interest. The layout of the phrases are not very important. When the mouse hovers the selected phrases, the corresponding reviews will be listed (maybe with a smart summary?).

In a way, this interface has similarity in word/tag clouds but do has very reasonably advantageous edges. Shall we implement one for some projects?

SIGIR 2011

This time it is in Beijing.

Tutorials

I'd say most of them are quite elementary:

• one tells machine learning techniques for IR;
• another talks about online algorithm, which is the now trending topic in ML;

Keynotes

It is quite general but should be interesting enough.

Papers

Not sure about the content. No online proceedings. Not sure we may go there and listen to some of the talks.

Workshops

Some of them look interesting:

• query session
• entity oriented search

Hope I may sneak in.

Like like alike---Joint Friendship and Interest Propagation in Social Networks

by Shuang Hong Yang, Bo Long, Alex Smola, Narayanan Sadagopan, Zhaohui Zheng and Hongyuan Zha

This paper extends the idea of RLFM: we interpret RLFM with a supervised learning problem and this paper extends this idea with a social net, mainly via regularizers. So that's why the probabilistic model in RLFM may not be that important (just an interpretation in a disciplined way). There are 7 regularizers in total, which leads to a very complicated objective function.

The optimization is solved via stochastic gradient descent. Maybe for other techniques like interior point method, it is too difficult to derive?

Regression-based Latent Factor Models

by Deepak Agarwal and Bee-Chunh Chen

This paper talks about another way of using the rating matrix.

Given features of users and items, there are some correlations between them. The CCA idea is ``unsupervised'' since it works on two kinds of data and finds the maximum correlations without further ``supervised information.'' Then if indeed we have some ``supervised'' information, that is how correlated a user is to some items, the problem becomes a ``supervised learning'' version. Actually, most of the literatures are in this style. Haha, you might have realized my point now: is there any ``semi-supervised'' version? Yeah, I'd like to develop one :-)

OK, let's go back to this paper. So with supervised information, the problem of CCA becomes finding two linear mapping of user's feature and item's feature into a common subspace, so that their inner product approximates the given one. This might be problematic, since obviously the ratings might be non-consistent with their relative face values. But anyway we have this basic idea: it's like what we get in PCA.

The second step is to make some probabilistic model out of it (PCA to PPCA) so that everything gets some interpretation and a disciplined way to train the model and making inferences. The paper shows us an interpretation: there is a common subspace that each user/item is drawn from (zero mean, some variance?), which can be obtain from the original feature space (via a linear transformation). The observed rating can be seen as the inner product mixed with a noise. With this graphical model, we may do the learning via EM. Here the authors chose the MCEM (MC to compute the expectation).

Let's try some of the ideas.

Inferring Rlevent Social Networks from Interpersonal Communication

by Munmum de Choudhury, Winter A. Mason, Jake M. Hofman and Ducan J. Watts

The paper makes a point that the social nets are not really totally usable by its original form. We usually have to remove some edges by a certain extent for a specific tasks. My thought on this is like the social edges are like aqueduct or wires. Different behaviors have different propagation coefficients.

Another important thing in this paper is those features, in three categories:

• reach
  • node degree
  • average neighbor degree
  • size of two-hop neighborhood
• closure
  • embeddedness, an average of ratios of common friends over or-friends;
  • normalized clustering coefficient, the average probability of two of my neighbors are friends
• bridge
  • network constraints (sum of all neighbors, each inner producted with the node)
  • ego components (after removal, how many new components will appear)

Sentiment Analysis with Global Topics and Local Dependency

by Fangtao Li, Minlie Huang and Xiaoyan Zhu

This paper talks about the interaction between topic and sentiment. The first idea is to impose an additional factor of generating word: the topic decides the sentiment and the sentiment along with the topic decides the word. However, the structure can't determine where the writer changes his attitude. So they impose a hidden Markov structure on sentiment transitions. However the paper only gives some inference result and many parameters are manually set.

An Efficient Method For Compressive Sensing

by Seung-Jean Kim, Kwangmoo Koh, Michael Lustig and Stephen Boyd

This paper talks about how the interior point method is applied in L1 regularized least squared problem. The dual serves as an estimation of the duality gap, which then becomes the convergence judgement. The log barrier method formulates the primal objective function, which is solved by Newton's method. The Newtons's method requires solving a linear system, which addressed by conjugate gradient. The accuracy of the solution can be adjusted as the search evolves.

On a single machine this method may deal with millions of variables, in compressive sensing problems.

Near-Optimal Hashing Algorithms For Approximate Nearest Neighbor in High Dimensions

by Alexndr Andoni and Piotr Indyk

This is a survey paper on locality-sensitive hashing (LSH). LSH is quite useful for approximately retrieving similar items according to a given distance. The fact is, once we have enough data, those approximate nearest neighbors would perform as well as extact ones. So why bother computing the exact version?

The idea is based on stochastic algorithms in common literatures. The idea is to select a random projection and combine the binning to the final hash table. To understand intuitively how this works, given a point, the random projection into one bin will cut down the probability the retrieved points are not around the query by some extent. And when more projections are made, we get closer. E.g. for Hamming distance, the projection can be further simplified as a subset of randomly chosen coordinate indices.

There are some software implementing this LSH idea. I would like to try them in the following days.