Programming tasks provide an opportunity for students to improve their problem-solving skills (PSS). However, when programming tasks are challenging, students could become demotivated and lose the opportunity to improve PSS in the process. To scaffold the difficulty of programming tasks and better motivate students to enhance PSS via coding, this paper introduces PDL (Problem Description Language). Given the natural-language description of a combinatorial optimization problem (COP), PDL requires students to describe (i) inputs, (ii) constraints, (iii) the optimization objective, and (iv) outputs, based on their problem comprehension. PDL then validates each problem description by (1) compiling a solution program from the description and (2) executing the generated program with predefined test cases. Based on the compiling and testing results, PDL provides feedback to students, and assists students to adjust their problem comprehension and improve problem descriptions.

Combinatorial problems (CPs) arise in many areas, and people use constraint solvers to automatically solve these problems. However, the state-of-the-art constraint solvers (e.g., Gecode and Chuffed) have overly complicated software architectures; they compute solutions inefficiently. This paper presents a novel and model-driven approach---SoGen---to synthesize efficient problem-specific solvers from constraint models. Namely, when users model a CP with our domain-specific language PDL (short for Problem Description Language), SoGen automatically analyzes various properties of the problem (e.g., search space, value boundaries, function monotonicity, and overlapping subproblems), synthesizes an efficient solver algorithm based on those properties, and generates a C program as the problem solver. PDL is unique because it can create solvers that resolve constraints via dynamic programming (DP) search.

In game AI research, most work aims at building a more powerful AI but few are reported on explaining AI's behavior or revealing the characters of AI. Previous efforts in training a human-like AI via style learning implies that AI may behave with human characteristics. However, the early work treated human playstyle as a whole instead of identifying the difference among various AIs. In this paper, we focus on finding out manlike characters of individual AIs, and clustering AIs according to their characters. We propose a Neural Network based game AI imitator to imitate AIs' behavior and find that some AIs are easier to imitate than others. Based on this observation we define the term imitability to describe the difficulty of imitation and cluster the AIs into two categories according to their imitability. Through statically analyzing, we find that AIs with lower imitability are generally farseeing with a global perspective while the other group are nearsighted and narrow-minded. The AIs hard to imitate also perform better when fighting with others. Upon the above semantic analysis of the clustering results, we conclude that the imitability can be used to identify AIs' character.

Constraint optimization problems (COP) on finite domains are typically solved via search. Many problems (e.g., 0-1 knapsack) involve redundant search, making a general constraint solver revisit the same subproblems again and again. Existing approaches use caching, symmetry breaking, subproblem dominance, or search with decomposition to prune the search space of constraint problems. In this paper we present a different approach--DPSolver--which uses dynamic programming (DP) to efficiently solve certain types of constraint optimization problems (COPs). Given a COP modeled with MiniZinc, DPSolver first analyzes the model to decide whether the problem is efficiently solvable with DP. If so, DPSolver refactors the constraints and objective functions to model the problem as a DP problem. Finally, DPSolver feeds the refactored model to Gecode--a widely used constraint solver--for the optimal solution. Our evaluation shows that DPSolver significantly improves the performance of constraint solving.

In typical reinforcement learning (RL), the environment is assumed given and the goal of the learning is to identify an optimal policy for the agent taking actions through its interactions with the environment. In this paper, we extend this setting by considering the environment is not given, but controllable and learnable through its interaction with the agent at the same time. This extension is motivated by environment design scenarios in the real-world, including game design, shopping space design and traffic signal design. Theoretically, we find a dual Markov decision process (MDP) w.r.t. the environment to that w.r.t. the agent, and derive a policy gradient solution to optimizing the parametrized environment. Furthermore, discontinuous environments are addressed by a proposed general generative framework. Our experiments on a Maze game design task show the effectiveness of the proposed algorithms in generating diverse and challenging Mazes against various agent settings.

This paper presents Botzone, a competitive platform for game AI education and research. It aims to simplify the teaching process of game AI courses, inspire learners to self-study, and acting as a dataset for game AI research. This platform is a universal online multi-agent game AI platform, designed to evaluate different implementations of game AI by applying them to agents in a variety of games and compete with each other, featuring an ELO ranking system and a contest system for users to evaluate their AI programs. It has been successfully used in various AI competitions and courses in practice, and has the extensibility to support more games and languages, as well as further usages such as studying machine learning on game AI. In this paper, we firstly describe the structure and features of Botzone, then focus on our experience in utilizing Botzone for a programming course.

In recent years, finger vein recognition has become an important sub-field in biometrics and been applied to real-world applications. The development of finger vein recognition algorithms heavily depends on large-scale real-world data sets. In order to motivate research on finger vein recognition, we released the largest finger vein data set up to now and hold finger vein recognition competitions based on our data set every year. In 2017, International Competition on Finger Vein Recognition (ICFVR) is held jointly with IJCB 2017. 11 teams registered and 10 of them joined the final evaluation. The winner of this year dramatically improved the EER from 2.64% to 0.483% compared to the 'winner of last year. In this paper, we introduce the process and results of ICFVR 2017 and give insights on development of state-of-art finger vein recognition algorithms.

In this paper, we deal with the uncertainty of bidding for display advertising. Similar to the financial market trading, real-time bidding (RTB) based display advertising employs an auction mechanism to automate the impression level media buying; and running a campaign is no different than an investment of acquiring new customers in return for obtaining additional converted sales. Thus, how to optimally bid on an ad impression to drive the profit and return-on-investment becomes essential. However, the large randomness of the user behaviors and the cost uncertainty caused by the auction competition may result in a significant risk from the campaign performance estimation. In this paper, we explicitly model the uncertainty of user click-through rate estimation and auction competition to capture the risk. We borrow an idea from finance and derive the value at risk for each ad display opportunity. Our formulation results in two risk-aware bidding strategies that penalize risky ad impressions and focus more on the ones with higher expected return and lower risk. The empirical study on real-world data demonstrates the effectiveness of our proposed risk-aware bidding strategies: yielding profit gains of 15.4% in offline experiments and up to 17.5% in an online A/B test on a commercial RTB platform over the widely applied bidding strategies.

Learning programming at scale underlies computer science education ranging from basic programming to advanced software engineering topics. There are strong needs of providing effective system supports for learning programming at scale. Among various desirable characteristics of such system supports, system supports shall allow students to write programs via an online Integrated Development Environment (IDE), allow students to get feedback on how they perform on the given programming exercises, etc. To aim for such effective system supports for learning programming at scale, research teams from Peking University have developed two systems: POP (denoting Peking University Online Programming System) and POJ (denoting Peking University Online Judge System). These two systems have achieved high impact among students around the world (especially those in China). In this paper, we present the overview of the two systems, along with our ongoing and future work on extending the systems for achieving higher effectiveness in supporting learning programming at scale.

Finger-vein recognition as a non-contact biometric technique has its inherent superiority on accuracy, speed, sanitation, maintenance and security. However, we found that due to posture changes when acquiring finger images, the discrepancy between different images from the same finger greatly lowers the performance of the entire system. In this paper, we define 6 types of finger posture changes, and analysis how they influence imaging. We then proposed a method to reconstruct a 3D normalized finger model from 2D images, which can be used to map finger area in 2D image into a new 2D coordinate system, thus being able to eliminate the influence of these six types of posture changes. We choose three kinds of feature extraction method, with a test data set from a practical finger-vein recognition system including 50,700 finger-vein images. The experimental results well proved the effectiveness of this method.

Many researchers estimated the confidence interval of the evaluation index such as FMR and studied the relationship between the confidence interval width of FMR and sample size. In our research, we firstly indicated the relationship between confidence interval width w and sample size n by the equation: w^2=b1/n/n+b2/n. Apparently, the more test samples, the narrower of the confidence interval and the more convincible of the evaluation will come out. Most biometric test such as Fingerprint Verification Competitions (FVC) and NIST Fingerprint Evaluation collect as many samples as possible to get a convinced evaluation. However, based on the relationship between confidence interval and sample size, a big expansion of sample size only brings a little effect in reducing the confidence interval width when the sample size is very large. It has not been discussed till now whether it is worth achieving a narrow confidence interval by collecting a very big database. In this paper, we propose the concept of confidence elasticity which is defined by the ratio of the percentage change in confidence interval width to the percentage change in sample size to indicate the cost-effectiveness of the collecting data. Then we determine the test sample size of a deployed finger-vein biometric system according to empirical confidence elasticity. Experimental result shows that if we enlarge the sample size 150 which used in FVC2006 to 632 (about 4 times), the confidence interval width will reduce from 2.4% to 1.2% (about 1/2) based on the confidence elasticity of 0.5.

We found that the discrepancy between different finger vein templates of the same finger affects the identification results more seriously than the similarity of templates of different fingers does. Some areas on templates have stable values while some other areas are variable. We propose the Occurrence Probability Matrix (OPM), which is a property of a finger, to define the stability. When matching two templates using OPM, the areas of higher stability make more contribution to the result and those of lower stability make less contribution. In this way, OPM can enhance the similarity of templates of the same finger and drop off the influence of the unsteady areas. In a finger vein verification system running for a long time, we can get enough templates of every finger to generate an effective OPM. But it does not mean that using more templates can get a better OPM. So, we fatherly propose a strategy to select typical templates purposely from all templates of a finger to calculate the OPM. Experimental results show that by simply using OPM calculated from all existing templates, the EER of the system is reduced from 9.8% to 7.6%. And by using the OPM calculated from selected typical templates by our strategy, the EER of the system is further reduced from 7.6% to 3.1%.

In the finger-vein authentication, there are two problems in practice. One is that the quality of the vein image will be reduced under bad environment conditions; the other is the irregular distortion of the image caused by the variance of the finger poses. Both problems raise the error ratios. In this paper, we introduced a wide line detector for feature extraction, which can obtain precise width information of the vein and increase the information of the extracted feature from low quality image. We also developed a new pattern normalization model based on a hypothesis that the finger's cross-sections are approximately ellipses and the vein that can be imaged is close to the finger surface. It can effectively reduce the distortion caused by the pose. In our experiment based on a database containing 50,700 images, our method shows advantages on dealing with the low quality data collected from the practical personal authentication system.

Personal identification based on finger vein patterns is a newly developed biometrics technique and several practical systems have been deployed recent years. We developed a finger vein verification system for checking attendance and have collected a database of 0.8 million finger vein samples. Based on the database, we proposed a person retrieval solution for searching an image in the database and can get the response in an acceptable time. To fit for the retrieval solution, we designed a new encoding method. The experimental results show that our solution can get a result in about 10 seconds when working on a database of 50,700 samples. In the same time, the error rate is nearly the same as the linear searching.

In this paper, we propose a book dewarping model which flattens a curved book page to its original flat rectangle shape. This model generalizes the model proposed by Cao to handle warped book images taken from different point of views instead of only from top of the book surface. In order to do so, we realize the impact of the angle between the camera lens and the book surface and take it into account in the transform model. Based on the new model, the rectification process includes two steps: 1) on the warped book image, find a region which is original a rectangle on a flat page; 2) map each pixel in warped region to a pixel in its original rectangle region. The experimental results demonstrate the effectiveness of our proposed book dewarping approach.