Multi-armed bandits with episode context

A multi-armed bandit episode consists of n trials, each allowing selection of one of K arms, resulting in payoff from a distribution over [0,1] associated with that arm. We assume contextual side information is available at the start of the episode. This context enables an arm predictor to identify possible favorable arms, but predictions may be imperfect so that they need to be combined with further exploration during the episode. Our setting is an alternative to classical multi-armed bandits which provide no contextual side information, and is also an alternative to contextual bandits which provide new context each individual trial. Multi-armed bandits with episode context can arise naturally, for example in computer Go where context is used to bias move decisions made by a multi-armed bandit algorithm. The UCB1 algorithm for multi-armed bandits achieves worst-case regret bounded by \(O\left(\sqrt{Kn\log(n)}\right)\). We seek to improve this using episode context, particularly in the case where K is large. Using a predictor that places weight M _i ?>?0 on arm i with weights summing to 1, we present the PUCB algorithm which achieves regret \(O\left(\frac{1}{M_{\ast}}\sqrt{n\log(n)}\right)\) where M _??? is the weight on the optimal arm. We illustrate the behavior of PUCB with small simulation experiments, present extensions that provide additional capabilities for PUCB, and describe methods for obtaining suitable predictors for use with PUCB.     

Refined modeling of sensor reliability in the belief function framework using contextual discounting

In belief functions theory, the discounting operation allows to combine information provided by a source in the form of a belief function with meta-knowledge regarding the reliability of that source, resulting in a “weakened”, less informative belief function. In this article, an extension of the discounting operation is proposed, allowing to use more detailed information regarding the reliability of the source in different contexts, i.e., conditionally on different hypotheses regarding the variable on interest. This results in a contextual discounting operation parameterized with a discount rate vector. Some properties of this contextual discounting operation are studied, and its relationship with classical discounting is explained. A method for learning the discount rates is also presented.     

An empirical evaluation of hierarchical feature selection methods for classification in bioinformatics datasets with gene ontology-based features

Hierarchical feature selection is a new research area in machine learning/data mining, which consists of performing feature selection by exploiting dependency relationships among hierarchically structured features. This paper evaluates four hierarchical feature selection methods, i.e., HIP, MR, SHSEL and GTD, used together with four types of lazy learning-based classifiers, i.e., Naïve Bayes, Tree Augmented Naïve Bayes, Bayesian Network Augmented Naïve Bayes and k-Nearest Neighbors classifiers. These four hierarchical feature selection methods are compared with each other and with a well-known “flat” feature selection method, i.e., Correlation-based Feature Selection. The adopted bioinformatics datasets consist of aging-related genes used as instances and Gene Ontology terms used as hierarchical features. The experimental results reveal that the HIP (Select Hierarchical Information Preserving Features) method performs best overall, in terms of predictive accuracy and robustness when coping with data where the instances’ classes have a substantially imbalanced distribution. This paper also reports a list of the Gene Ontology terms that were most often selected by the HIP method.     

Experimental evaluation of context-dependent collaborative filtering using item splitting

Collaborative Filtering (CF) computes recommendations by leveraging a historical data set of users’ ratings for items. CF assumes that the users’ recorded ratings can help in predicting their future ratings. This has been validated extensively, but in some domains the user’s ratings can be influenced by contextual conditions, such as the time, or the goal of the item consumption. This type of contextual information is not exploited by standard CF models. This paper introduces and analyzes a novel technique for context-aware CF called Item Splitting. In this approach items experienced in two alternative contextual conditions are “split” into two items. This means that the ratings of a split item, e.g., a place to visit, are assigned (split) to two new fictitious items representing for instance the place in summer and the same place in winter. This split is performed only if there is statistical evidence that under these two contextual conditions the items ratings are different; for instance, a place may be rated higher in summer than in winter. These two new fictitious items are then used, together with the unaffected items, in the rating prediction algorithm. When the system must predict the rating for that “split” item in a particular contextual condition (e.g., in summer), it will consider the new fictitious item representing the original one in that particular contextual condition, and will predict its rating. We evaluated this approach on real world, and semi-synthetic data sets using matrix factorization, and nearest neighbor CF algorithms. We show that Item Splitting can be beneficial and its performance depends on the method used to determine which items to split. We also show that the benefit of the method is determined by the relevance of the contextual factors that are used to split.     

Magic numbers in the state hierarchy of finite automata

A number d is magic for n, if there is no regular language for which an optimal nondeterministic finite state automaton (nfa) uses exactly n states and, at the same time, the optimal deterministic finite state automaton (dfa) uses exactly d states. We show that, in the case of unary regular languages, the state hierarchy of dfa’s, for the family of languages accepted by n-state nfa’s, is not contiguous. There are some “holes” in the hierarchy, i.e., magic numbers in between values that are not magic. This solves, for automata with a single letter input alphabet, an open problem of existence of magic numbers. Actually, most of the numbers is magic in the unary case. As an additional bonus, we also get a new universal lower bound for the conversion of unary d-state dfa’s into equivalent nfa’s: nondeterminism does not reduce the number of states below log² d, not even in the best case.     

Path-vector contracting: Profit maximization and risk management

We consider an Internet Service Provider’s (ISP’s) problem of providing end-to-end (e2e) services with bandwidth guarantees, using a path-vector based approach. In this approach, an ISP uses its edge-to-edge (g2g) single-domain contracts and vector of contracts purchased from neighboring ISPs as the building blocks to construct, or participate in constructing, an end-to-end “contract path”. We develop a spot-pricing framework for the e2e bandwidth guaranteed services utilizing this path contracting strategy, by formulating it as a stochastic optimization problem with the objective of maximizing expected profit subject to risk constraints. In particular, we present time-invariant path contracting strategies that offer high expected profit at low risks, and can be implemented in a fully distributed manner. Simulation analysis is employed to evaluate the contracting and pricing framework under different network and market conditions. An admission control policy based on the path contracting strategy is developed and its performance is analyzed using simulations.     

A polynomial algorithm testing partial confluence of basic semi-Thue systems

We give a polynomial algorithm solving the problem “is S partially confluent on the rational set R?” for finite, basic, noetherian semi-Thue systems. The algorithm is obtained by a polynomial reduction of this problem to the equivalence problem for deterministic 2-tape finite automata, which has been shown to be polynomially decidable in Friedman and Greibach (1982).     

A dynamic programming strategy to balance exploration and exploitation in the bandit problem

The K-armed bandit problem is a well-known formalization of the exploration versus exploitation dilemma. In this learning problem, a player is confronted to a gambling machine with K arms where each arm is associated to an unknown gain distribution. The goal of the player is to maximize the sum of the rewards. Several approaches have been proposed in literature to deal with the K-armed bandit problem. This paper introduces first the concept of “expected reward of greedy actions” which is based on the notion of probability of correct selection (PCS), well-known in simulation literature. This concept is then used in an original semi-uniform algorithm which relies on the dynamic programming framework and on estimation techniques to optimally balance exploration and exploitation. Experiments with a set of simulated and realistic bandit problems show that the new DP-greedy algorithm is competitive with state-of-the-art semi-uniform techniques.     

The Trouble with Common Ground

Tenenberg, Roth and Socha (2016) documents interaction within a paired programming task. The analysis rests on a conceptualization the authors term “We-awareness.” “We-awareness”, in turn, builds on Tomasello’s notion of “shared intentionality” and through it, upon Clark’s formulation of Common Ground (CG). In this commentary I review the features of CG. I attempt to show that neither Tomasello’s (2014) notion of “shared intentionality” nor Clark’s (1996) model of CG-shared develop an adequate treatment of the sequential emergence of subjective meaning. This is a critical problem for CG and other conceptualizations that build upon it (e.g., “shared intentionality”, “We-awareness”). And it calls into question their usefulness for building an analytic apparatus for studying mutual awareness at the worksite. I suggest that Schütz’s (1953) model of “motive coordination” might serve as a better starting place.     

An attribute-based ant colony system for adaptive learning object recommendation

Teachers usually have a personal understanding of what “good teaching” means, and as a result of their experience and educationally related domain knowledge, many of them create learning objects (LO) and put them on the web for study use. In fact, most students cannot find the most suitable LO (e.g. learning materials, learning assets, or learning packages) from webs. Consequently, many researchers have focused on developing e-learning systems with personalized learning mechanisms to assist on-line web-based learning and to adaptively provide learning paths. However, although most personalized learning mechanism systems neglect to consider the relationship between learner attributes (e.g. learning style, domain knowledge) and LO’s attributes. Thus, it is not easy for a learner to find an adaptive learning object that reflects his own attributes in relationship to learning object attributes. Therefore, in this paper, based on an ant colony optimization (ACO) algorithm, we proposed an attributes-based ant colony system (AACS) to help learners find an adaptive learning object more effectively. Our paper makes three critical contributions: (1) It presents an attribute-based search mechanism to find adaptive learning objects effectively; (2) An attributes-ant algorithm was proposed; (3) An adaptive learning rule was developed to identify how learners with different attributes may locate learning objects which have a higher probability of being useful and suitable; (4) A web-based learning portal was created for learners to find the learning objects more effectively.     

DynamiCITY: Revealing city dynamics from citizens social media broadcasts

Social media and mobile devices have revolutionized the way people communicate and share information in various contexts, such as in cities. In today’s “smart” cities, massive amounts of multiple forms of geolocated content is generated daily in social media, out of which knowledge for social interactions and urban dynamics can be derived. This work addresses the problem of detecting urban social activity patterns and interactions, by modeling cities into “dynamic areas”, i.e., coherent geographic areas shaped through social activities. Social media users provide the information on such social activities and interactions in cases when they are on the move around the city neighborhoods. The proposed approach models city places as feature vectors which represent users visiting patterns (social activity), the time of observed visits (temporal activity), and the context of functionality of visited places category. To uncover the dynamics of city areas, a clustering approach is proposed which considers the derived feature vectors to group people’s activities with respect to location, time, and context. The proposed methodology has been implemented on the DynamiCITY platform which demonstrates neighborhood analytics via a Web interface that allows end-users to explore neighborhoods dynamics and gain insights for city cross-neighborhood patterns and inter-relationships.     

The “book problem” and its neural correlates

Presence research can tell us why we feel present in the real world and can experience presence while using virtual reality technology (and movies and games) but has strikingly less to say on why we feel present in the scenes described in a book. Just how is it that the wonderful tangible detail of the real world or the complexity of digital technology can be matched and even surpassed by a story in a paperback book? This paper identifies a range of potential neurological solutions to this problem (and the “real world” and “dream” problems for good measure). We consider Jeannerod’s neural simulation of action, Grush’s emulation theory of representation and Rizzolatti’s work on mirror neurons as being candidate solutions to the “book problem”. We conclude by observing that these potential solutions further underline the “purpose” of presence is to act in the world whether it is real, virtual or solely in our imaginations.     

Security? Who’s Got Time For Security?: I’m Trying to Get my Job Done

What would you do if you were stuck in one place, and everyday was exactly the same, and nothing you did mattered?”Phil Connor, Ground Hog Day

“That about sums it up for me,” answered Ralph, and I’m sure most system administrators, information system security officers (ISSOs), physical security, operations security, and other security professionals would agree. Everybody takes them for granted — until the network goes down or applications can’t be used. And that’s the problem: a totally wrong perception of what’s required for the serious business of properly doing full spectrum security. Security is not something extra. Security is a normal part of doing business.     

HOPE: a hybrid deep neural model for out-of-town next POI recommendation

Next Point-of-interest (POI) recommendation has been recognized as an important technique in location-based services, and existing methods aim to utilize sequential models to return meaningful recommendation results. But these models fail to fully consider the phenomenon of user interest drift, i.e. a user tends to have different preferences when she is in out-of-town areas, resulting in sub-optimal results accordingly. To achieve more accurate next POI recommendation for out-of-town users, an adaptive attentional deep neural model HOPE is proposed in this paper for modeling user’s out-of-town dynamic preferences precisely. Aside from hometown preferences of a user, it captures the long and short-term preferences of the user in out-of-town areas using “Asymmetric-SVD” and “TC-SeqRec” respectively. In addition, toward the data sparsity problem of out-of-town preference modeling, a region-based pattern discovery method is further adopted to capture all visitor’s crowd preferences of this area, enabling out-of-town preferences of cold start users to be captured reasonably. In addition, we adaptively fuse all above factors according to the contextual information by adaptive attention, which incorporates temporal gating to balance the importance of the long-term and short-term preferences in a reasonable and explainable way. At last, we evaluate the HOPE with baseline sequential models for POI recommendation on two real datasets, and the results demonstrate that our proposed solution outperforms the state-of-art models significantly.

     

On the Possibility of Quantum Informational Structural Realism

In The Philosophy of Information, Luciano Floridi presents an ontological theory of Being qua Being, which he calls “Informational Structural Realism”, a theory which applies, he says, to every possible world. He identifies primordial information (“dedomena”) as the foundation of any structure in any possible world. The present essay examines Floridi’s defense of that theory, as well as his refutation of “Digital Ontology” (which some people might confuse with his own). Then, using Floridi’s ontology as a starting point, the present essay adds quantum features to dedomena, yielding an ontological theory for our own universe, Quantum Informational Structural Realism, which provides a metaphysical interpretation of key quantum phenomena, and diminishes the “weirdness” or “spookiness” of quantum mechanics.     

Classification using Hierarchical Naïve Bayes models

Classification problems have a long history in the machine learning literature. One of the simplest, and yet most consistently well-performing set of classifiers is the Naïve Bayes models. However, an inherent problem with these classifiers is the assumption that all attributes used to describe an instance are conditionally independent given the class of that instance. When this assumption is violated (which is often the case in practice) it can reduce classification accuracy due to “information double-counting” and interaction omission. In this paper we focus on a relatively new set of models, termed Hierarchical Naïve Bayes models. Hierarchical Naïve Bayes models extend the modeling flexibility of Naïve Bayes models by introducing latent variables to relax some of the independence statements in these models. We propose a simple algorithm for learning Hierarchical Naïve Bayes models in the context of classification. Experimental results show that the learned models can significantly improve classification accuracy as compared to other frameworks.