Catalog footprint

What is connected

37works
22topics
4close collaborators

Actions

Connect this record

Log in to claim

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

37 published item(s)

preprint2026arXiv

Scalable Learning in Structured Recurrent Spiking Neural Networks without Backpropagation

Spiking Neural Networks (SNNs) provide a promising framework for energy-efficient and biologically grounded computation; however, scalable learning in deep recurrent architectures with sparse connectivity remains a major challenge. In this work, we propose a structured multi-layer recurrent SNN architecture composed of locally dense recurrent layers augmented with sparse small-world long-range projections to a readout population. The long-range connectivity is largely fixed, preserving routing efficiency and hardware scalability, while synaptic adaptation is performed using strictly local plasticity mechanisms. To enable supervised learning without backpropagation or surrogate gradients, we introduce a biologically motivated learning framework that combines: (i) population-based winner-take-all (WTA) teaching signals at the output layer, (ii) fixed random broadcast alignment feedback pathways, and (iii) low-dimensional modulatory neuron populations that gate synaptic updates through three-factor learning rules with eligibility traces. This design supports deep recurrent computation with sparse global communication and purely local synaptic updates. We analyze the algorithmic properties, computational complexity, and hardware feasibility of the proposed approach, and demonstrate stable learning and competitive performance on benchmark classification tasks. The results highlight the potential of structured recurrence and neuromodulatory learning to enable scalable, hardware-compatible SNN training beyond gradient-based methods.

preprint2025arXiv

xVerify: Efficient Answer Verifier for Reasoning Model Evaluations

With the release of OpenAI's o1 model, reasoning models that adopt slow-thinking strategies have become increasingly common. Their outputs often contain complex reasoning, intermediate steps, and self-reflection, making existing evaluation methods and reward models inadequate. In particular, they struggle to judge answer equivalence and to reliably extract final answers from long, complex responses. To address this challenge, we propose xVerify, an efficient answer verifier for evaluating reasoning models. xVerify shows strong equivalence judgment capabilities, enabling accurate comparison between model outputs and reference answers across diverse question types. To train and evaluate xVerify, we construct the VAR dataset, which consists of question-answer pairs generated by multiple LLMs across various datasets. The dataset incorporates multiple reasoning models and challenging evaluation sets specifically designed for reasoning assessment, with a multi-round annotation process to ensure label quality. Based on VAR, we train xVerify models at different scales. Experimental results on both test and generalization sets show that all xVerify variants achieve over 95% F1 score and accuracy. Notably, the smallest model, xVerify-0.5B-I, outperforms all evaluation methods except GPT-4o, while xVerify-3B-Ib surpasses GPT-4o in overall performance. In addition, reinforcement learning experiments using xVerify as the reward model yield an 18.4% improvement for Qwen2.5-7B compared with direct generation, exceeding the gains achieved with Math Verify as the reward. These results demonstrate the effectiveness and generalizability of xVerify. All xVerify resources are available on \href{https://github.com/IAAR-Shanghai/xVerify}{GitHub}.

preprint2023arXiv

RL-MPCA: A Reinforcement Learning Based Multi-Phase Computation Allocation Approach for Recommender Systems

Recommender systems aim to recommend the most suitable items to users from a large number of candidates. Their computation cost grows as the number of user requests and the complexity of services (or models) increases. Under the limitation of computation resources (CRs), how to make a trade-off between computation cost and business revenue becomes an essential question. The existing studies focus on dynamically allocating CRs in queue truncation scenarios (i.e., allocating the size of candidates), and formulate the CR allocation problem as an optimization problem with constraints. Some of them focus on single-phase CR allocation, and others focus on multi-phase CR allocation but introduce some assumptions about queue truncation scenarios. However, these assumptions do not hold in other scenarios, such as retrieval channel selection and prediction model selection. Moreover, existing studies ignore the state transition process of requests between different phases, limiting the effectiveness of their approaches. This paper proposes a Reinforcement Learning (RL) based Multi-Phase Computation Allocation approach (RL-MPCA), which aims to maximize the total business revenue under the limitation of CRs. RL-MPCA formulates the CR allocation problem as a Weakly Coupled MDP problem and solves it with an RL-based approach. Specifically, RL-MPCA designs a novel deep Q-network to adapt to various CR allocation scenarios, and calibrates the Q-value by introducing multiple adaptive Lagrange multipliers (adaptive-$λ$) to avoid violating the global CR constraints. Finally, experiments on the offline simulation environment and online real-world recommender system validate the effectiveness of our approach.

preprint2022arXiv

A Probabilistic Model-Based Robust Waveform Design for MIMO Radar Detection

This paper addresses robust waveform design for multiple-input-multiple-output (MIMO) radar detection. A probabilistic model is proposed to describe the target uncertainty. Considering that waveform design based on maximizing the probability of detection is intractable, the relative entropy between the distributions of the observations under two hypotheses (viz., the target is present/absent) is employed as the design metric. To tackle the resulting non-convex optimization problem, an efficient algorithm based on minorization-maximization (MM) is derived. Numerical results demonstrate that the waveform synthesized by the proposed algorithm is more robust to model mismatches.

preprint2022arXiv

Automatic Meta-Path Discovery for Effective Graph-Based Recommendation

Heterogeneous Information Networks (HINs) are labeled graphs that depict relationships among different types of entities (e.g., users, movies and directors). For HINs, meta-path-based recommenders (MPRs) utilize meta-paths (i.e., abstract paths consisting of node and link types) to predict user preference, and have attracted a lot of attention due to their explainability and performance. We observe that the performance of MPRs is highly sensitive to the meta-paths they use, but existing works manually select the meta-paths from many possible ones. Thus, to discover effective meta-paths automatically, we propose the Reinforcement learning-based Meta-path Selection (RMS) framework. Specifically, we define a vector encoding for meta-paths and design a policy network to extend meta-paths. The policy network is trained based on the results of downstream recommendation tasks and an early stopping approximation strategy is proposed to speed up training. RMS is a general model, and it can work with all existing MPRs. We also propose a new MPR called RMS-HRec, which uses an attention mechanism to aggregate information from the meta-paths. We conduct extensive experiments on real datasets. Compared with the manually selected meta-paths, the meta-paths identified by RMS consistently improve recommendation quality. Moreover, RMS-HRec outperforms state-of-the-art recommender systems by an average of 7% in hit ratio. The codes and datasets are available on https://github.com/Stevenn9981/RMS-HRec.

preprint2022arXiv

BCRLSP: An Offline Reinforcement Learning Framework for Sequential Targeted Promotion

We utilize an offline reinforcement learning (RL) model for sequential targeted promotion in the presence of budget constraints in a real-world business environment. In our application, the mobile app aims to boost customer retention by sending cash bonuses to customers and control the costs of such cash bonuses during each time period. To achieve the multi-task goal, we propose the Budget Constrained Reinforcement Learning for Sequential Promotion (BCRLSP) framework to determine the value of cash bonuses to be sent to users. We first find out the target policy and the associated Q-values that maximizes the user retention rate using an RL model. A linear programming (LP) model is then added to satisfy the constraints of promotion costs. We solve the LP problem by maximizing the Q-values of actions learned from the RL model given the budget constraints. During deployment, we combine the offline RL model with the LP model to generate a robust policy under the budget constraints. Using both online and offline experiments, we demonstrate the efficacy of our approach by showing that BCRLSP achieves a higher long-term customer retention rate and a lower cost than various baselines. Taking advantage of the near real-time cost control method, the proposed framework can easily adapt to data with a noisy behavioral policy and/or meet flexible budget constraints.

preprint2022arXiv

Fundamental Limits on Detection With a Dual-function Radar Communication System

This paper investigates the fundamental limits on the target detection performance with a dual-function multiple-input-multiple-output (MIMO) radar communication (RadCom) systems. By assuming the presence of a point-like target and a communication receiver, closed-form expressions for the maximum detection probability and the transmit waveforms achieving the optimal performance are derived. Results show that for the considered case, the dual-function system should transmit coherent waveforms to achieve the optimal detection performance. Moreover, the angle separation between the target and communication receiver has a great impact on the achievable detection performance.

preprint2022arXiv

Generalized Federated Learning via Sharpness Aware Minimization

Federated Learning (FL) is a promising framework for performing privacy-preserving, distributed learning with a set of clients. However, the data distribution among clients often exhibits non-IID, i.e., distribution shift, which makes efficient optimization difficult. To tackle this problem, many FL algorithms focus on mitigating the effects of data heterogeneity across clients by increasing the performance of the global model. However, almost all algorithms leverage Empirical Risk Minimization (ERM) to be the local optimizer, which is easy to make the global model fall into a sharp valley and increase a large deviation of parts of local clients. Therefore, in this paper, we revisit the solutions to the distribution shift problem in FL with a focus on local learning generality. To this end, we propose a general, effective algorithm, \texttt{FedSAM}, based on Sharpness Aware Minimization (SAM) local optimizer, and develop a momentum FL algorithm to bridge local and global models, \texttt{MoFedSAM}. Theoretically, we show the convergence analysis of these two algorithms and demonstrate the generalization bound of \texttt{FedSAM}. Empirically, our proposed algorithms substantially outperform existing FL studies and significantly decrease the learning deviation.

preprint2022arXiv

LoMar: A Local Defense Against Poisoning Attack on Federated Learning

Federated learning (FL) provides a high efficient decentralized machine learning framework, where the training data remains distributed at remote clients in a network. Though FL enables a privacy-preserving mobile edge computing framework using IoT devices, recent studies have shown that this approach is susceptible to poisoning attacks from the side of remote clients. To address the poisoning attacks on FL, we provide a \textit{two-phase} defense algorithm called {Lo}cal {Ma}licious Facto{r} (LoMar). In phase I, LoMar scores model updates from each remote client by measuring the relative distribution over their neighbors using a kernel density estimation method. In phase II, an optimal threshold is approximated to distinguish malicious and clean updates from a statistical perspective. Comprehensive experiments on four real-world datasets have been conducted, and the experimental results show that our defense strategy can effectively protect the FL system. {Specifically, the defense performance on Amazon dataset under a label-flipping attack indicates that, compared with FG+Krum, LoMar increases the target label testing accuracy from $96.0\%$ to $98.8\%$, and the overall averaged testing accuracy from $90.1\%$ to $97.0\%$.

preprint2022arXiv

Manu: A Cloud Native Vector Database Management System

With the development of learning-based embedding models, embedding vectors are widely used for analyzing and searching unstructured data. As vector collections exceed billion-scale, fully managed and horizontally scalable vector databases are necessary. In the past three years, through interaction with our 1200+ industry users, we have sketched a vision for the features that next-generation vector databases should have, which include long-term evolvability, tunable consistency, good elasticity, and high performance. We present Manu, a cloud native vector database that implements these features. It is difficult to integrate all these features if we follow traditional DBMS design rules. As most vector data applications do not require complex data models and strong data consistency, our design philosophy is to relax the data model and consistency constraints in exchange for the aforementioned features. Specifically, Manu firstly exposes the write-ahead log (WAL) and binlog as backbone services. Secondly, write components are designed as log publishers while all read-only analytic and search components are designed as independent subscribers to the log services. Finally, we utilize multi-version concurrency control (MVCC) and a delta consistency model to simplify the communication and cooperation among the system components. These designs achieve a low coupling among the system components, which is essential for elasticity and evolution. We also extensively optimize Manu for performance and usability with hardware-aware implementations and support for complex search semantics.

preprint2022arXiv

Measuring Friendship Closeness: A Perspective of Social Identity Theory

Measuring the closeness of friendships is an important problem that finds numerous applications in practice. For example, online gaming platforms often host friendship-enhancing events in which a user (called the source) only invites his/her friend (called the target) to play together. In this scenario, the measure of friendship closeness is the backbone for understanding source invitation and target adoption behaviors, and underpins the recommendation of promising targets for the sources. However, most existing measures for friendship closeness only consider the information between the source and target but ignore the information of groups where they are located, which renders inferior results. To address this issue, we present new measures for friendship closeness based on the social identity theory (SIT), which describes the inclination that a target endorses behaviors of users inside the same group. The core of SIT is the process that a target assesses groups of users as them or us. Unfortunately, this process is difficult to be captured due to perceptual factors. To this end, we seamlessly reify the factors of SIT into quantitative measures, which consider local and global information of a target's group. We conduct extensive experiments to evaluate the effectiveness of our proposal against 8 state-of-the-art methods on 3 online gaming datasets. In particular, we demonstrate that our solution can outperform the best competitor on the behavior prediction (resp. online target recommendation) by up to 23.2% (resp. 34.2%) in the corresponding evaluation metric.

preprint2022arXiv

MIMO Multifunction RF Systems: Detection Performance and Waveform Design

This paper studies the detection performance of a multiple-input-multiple-output (MIMO) multifunction radio frequency (MFRF) system, which simultaneously supports radar, communication, and jamming. We show that the detection performance of the MIMO MFRF system improves as the transmit signal-to-interference-plus-noise-ratio (SINR) increases. To analyze the achievable SINR of the system, we formulate an SINR maximization problem under the communication and jamming functionality constraint as well as a transmit energy constraint. We derive a closed-form solution of this optimization problem for energy-constrained waveforms and present a detailed analysis of the achievable SINR. Moreover, we analyze the SINR for systems transmitting constant-modulus waveforms, which are often used in practice. We propose an efficient constant-modulus waveform design algorithm to maximize the SINR. Numerical results demonstrate the capability of a MIMO array to provide multiple functions, and also show the tradeoff between radar detection and the communication/jamming functionality.

preprint2022arXiv

On the Convergence of Multi-Server Federated Learning with Overlapping Area

Multi-server Federated learning (FL) has been considered as a promising solution to address the limited communication resource problem of single-server FL. We consider a typical multi-server FL architecture, where the coverage areas of regional servers may overlap. The key point of this architecture is that the clients located in the overlapping areas update their local models based on the average model of all accessible regional models, which enables indirect model sharing among different regional servers. Due to the complicated network topology, the convergence analysis is much more challenging than single-server FL. In this paper, we firstly propose a novel MS-FedAvg algorithm for this multi-server FL architecture and analyze its convergence on non-iid datasets for general non-convex settings. Since the number of clients located in each regional server is much less than in single-server FL, the bandwidth of each client should be large enough to successfully communicate training models with the server, which indicates that full client participation can work in multi-server FL. Also, we provide the convergence analysis of the partial client participation scheme and develop a new biased partial participation strategy to further accelerate convergence. Our results indicate that the convergence results highly depend on the ratio of the number of clients in each area type to the total number of clients in all three strategies. The extensive experiments show remarkable performance and support our theoretical results.

preprint2022arXiv

Waveform Design for Mutual Interference Mitigation in Automotive Radar

The mutual interference between similar radar systems can result in reduced radar sensitivity and increased false alarm rates. To address the synchronous and asynchronous interference mitigation problems in similar radar systems, we first propose herein two slow-time coding schemes to modulate the pulses within a coherent processing interval (CPI) for a single-input-single-output (SISO) scenario. Specifically, the first coding scheme relies on Doppler shifting and the second one is devised based on an optimization approach. We further extend our discussion to the more general case of multiple-input-multiple-output (MIMO) radars and propose an efficient algorithm to design waveforms to mitigate mutual interference in such systems. The proposed coding schemes are computationally efficient in practice and the incorporation of the coding schemes requires only a slight modification of the existing systems. Our numerical examples indicate that the proposed coding schemes can reduce the interference power level in a desired area of the cross-ambiguity function significantly.

preprint2021arXiv

Overcoming Long-term Catastrophic Forgetting through Adversarial Neural Pruning and Synaptic Consolidation

Artificial neural networks face the well-known problem of catastrophic forgetting. What's worse, the degradation of previously learned skills becomes more severe as the task sequence increases, known as the long-term catastrophic forgetting. It is due to two facts: first, as the model learns more tasks, the intersection of the low-error parameter subspace satisfying for these tasks becomes smaller or even does not exist; second, when the model learns a new task, the cumulative error keeps increasing as the model tries to protect the parameter configuration of previous tasks from interference. Inspired by the memory consolidation mechanism in mammalian brains with synaptic plasticity, we propose a confrontation mechanism in which Adversarial Neural Pruning and synaptic Consolidation (ANPyC) is used to overcome the long-term catastrophic forgetting issue. The neural pruning acts as long-term depression to prune task-irrelevant parameters, while the novel synaptic consolidation acts as long-term potentiation to strengthen task-relevant parameters. During the training, this confrontation achieves a balance in that only crucial parameters remain, and non-significant parameters are freed to learn subsequent tasks. ANPyC avoids forgetting important information and makes the model efficient to learn a large number of tasks. Specifically, the neural pruning iteratively relaxes the current task's parameter conditions to expand the common parameter subspace of the task; the synaptic consolidation strategy, which consists of a structure-aware parameter-importance measurement and an element-wise parameter updating strategy, decreases the cumulative error when learning new tasks. The full source code is available at https://github.com/GeoX-Lab/ANPyC.

preprint2021arXiv

Stragglers Are Not Disaster: A Hybrid Federated Learning Algorithm with Delayed Gradients

Federated learning (FL) is a new machine learning framework which trains a joint model across a large amount of decentralized computing devices. Existing methods, e.g., Federated Averaging (FedAvg), are able to provide an optimization guarantee by synchronously training the joint model, but usually suffer from stragglers, i.e., IoT devices with low computing power or communication bandwidth, especially on heterogeneous optimization problems. To mitigate the influence of stragglers, this paper presents a novel FL algorithm, namely Hybrid Federated Learning (HFL), to achieve a learning balance in efficiency and effectiveness. It consists of two major components: synchronous kernel and asynchronous updater. Unlike traditional synchronous FL methods, our HFL introduces the asynchronous updater which actively pulls unsynchronized and delayed local weights from stragglers. An adaptive approximation method, Adaptive Delayed-SGD (AD-SGD), is proposed to merge the delayed local updates into the joint model. The theoretical analysis of HFL shows that the convergence rate of the proposed algorithm is $\mathcal{O}(\frac{1}{t+τ})$ for both convex and non-convex optimization problems.

preprint2020arXiv

Learning Discontinuous Piecewise Affine Fitting Functions using Mixed Integer Programming for Segmentation and Denoising

Piecewise affine functions are widely used to approximate nonlinear and discontinuous functions. However, most, if not all existing models only deal with fitting continuous functions. In this paper, we investigate the problem of fitting a discontinuous piecewise affine function to given data that lie in an orthogonal grid, where no restriction on the partition is enforced (i.e., its geometric shape can be nonconvex). This is useful for segmentation and denoising when data corresponding to images. We propose a novel Mixed Integer Program (MIP) formulation for the piecewise affine fitting problem, where binary variables determine the location of break-points. To obtain consistent partitions (i.e. image segmentation), we include multi-cut constraints in the formulation. Since the resulting problem is $\mathcal{NP}$-hard, two techniques are introduced to improve the computation. One is to add facet-defining inequalities to the formulation and the other to provide initial integer solutions using a special heuristic algorithm. We conduct extensive experiments by some synthetic images as well as real depth images, and the results demonstrate the feasibility of our model.

preprint2020arXiv

RCELF: A Residual-based Approach for Influence Maximization Problem

Influence Maximization Problem (IMP) is selecting a seed set of nodes in the social network to spread the influence as widely as possible. It has many applications in multiple domains, e.g., viral marketing is frequently used for new products or activities advertisements. While it is a classic and well-studied problem in computer science, unfortunately, all those proposed techniques are compromising among time efficiency, memory consumption, and result quality. In this paper, we conduct comprehensive experimental studies on the state-of-the-art IMP approximate approaches to reveal the underlying trade-off strategies. Interestingly, we find that even the state-of-the-art approaches are impractical when the propagation probability of the network have been taken into consideration. With the findings of existing approaches, we propose a novel residual-based approach (i.e., RCELF) for IMP, which i) overcomes the deficiencies of existing approximate approaches, and ii) provides theoretical guaranteed results with high efficiency in both time- and space- perspectives. We demonstrate the superiority of our proposal by extensive experimental evaluation on real datasets.

preprint2020arXiv

Towards Self-Tuning Parameter Servers

Recent years, many applications have been driven advances by the use of Machine Learning (ML). Nowadays, it is common to see industrial-strength machine learning jobs that involve millions of model parameters, terabytes of training data, and weeks of training. Good efficiency, i.e., fast completion time of running a specific ML job, therefore, is a key feature of a successful ML system. While the completion time of a long-running ML job is determined by the time required to reach model convergence, practically that is also largely influenced by the values of various system settings. In this paper, we contribute techniques towards building self-tuning parameter servers. Parameter Server (PS) is a popular system architecture for large-scale machine learning systems; and by self-tuning we mean while a long-running ML job is iteratively training the expert-suggested model, the system is also iteratively learning which system setting is more efficient for that job and applies it online. While our techniques are general enough to various PS-style ML systems, we have prototyped our techniques on top of TensorFlow. Experiments show that our techniques can reduce the completion times of a variety of long-running TensorFlow jobs from 1.4x to 18x.

preprint2016arXiv

A Local Density-Based Approach for Local Outlier Detection

This paper presents a simple but effective density-based outlier detection approach with the local kernel density estimation (KDE). A Relative Density-based Outlier Score (RDOS) is introduced to measure the local outlierness of objects, in which the density distribution at the location of an object is estimated with a local KDE method based on extended nearest neighbors of the object. Instead of using only $k$ nearest neighbors, we further consider reverse nearest neighbors and shared nearest neighbors of an object for density distribution estimation. Some theoretical properties of the proposed RDOS including its expected value and false alarm probability are derived. A comprehensive experimental study on both synthetic and real-life data sets demonstrates that our approach is more effective than state-of-the-art outlier detection methods.

preprint2016arXiv

Adaptive Signal Detection and Parameter Estimation in Unknown Colored Gaussian Noise

This paper considers the general signal detection and parameter estimation problem in the presence of colored Gaussian noise disturbance. By modeling the disturbance with an autoregressive process, we present three signal detectors with different unknown parameters under the general framework of binary hypothesis testing. The closed form of parameter estimates and the asymptotic distributions of these three tests are also given. Given two examples of frequency modulated signal detection problem and time series moving object detection problem, the simulation results demonstrate the effectiveness of three presented detectors.

preprint2016arXiv

Detection of False Data Injection Attacks in Smart Grid under Colored Gaussian Noise

In this paper, we consider the problems of state estimation and false data injection detection in smart grid when the measurements are corrupted by colored Gaussian noise. By modeling the noise with the autoregressive process, we estimate the state of the power transmission networks and develop a generalized likelihood ratio test (GLRT) detector for the detection of false data injection attacks. We show that the conventional approach with the assumption of Gaussian noise is a special case of the proposed method, and thus the new approach has more applicability. {The proposed detector is also tested on an independent component analysis (ICA) based unobservable false data attack scheme that utilizes similar assumptions of sample observation.} We evaluate the performance of the proposed state estimator and attack detector on the IEEE 30-bus power system with comparison to conventional Gaussian noise based detector. The superior performance of {both observable and unobservable false data attacks} demonstrates the effectiveness of the proposed approach and indicates a wide application on the power signal processing.

preprint2016arXiv

EEF: Exponentially Embedded Families with Class-Specific Features for Classification

In this letter, we present a novel exponentially embedded families (EEF) based classification method, in which the probability density function (PDF) on raw data is estimated from the PDF on features. With the PDF construction, we show that class-specific features can be used in the proposed classification method, instead of a common feature subset for all classes as used in conventional approaches. We apply the proposed EEF classifier for text categorization as a case study and derive an optimal Bayesian classification rule with class-specific feature selection based on the Information Gain (IG) score. The promising performance on real-life data sets demonstrates the effectiveness of the proposed approach and indicates its wide potential applications.

preprint2016arXiv

FSMJ: Feature Selection with Maximum Jensen-Shannon Divergence for Text Categorization

In this paper, we present a new wrapper feature selection approach based on Jensen-Shannon (JS) divergence, termed feature selection with maximum JS-divergence (FSMJ), for text categorization. Unlike most existing feature selection approaches, the proposed FSMJ approach is based on real-valued features which provide more information for discrimination than binary-valued features used in conventional approaches. We show that the FSMJ is a greedy approach and the JS-divergence monotonically increases when more features are selected. We conduct several experiments on real-life data sets, compared with the state-of-the-art feature selection approaches for text categorization. The superior performance of the proposed FSMJ approach demonstrates its effectiveness and further indicates its wide potential applications on data mining.

preprint2016arXiv

Kernel-based Generative Learning in Distortion Feature Space

This paper presents a novel kernel-based generative classifier which is defined in a distortion subspace using polynomial series expansion, named Kernel-Distortion (KD) classifier. An iterative kernel selection algorithm is developed to steadily improve classification performance by repeatedly removing and adding kernels. The experimental results on character recognition application not only show that the proposed generative classifier performs better than many existing classifiers, but also illustrate that it has different recognition capability compared to the state-of-the-art discriminative classifier - deep belief network. The recognition diversity indicates that a hybrid combination of the proposed generative classifier and the discriminative classifier could further improve the classification performance. Two hybrid combination methods, cascading and stacking, have been implemented to verify the diversity and the improvement of the proposed classifier.

preprint2016arXiv

Probabilistic Human Mobility Model in Indoor Environment

Understanding human mobility is important for the development of intelligent mobile service robots as it can provide prior knowledge and predictions of human distribution for robot-assisted activities. In this paper, we propose a probabilistic method to model human motion behaviors which is determined by both internal and external factors in an indoor environment. While the internal factors are represented by the individual preferences, aims and interests, the external factors are indicated by the stimulation of the environment. We model the randomness of human macro-level movement, e.g., the probability of visiting a specific place and staying time, under the Bayesian framework, considering the influence of both internal and external variables. We use two case studies in a shopping mall and in a college student dorm building to show the effectiveness of our proposed probabilistic human mobility model. Real surveillance camera data are used to validate the proposed model together with survey data in the case study of student dorm.

preprint2016arXiv

Toward Optimal Feature Selection in Naive Bayes for Text Categorization

Automated feature selection is important for text categorization to reduce the feature size and to speed up the learning process of classifiers. In this paper, we present a novel and efficient feature selection framework based on the Information Theory, which aims to rank the features with their discriminative capacity for classification. We first revisit two information measures: Kullback-Leibler divergence and Jeffreys divergence for binary hypothesis testing, and analyze their asymptotic properties relating to type I and type II errors of a Bayesian classifier. We then introduce a new divergence measure, called Jeffreys-Multi-Hypothesis (JMH) divergence, to measure multi-distribution divergence for multi-class classification. Based on the JMH-divergence, we develop two efficient feature selection methods, termed maximum discrimination ($MD$) and $MD-χ^2$ methods, for text categorization. The promising results of extensive experiments demonstrate the effectiveness of the proposed approaches.

preprint2015arXiv

On the Efficiency of All-Pay Mechanisms

We study the inefficiency of mixed equilibria, expressed as the price of anarchy, of all-pay auctions in three different environments: combinatorial, multi-unit and single-item auctions. First, we consider item-bidding combinatorial auctions where m all-pay auctions run in parallel, one for each good. For fractionally subadditive valuations, we strengthen the upper bound from 2 [Syrgkanis and Tardos STOC'13] to 1.82 by proving some structural properties that characterize the mixed Nash equilibria of the game. Next, we design an all-pay mechanism with a randomized allocation rule for the multi- unit auction. We show that, for bidders with submodular valuations, the mechanism admits a unique, 75% efficient, pure Nash equilibrium. The efficiency of this mechanism outperforms all the known bounds on the price of anarchy of mechanisms used for multi-unit auctions. Finally, we analyze single-item all-pay auctions motivated by their connection to contests and show tight bounds on the price of anarchy of social welfare, revenue and maximum bid.

preprint2015arXiv

On the Efficiency of the Proportional Allocation Mechanism for Divisible Resources

We study the efficiency of the proportional allocation mechanism, that is widely used to allocate divisible resources. Each agent submits a bid for each divisible resource and receives a fraction proportional to her bids. We quantify the inefficiency of Nash equilibria by studying the Price of Anarchy (PoA) of the induced game under complete and incomplete information. When agents' valuations are concave, we show that the Bayesian Nash equilibria can be arbitrarily inefficient, in contrast to the well-known 4/3 bound for pure equilibria. Next, we upper bound the PoA over Bayesian equilibria by 2 when agents' valuations are subadditive, generalizing and strengthening previous bounds on lattice submodular valuations. Furthermore, we show that this bound is tight and cannot be improved by any simple or scale-free mechanism. Then we switch to settings with budget constraints, and we show an improved upper bound on the PoA over coarse-correlated equilibria. Finally, we prove that the PoA is exactly 2 for pure equilibria in the polyhedral environment.

preprint2015arXiv

Tight Bounds for the Price of Anarchy of Simultaneous First Price Auctions

We study the Price of Anarchy of simultaneous first-price auctions for buyers with submodular and subadditive valuations. The current best upper bounds for the Bayesian Price of Anarchy of these auctions are e/(e-1) [Syrgkanis and Tardos 2013] and 2 [Feldman et al. 2013], respectively. We provide matching lower bounds for both cases even for the case of full information and for mixed Nash equilibria via an explicit construction. We present an alternative proof of the upper bound of e/(e-1) for first-price auctions with fractionally subadditive valuations which reveals the worst-case price distribution, that is used as a building block for the matching lower bound construction. We generalize our results to a general class of item bidding auctions that we call bid-dependent auctions (including first-price auctions and all-pay auctions) where the winner is always the highest bidder and each bidder's payment depends only on his own bid. Finally, we apply our techniques to discriminatory price multi-unit auctions. We complement the results of [de Keijzer et al. 2013] for the case of subadditive valuations, by providing a matching lower bound of 2. For the case of submodular valuations, we provide a lower bound of 1.109. For the same class of valuations, we were able to reproduce the upper bound of e/(e-1) using our non-smooth approach.

preprint2015arXiv

Updated reduced CMB data and constraints on cosmological parameters

We obtain the reduced CMB data $\{l_A, R, z_*\}$ from WMAP9, WMAP9+BICEP2, Planck+WP and Planck+WP+BICEP2 for the $Λ$CDM and $w$CDM models with or without spatial curvature. We then use these reduced CMB data in combination with low-redshift observations to put constraints on cosmological parameters. We find that including BICEP2 results in a higher value of the Hubble constant especially when the equation of state of dark energy and curvature are allowed to vary. For the $Λ$CDM model with curvature, the estimate of the Hubble constant with Planck+WP+Lensing is inconsistent with the one derived from Planck+WP+BICEP at about 1.3 $σ$ confidence level.

preprint2015arXiv

Well-Supported versus Approximate Nash Equilibria: Query Complexity of Large Games

We study the randomized query complexity of approximate Nash equilibria (ANE) in large games. We prove that, for some constant $ε>0$, any randomized oracle algorithm that computes an $ε$-ANE in a binary-action, $n$-player game must make $2^{Ω(n/\log n)}$ payoff queries. For the stronger solution concept of well-supported Nash equilibria (WSNE), Babichenko previously gave an exponential $2^{Ω(n)}$ lower bound for the randomized query complexity of $ε$-WSNE, for some constant $ε>0$; the same lower bound was shown to hold for $ε$-ANE, but only when $ε=O(1/n)$. Our result answers an open problem posed by Hart and Nisan and Babichenko and is very close to the trivial upper bound of $2^n$. Our proof relies on a generic reduction from the problem of finding an $ε$-WSNE to the problem of finding an $ε/(4α)$-ANE, in large games with $α$ actions, which might be of independent interest.

preprint2014arXiv

Constraints on the $Λ$CDM model with redshift tomography

Recently released Planck data favor a lower value of the Hubble constant and a higher value of the fraction matter density in the standard $Λ$CDM model, which are discrepant with some of the low-redshift measurements. Within the context of this cosmology, we examine the consistency of the estimated values for the Hubble constant and fraction matter density with redshift tomography. Using the SNe Ia, Hubble parameter, BAO and CMB data, which are divided into three bins, we find no statistical evidence for any tension in the three redshift bins, although there exists a 1.4$σ$ deviation of the Hubble constant in the middle redshift from the one in the high redshift bin.

preprint2013arXiv

Constraining the Anisotropic Expansion of Universe

We study the possibly existing anisotropy in the accelerating expansion universe with the Union2 Type Ia supernovae data and Gamma-ray burst data. We construct a direction-dependent dark energy model and constrain the anisotropy direction and strength of modulation. We find that the maximum anisotropic deviation direction is $(l,\,b)=(126^{\circ},\,13^{\circ})$ (or equivalently $(l,\,b)=(306^{\circ},\,-13^{\circ})$), and the current anisotropy level is $g_0=0.030_{+0.010}^{-0.030}$ ($1σ$ confidence level with Union2 data). Our results do not show strong evidence for the anisotropic dark energy model. We also discuss potential methods that may distinguish the peculiar velocity field from the anisotropic dark energy model.

preprint2013arXiv

Pricing Ad Slots with Consecutive Multi-unit Demand

We consider the optimal pricing problem for a model of the rich media advertisement market, as well as other related applications. In this market, there are multiple buyers (advertisers), and items (slots) that are arranged in a line such as a banner on a website. Each buyer desires a particular number of {\em consecutive} slots and has a per-unit-quality value $v_i$ (dependent on the ad only) while each slot $j$ has a quality $q_j$ (dependent on the position only such as click-through rate in position auctions). Hence, the valuation of the buyer $i$ for item $j$ is $v_iq_j$. We want to decide the allocations and the prices in order to maximize the total revenue of the market maker. A key difference from the traditional position auction is the advertiser's requirement of a fixed number of consecutive slots. Consecutive slots may be needed for a large size rich media ad. We study three major pricing mechanisms, the Bayesian pricing model, the maximum revenue market equilibrium model and an envy-free solution model. Under the Bayesian model, we design a polynomial time computable truthful mechanism which is optimum in revenue. For the market equilibrium paradigm, we find a polynomial time algorithm to obtain the maximum revenue market equilibrium solution. In envy-free settings, an optimal solution is presented when the buyers have the same demand for the number of consecutive slots. We conduct a simulation that compares the revenues from the above schemes and gives convincing results.

preprint2013arXiv

The Simulated Greedy Algorithm for Several Submodular Matroid Secretary Problems

We study the matroid secretary problems with submodular valuation functions. In these problems, the elements arrive in random order. When one element arrives, we have to make an immediate and irrevocable decision on whether to accept it or not. The set of accepted elements must form an {\em independent set} in a predefined matroid. Our objective is to maximize the value of the accepted elements. In this paper, we focus on the case that the valuation function is a non-negative and monotonically non-decreasing submodular function. We introduce a general algorithm for such {\em submodular matroid secretary problems}. In particular, we obtain constant competitive algorithms for the cases of laminar matroids and transversal matroids. Our algorithms can be further applied to any independent set system defined by the intersection of a {\em constant} number of laminar matroids, while still achieving constant competitive ratios. Notice that laminar matroids generalize uniform matroids and partition matroids. On the other hand, when the underlying valuation function is linear, our algorithm achieves a competitive ratio of 9.6 for laminar matroids, which significantly improves the previous result.

preprint2011arXiv

Optimal Pricing in Social Networks with Incomplete Information

In revenue maximization of selling a digital product in a social network, the utility of an agent is often considered to have two parts: a private valuation, and linearly additive influences from other agents. We study the incomplete information case where agents know a common distribution about others' private valuations, and make decisions simultaneously. The "rational behavior" of agents in this case is captured by the well-known Bayesian Nash equilibrium. Two challenging questions arise: how to compute an equilibrium and how to optimize a pricing strategy accordingly to maximize the revenue assuming agents follow the equilibrium? In this paper, we mainly focus on the natural model where the private valuation of each agent is sampled from a uniform distribution, which turns out to be already challenging. Our main result is a polynomial-time algorithm that can exactly compute the equilibrium and the optimal price, when pairwise influences are non-negative. If negative influences are allowed, computing any equilibrium even approximately is PPAD-hard. Our algorithm can also be used to design an FPTAS for optimizing discriminative price profile.