TASK DEFINITION: In this task, you are given a part of an article. Your task is to generate headline (title) for this text. Preferred headlines are under fifteen words.
PROBLEM: We first consider the problem of learning k-parities in the on-line mistake-bound model: given a hidden vector x ∈ {0, 1} with |x| = k and a sequence of “questions” a1, a2, · · · ∈ {0, 1} , where the algorithm must reply to each question with 〈ai, x〉 (mod 2), what is the best tradeoff between the number of mistakes made by the algorithm and its time complexity? We improve the previous best result of Buhrman et. al. [BGM10] by an exp(k) factor in the time complexity. Second, we consider the problem of learning k-parities in the presence of classification noise of rate η ∈ (0, 1/2). A polynomial time algorithm for this problem (when η > 0 and k = ω(1)) is a longstanding challenge in learning theory. Grigorescu et al. [GRV11] showed an algorithm running in time ( n k/2 )1+4η+o(1) . Note that this algorithm inherently requires time ( n k/2 ) even when the noise rate η is polynomially small. We observe that for sufficiently small noise rate, it is possible to break the ( n k/2 ) barrier. In particular, if for some function f(n) = ω(1) and α ∈ [1/2, 1), k = n/f(n) and η = o(f(n)/ log n), then there is an algorithm for the problem with running time poly(n) · ( n k )1−α · e.

SOLUTION: On learning k-parities with and without noise

PROBLEM: A famous biologically inspired hierarchical model firstly proposed by Riesenhuber and Poggio has been successfully applied to multiple visual recognition tasks. The model is able to achieve a set of positionand scale-tolerant recognition, which is a central problem in pattern recognition. In this paper, based on some other biological experimental results, we introduce the Memory and Association Mechanisms into the above biologically inspired model. The main motivations of the work are (a) to mimic the active memory and association mechanism and add the ’top down’ adjustment to the above biologically inspired hierarchical model and (b) to build up an algorithm which can save the space and keep a good recognition performance. More details of the work could be explained as follows: (1) In objects memorizing process: Our proposed model mimics some characteristics of human’s memory mechanism as follows: (a) In our model, one object is memorized by semantic attributes and special image patches (corresponding to episodic memory). The semantic attributes describe each part of the object with clear physical meaning, for example, if eyes and mouths of faces are ’big’ or ’small’ and so on. One special patch is selected if the value of the corresponding semantic feature is far from average one. The patch should be the most prominent part of the object. (b) In our model, different features (semantic attributes and special patches) of one object are stored in distributed places and the common feature of different objects is saved aggregately, which can learn to classify the difference of similar features of different objects. The similarity thresholds to each object can be learnt when new objects are learnt. (2) In object recognition process: In biological process, the associated recognition including familiarity discrimination and recollective matching. In our proposed model, firstly mimicking familiarity discrimination (’knowing’ though the episode), we compare the special patches of candidates with that of saved objects using above mentioned biologically inspired hierarchical model, where the candidates and saved objects have the same prominent semantic features. Then mimicking recollective matching, the comparison results of special patches are combined with semantic feature comparison. The new model is also applied to object recognition processes. The primary experimental results show that our method is efficient with much less memory requirement.

SOLUTION: Introducing Memory and Association Mechanism Into a Biologically Inspired Visual Model

PROBLEM: Learning to localize objects with minimal supervision is an important problem in computer vision, since large fully annotated datasets are extremely costly to obtain. In this paper, we propose a new method that achieves this goal with only image-level labels of whether the objects are present or not. Our approach combines a discriminative submodular cover problem for automatically discovering a set of positive object windows with a smoothed latent SVM formulation. The latter allows us to leverage efficient quasiNewton optimization techniques. Our experiments demonstrate that the proposed approach provides a 50% relative improvement in mean average precision over the current state-of-the-art on PASCAL VOC 2007 detection.

SOLUTION:
On learning to localize objects with minimal supervision