In industrial manufacturing, ensuring product quality is of paramount importance. A key component of this process is anomaly detection, which aims to promptly identify defective products to reduce operational losses. However, practical industrial environments are characterized by complexity, including limited availability of labeled data, a wide variety of defect categories, and frequent changes in these categories. Such factors pose significant challenges to the effective cross-domain generalization of anomaly detection methods. To address this limitation, IA-CLIP, a novel framework that enhances cross-domain generalization for industrial anomaly detection, is proposed. IA-CLIP integrates global and local prompts with contrastive learning to overcome the limitations of existing approaches. The proposed class-agnostic global-local semantic prompts enable the model to capture general patterns of normality and anomaly without relying on object-specific semantics. We further introduce a Similarity-aware Triplet Contrastive Learning strategy to facilitate complementary learning between global and local prompts, and an Adaptive Focal Contrastive Learning scheme to help the model focus more effectively on hard-to-identify anomalous regions. Extensive experiments on nine real-world target-domain datasets, covering 50 categories of industrial products, demonstrate that IA-CLIP achieves impressive cross-domain generalization performance in realistic industrial settings. Code and data will be released upon publication.

Compiler developers have designed and implemented numerous compiler optimization techniques and provided several standard compilation flag combinations to simplify the user workflow. However, achieving the desired optimization results is difficult when using the standard compiler flag combinations provided or manually selecting the compiler flag combinations. Thus, we propose PreTuner, a general compilation flag optimization framework based on iterative compilation and predictive models. Using the optimization results from evolutionary algorithms to build a dataset of code features and compilation flag combinations, we can optimize any program in one round by extracting code features and combining them with compilation flags. PreTuner effectively addresses the problem of limited dataset availability and improves model generalization. Based on the GCC compiler, PreTuner achieves an average speedup of 1.098× (up to 1.252×) compared to the -O3 standard optimization flag combination on the cBench test suite, validating the feasibility and effectiveness of PreTuner.

Anomaly detection is often approached as an out-of-distribution (OOD) detection task, where a feature distribution from normal samples is constructed, and deviations are flagged as anomalies. This approach is dependent on manual labeling, as subtle visual anomalies can be easily overlooked, resulting in the potential for bias in labeling and subsequent unsatisfactory detection results. Based on the issue, we propose Anomaly Detection with Succinct Feature Filtering (ADSFF) for unlabeled samples. Our method avoids sample labeling bias and provides a solution to the coexistence of anomalous and normal features in the feature space of unlabeled samples. ADSFF includes a data preprocessing module and a feature filtering module, where the data preprocessing module improves the visibility of subtle anomalies, while the feature filtering module screens the local features of the samples. In feature filtering, we found that feedforward neural networks do not lose feature information during the feature transformation process. Consequently, we utilized feedforward neural networks for feature filtering and achieved expected results. Furthermore, we investigate the impact of sample imbalance on the task of anomaly detection using unlabeled samples. This paper assesses the performance of ADSFF using the MVTec AD and BeanTech Anomaly Detection (BTAD) datasets. The results demonstrate that ADSFF achieves an average area under the curve (AUC) of 0.978 on the MVTec AD and an average AUC of 0.942 on the BTAD. ADSFF outperformed other methods on seven test datasets in MVTec AD, achieving the highest average accuracy on MVTec AD.

In the current clinical healthcare environment, there is often a challenge where there is a wealth of unlabeled medical images, but a shortage of labeled images specific to particular medical cases. This limitation restricts the improvement of training effectiveness for deep learning models. This paper, starting from self-supervised learning and drawing inspiration from multi-task learning, explores a Vision Transformer-based self-supervised auxiliary task using MAE for medical image classification. This model establishes both a self-supervised auxiliary task and a supervised primary task, using a shared-weight VIT (Vision Transformer) encoder and synchronously updating network parameters. It effectively leverages both unlabeled and labeled medical images, resulting in promising outcomes. The model is alternately tested on two different medical image classification primary task datasets using three different types of self-supervised auxiliary task sets, and in most cases, it outperforms pure VIT models trained using both supervised and self-supervised learning methods under similar conditions.

The manual adjustment of compilation flags by compiler users is impractical due to the exponential size of the search space. To address this, machine learning-based compiler auto-tuning methods, particularly evolutionary algorithms, have been proposed. However, existing works use different benchmarks and experimental setups, making it difficult to compare the strengths and weaknesses of various algorithms. To address this, we present EAtuner, an evolutionary algorithm-based framework for compiler auto-tuning, with the goal of benchmarking and identifying suitable algorithms for compiler auto-tuning. We implement ten discrete binary evolutionary algorithms and evaluate their effectiveness on the LLVM compiler through experiments. Notably, eight of these algorithms have not been previously applied to compiler flag optimization problems before our work. The results show that all ten algorithms can effectively achieve compiler auto-tuning, resulting in an average speedup of 1.204. However, there are notable differences in the effectiveness and efficiency of each algorithm, particularly in optimization efficiency, which is positively correlated with the number of program compilations. Based on this, we classify the algorithms into three levels, with Differential Evolution (DE) showing significant advantages in optimization effectiveness and efficiency. Additionally, we provide a comprehensive summary of the applicability of compiler flags, the correlation between them, and their relationship with programs.

Low-dose PET imaging has been widely studied to reduce patient radiation exposure and improve hospital resource utilization. However, reducing the dose often introduces noise and blurs the tissue contours, motivating the development of deep-learning methods for reconstructing low-dose PET into fulldose PET. While these models can explore information within given low-dose PET patches, they overlook the anatomical variations present in whole-body PET imaging. We observe that in random sampling for whole-body PET, the probability of sampling difficult-to-reconstruct regions is the same as that of easily reconstructable regions, resulting in an imbalance that hinders the overall performance of the trained networks. Therefore, we propose a difficulty-adaptive sampling method that increases the sampling probability of challenging regions, reinforcing the network’s fitting capability for the poorly reconstructed areas during training and ultimately improving the reconstruction quality. Additionally, we design a noise level map as a guidance input during network training, enabling the network to recognize the noise level of each voxel in the low-dose PET, thereby enhancing the overall performance. The proposed method achieved fourth place in the MICCAI 2023 Ultra-low Dose PET Imaging Challenge.

We propose a novel ensemble learning method based on sample complementarity that considers sample complementarity through scientific model selection and weight allocation. Our approach aims to capture the essence of ensemble learning, which is to achieve complementary advantages between models. Our ensemble method shares a similar level of simplicity in operation as averaging ensemble learning methods, while demonstrating better performance. We first select the model with the best performance to participate in the ensemble. Then, we identify and filter samples that show poor performance in the best model according to the performance to form a subset. We select models with strong complementarity for ensemble learning by evaluating the performance metrics of other models on this subset to determine their level of complementarity with the best model. Furthermore, we reasonably assign ensemble weights by combining the performance of the best model and the sample complementarity of other models. The experimental results show that our proposed method outperforms the averaging ensemble learning methods on the DFUC2022 dataset, the Bank Marketing dataset, and the Predicting Facebook Comment Volume dataset, demonstrating its effectiveness. Our approach achieves 0.7352 mean Dice in the Diabetic Foot Ulcer Challenge 2022 on MICCAI 2022, ranking second on the Live Leaderboard. Our code will be released at https://github.com/xupin262/complementarity.

Multiple kernel clustering (MKC) aims to learn an optimal kernel to better serve for clustering from several precomputed basic kernels. Most MKC algorithms adhere to a common assumption that an optimal kernel is linearly combined by basic kernels. Based on a min-max framework, a newly proposed MKC method termed simple multiple kernel k -means (SimpleMKKM) can acquire a high-quality unified kernel. Although SimpleMKKM has achieved promising clustering performance, we observe that it cannot benefit from any prior knowledge. This would cause the learned partition matrix may seriously deviate from the expected one, especially in clustering tasks where the ground truth is absent during the learning course. To tackle this issue, we propose a novel algorithm termed regularized simple multiple kernel k -means with kernel average alignment (R-SMKKM-KAA). According to the experimental results of existing MKC algorithms, the average partition is a strong baseline to reflect true clustering. To gain knowledge from the average partition, we add the average alignment as a regularization term to prevent the learned unified partition from being far from the average partition. After that, we have designed an efficient solving algorithm to optimize the new resulting problem. In this way, both the incorporated prior knowledge and the combination of basic kernels are helpful to learn better unified partition. Consequently, the clustering performance can be significantly improved. Extensive experiments on nine common datasets have sufficiently demonstrated the effectiveness of incorporation of prior knowledge into SimpleMKKM.

Anomaly detection (AD), which models a given normal class and distinguishes it from the rest of abnormal classes, has been a long-standing topic with ubiquitous applications. As modern scenarios often deal with massive high-dimensional complex data spawned by multiple sources, it is natural to consider AD from the perspective of multiview deep learning. However, it has not been formally discussed by the literature and remains underexplored. Motivated by this blank, this article makes fourfold contributions: First, to the best of our knowledge, this is the first work that formally identifies and formulates the multiview deep AD problem. Second, we take recent advances in relevant areas into account and systematically devise various baseline solutions, which lays the foundation for multiview deep AD research. Third, to remedy the problem that limited benchmark datasets are available for multiview deep AD, we extensively collect the existing public data and process them into more than 30 multiview benchmark datasets via multiple means, so as to provide a better evaluation platform for multiview deep AD. Finally, by comprehensively evaluating the devised solutions on different types of multiview deep AD benchmark datasets, we conduct a thorough analysis on the effectiveness of the designed baselines and hopefully provide other researchers with beneficial guidance and insight into the new multiview deep AD topic.

Existing unsupervised outlier detection (OD) solutions face a grave challenge with surging visual data like images. Although deep neural networks (DNNs) prove successful for visual data, deep OD remains difficult due to OD’s unsupervised nature. This paper proposes a novel framework namedE$^{3}$Outlierthat can performeffective andend-to-end deep outlier removal. Its core idea is to introduceself-supervisioninto deep OD. Specifically, our major solution is to adopt a discriminative learning paradigm that creates multiple pseudo classes from given unlabeled data by various data operations, which enables us to apply prevalent discriminative DNNs (e.g. ResNet) to the unsupervised OD problem. Then, with theoretical and empirical demonstration, we argue that inlier priority, a property that encourages DNN to prioritize inliers during self-supervised learning, makes it possible to perform end-to-end OD. Meanwhile, unlike frequently-used outlierness measures (e.g. density, proximity) in previous OD methods, we explore network uncertainty and validate it as a highly effective outlierness measure, while two practical score refinement strategies are also designed to improve OD performance. Finally, in addition to the discriminative learning paradigm above, we also explore the solutions that exploit other learning paradigms (i.e. generative learning and contrastive learning) to introduce self-supervision forE$^{3}$Outlier. Such extendibility not only brings further performance gain on relatively difficult datasets, but also enablesE$^{3}$Outlierto be applied to other OD applications like video abnormal event detection. Extensive experiments demonstrate thatE$^{3}$Outliercan considerably outperform state-of-the-art counterparts by 10%-30% AUROC. Demo codes are available athttps://github.com/demonzyj56/E3Outlier.

Although great progress has been sparked in video anomaly detection (VAD) by deep neural networks (DNNs), existing solutions still fall short in two aspects: (1) The extraction of video events cannot be both precise and comprehensive. (2) The semantics and temporal context are under-explored. To tackle above issues, we are inspired by cloze tests in language education and propose a novel approach namedVisual Cloze Completion(VCC), which conducts VAD by completingvisual cloze tests(VCTs). Specifically, VCC first localizes each video event and encloses it into a spatio-temporal cube (STC). To realize both precise and comprehensive event extraction, appearance and motion are used as complementary cues to mark the object region associated with each event. For each marked region, a normalized patch sequence is extracted from several neighboring frames and stacked into a STC. With each patch and the patch sequence of a STC regarded as a visual “word” and “sentence” respectively, we deliberately erase a certain “word” (patch) to yield a VCT. Then, the VCT is completed by training DNNs to infer the erased patch and its optical flow via video semantics. Meanwhile, VCC fully exploits temporal context by alternatively erasing each patch in temporal context and creating multiple VCTs. Furthermore, we propose localization-level, event-level, model-level and decision-level solutions to enhance VCC, which can further exploit VCC’s potential and produce significant VAD performance improvement. Extensive experiments demonstrate that VCC achieves highly competitive VAD performance.

Multiple kernel clustering (MKC) has recently achieved remarkable progress in fusing multisource information to boost the clustering performance. However, the$\mathcal {O}({n}^{2})$memory consumption and$\mathcal {O}({n}^{3})$computational complexity prohibit these methods from being applied into median- or large-scale applications, where$n$denotes the number of samples. To address these issues, we carefully redesign the formulation of subspace segmentation-based MKC, which reduces the memory and computational complexity to$\mathcal {O}({n})$and$\mathcal {O}({n}^{2})$, respectively. The proposed algorithm adopts a novel sampling strategy to enhance the performance and accelerate the speed of MKC. Specifically, we first mathematically model the sampling process and then learn it simultaneously during the procedure of information fusion. By this way, the generated anchor point set can better serve data reconstruction across different views, leading to improved discriminative capability of the reconstruction matrix and boosted clustering performance. Although the integrated sampling process makes the proposed algorithm less efficient than the linear complexity algorithms, the elaborate formulation makes our algorithm straightforward for parallelization. Through the acceleration of GPU and multicore techniques, our algorithm achieves superior performance against the compared state-of-the-art methods on six datasets with comparable time cost to the linear complexity algorithms.

CD56, one of the latest tumor molecular markers, is a nerve cell adhesion molecule that can be used in the diagnosis and study of a variety of tumor cells. In the field of digital medical image processing, research on CD56 images is emerging. In CD56 images, cells are densely packed and the number of positive cells is low, these make it difficult to accurately detect cells in CD56 images. In this paper, we proposed a new hierarchy method to detect positive cells from CD56 images. Specifically, we first utilize an ExtremeNet to roughly detect positive and negative cells from an image. Then Shape Constraints are adopted to refine the detection results. We further trained a convolutional neural network to identify negative and positive cells more accurately, which is called Re-Discrimination. Experimental results showed that compared with several state-of-the-art one-stage object detection algorithms, the proposed method achieved the highest detection accuracy of cells in CD56 images.

Complex categorical data is often hierarchically coupled with heterogeneous relationships between attributes and attribute values and the couplings between objects. Such value-to-object couplings are heterogeneous with complementary and inconsistent interactions and distributions. Limited research exists on unlabeled categorical data representations, ignores the heterogeneous and hierarchical couplings, underestimates data characteristics and complexities, and overuses redundant information, etc. The deep representation learning of unlabeled categorical data is challenging, overseeing such value-to-object couplings, complementarity and inconsistency, and requiring large data, disentanglement, and high computational power. This work introduces a shallow but powerful UNsupervised heTerogeneous couplIng lEarning (UNTIE) approach for representing coupled categorical data by untying the interactions between couplings and revealing heterogeneous distributions embedded in each type of couplings. UNTIE is efficiently optimized w.r.t. a kernel k-means objective function for unsupervised representation learning of heterogeneous and hierarchical value-to-object couplings. Theoretical analysis shows that UNTIE can represent categorical data with maximal separability while effectively represent heterogeneous couplings and disclose their roles in categorical data. The UNTIE-learned representations make significant performance improvement against the state-of-the-art categorical representations and deep representation models on 25 categorical data sets with diversified characteristics.

In online learning, the dynamic regret metric chooses the reference oracle that may change over time, while the typical (static) regret metric assumes the reference solution to be constant over the whole time horizon. The dynamic regret metric is particularly interesting for applications, such as online recommendation (since the customers' preference always evolves over time). While the online gradient (OG) method has been shown to be optimal for the static regret metric, the optimal algorithm for the dynamic regret remains unknown. In this article, we show that proximal OG (a general version of OG) is optimum to the dynamic regret by showing that the proved lower bound matches the upper bound. It is highlighted that we provide a new and general lower bound of dynamic regret. It provides new understanding about the difficulty to follow the dynamics in the online setting.

In the field of human-computer interaction, video-based gesture detection has already sparked a lot of attention. Unlike typical RGB gesture movies, RGB-D gesture videos also record the depth information corresponding to all of the pixels in each frame, potentially reducing the impact of lighting and background fluctuations. To the best of our knowledge, current RGB-D gesture video datasets primarily focus on high classification accuracy while ignoring adequate illumination and backdrop variations that occur in real life. These will stifle the advancement of gesture recognition algorithms in some way. Instead, we present DG-13, an RGB-D gesture video dataset that properly accounts for various brightness and backdrops. On the proposed DG-13 dataset, benchmark evaluations of five exemplary light-weighted 3D CNN networks are also provided. Experiment results reveal that when there are significant illumination and backdrop differences, RGB-D gesture video can successfully aid increase classification accuracy and numerous other classification metrics. The DG-13 dataset and benchmark codes are public at https://github.com/xiaooo-jian/DG-13.

Recently, convex-concave bilinear Saddle Point Problems (SPP) is widely used in lasso problems, Support Vector Machines, game theory, and so on. Previous researches have proposed many methods to solve SPP, and present their convergence rate theoretically. To achieve linear convergence, analysis in those previouse studies requires strong convexity of φ( z ). But, we find the linear convergence can also be achieved even for a general convex but not strongly convex φ( z ). In the article, by exploiting the strong duality of SPP, we propose a new method to solve SPP, and achieve the linear convergence. We present a new general sufficient condition to achieve linear convergence, but do not require the strong convexity of φ( z ). Furthermore, a more efficient method is also proposed, and its convergence rate is analyzed in theoretical. Our analysis shows that the well conditioned φ( z ) is necessary to improve the efficiency of our method. Finally, we conduct extensive empirical studies to evaluate the convergence performance of our methods.

Simultaneous clustering and optimization (SCO) has recently drawn much attention due to its wide range of practical applications. Many methods have been previously proposed to solve this problem and obtain the optimal model. However, when a dataset evolves over time, those existing methods have to update the model frequently to guarantee accuracy; such updating is computationally infeasible. In this paper, we propose a new formulation of SCO to handle evolving datasets. Specifically, we propose a new variant of the alternating direction method of multipliers (ADMM) to solve this problem efficiently. The guarantee of model accuracy is analyzed theoretically for two specific tasks: ridge regression and convex clustering. Extensive empirical studies confirm the effectiveness of our method.

Multi-view spectral clustering aims to group data into different categories by optimally exploring complementary information from multiple Laplacian matrices. However, existing methods usually linearly combine a group of pre-specified first-order Laplacian matrices to construct an optimal Laplacian matrix, which may result in limited representation capability and insufficient information exploitation. In this paper, we propose a novel optimal neighborhood multi-view spectral clustering (ONMSC) algorithm to address these issues. Specifically, the proposed algorithm generates an optimal Laplacian matrix by searching the neighborhood of both the linear combination of the first-order and high-order base Laplacian matrices simultaneously. This design enhances the representative capacity of the optimal Laplacian and better utilizes the hidden high-order connection information, leading to improved clustering performance. An efficient algorithm with proved convergence is designed to solve the resultant optimization problem. Extensive experimental results on 9 datasets demonstrate the superiority of our algorithm against state-of-the-art methods, which verifies the effectiveness and advantages of the proposed ONMSC.

As a vital topic in media content interpretation, video anomaly detection (VAD) has made fruitful progress via deep neural network (DNN). However, existing methods usually follow a reconstruction or frame prediction routine. They suffer from two gaps: (1) They cannot localize video activities in a both precise and comprehensive manner. (2) They lack sufficient abilities to utilize high-level semantics and temporal context information. Inspired by frequently-used cloze test in language study, we propose a brand-new VAD solution named Video Event Completion (VEC) to bridge gaps above: First, we propose a novel pipeline to achieve both precise and comprehensive enclosure of video activities. Appearance and motion are exploited as mutually complimentary cues to localize regions of interest (RoIs). A normalized spatio-temporal cube (STC) is built from each RoI as a video event, which lays the foundation of VEC and serves as a basic processing unit. Second, we encourage DNN to capture high-level semantics by solving a visual cloze test. To build such a visual cloze test, a certain patch of STC is erased to yield an incomplete event (IE). The DNN learns to restore the original video event from the IE by inferring the missing patch. Third, to incorporate richer motion dynamics, another DNN is trained to infer erased patches' optical flow. Finally, two ensemble strategies using different types of IE and modalities are proposed to boost VAD performance, so as to fully exploit the temporal context and modality information for VAD. VEC can consistently outperform state-of-the-art methods by a notable margin (typically 1.5%-5% AUROC) on commonly-used VAD benchmarks. Our codes and results can be verified at github.com/yuguangnudt/VEC_VAD

Multiple kernel learning (MKL) has been intensively studied during the past decade. It optimally combines the multiple channels of each sample to improve classification performance. However, existing MKL algorithms cannot effectively handle the situation where some channels of the samples are missing, which is not uncommon in practical applications. This paper proposes three absent MKL (AMKL) algorithms to address this issue. Different from existing approaches where missing channels are first imputed and then a standard MKL algorithm is deployed on the imputed data, our algorithms directly classify each sample based on its observed channels, without performing imputation. Specifically, we define a margin for each sample in its own relevant space, a space corresponding to the observed channels of that sample. The proposed AMKL algorithms then maximize the minimum of all sample-based margins, and this leads to a difficult optimization problem. We first provide two two-step iterative algorithms to approximately solve this problem. After that, we show that this problem can be reformulated as a convex one by applying the representer theorem. This makes it readily be solved via existing convex optimization packages. In addition, we provide a generalization error bound to justify the proposed AMKL algorithms from a theoretical perspective. Extensive experiments are conducted on nine UCI and six MKL benchmark datasets to compare the proposed algorithms with existing imputation-based methods. As demonstrated, our algorithms achieve superior performance and the improvement is more significant with the increase of missing ratio.

Multiple kernel clustering (MKC) algorithms optimally combine a group of pre-specified base kernel matrices to improve clustering performance. However, existing MKC algorithms cannot efficiently address the situation where some rows and columns of base kernel matrices are absent. This paper proposes two simple yet effective algorithms to address this issue. Different from existing approaches where incomplete kernel matrices are first imputed and a standard MKC algorithm is applied to the imputed kernel matrices, our first algorithm integrates imputation and clustering into a unified learning procedure. Specifically, we perform multiple kernel clustering directly with the presence of incomplete kernel matrices, which are treated as auxiliary variables to be jointly optimized. Our algorithm does not require that there be at least one complete base kernel matrix over all the samples. Also, it adaptively imputes incomplete kernel matrices and combines them to best serve clustering. Moreover, we further improve this algorithm by encouraging these incomplete kernel matrices to mutually complete each other. The three-step iterative algorithm is designed to solve the resultant optimization problems. After that, we theoretically study the generalization bound of the proposed algorithms. Extensive experiments are conducted on 13 benchmark data sets to compare the proposed algorithms with existing imputation-based methods. Our algorithms consistently achieve superior performance and the improvement becomes more significant with increasing missing ratio, verifying the effectiveness and advantages of the proposed joint imputation and clustering.

Automatic image segmentation is an essential step for many medical image analysis applications, include computer-aided radiation therapy, disease diagnosis, and treatment effect evaluation. One of the major challenges for this task is the blurry nature of medical images (e.g., CT, MR and, microscopic images), which can often result in low-contrast and vanishing boundaries. With the recent advances in convolutional neural networks, vast improvements have been made for image segmentation, mainly based on the skip-connection-linked encoder-decoder deep architectures. However, in many applications (with adjacent targets in blurry images), these models often fail to accurately locate complex boundaries and properly segment tiny isolated parts. In this paper, we aim to provide a method for blurry medical image segmentation and argue that skip connections are not enough to help accurately locate indistinct boundaries. Accordingly, we propose a novel high-resolution multi-scale encoder-decoder network (HMEDN), in which multi-scale dense connections are introduced for the encoder-decoder structure to finely exploit comprehensive semantic information. Besides skip connections, extra deeply-supervised high-resolution pathways (comprised of densely connected dilated convolutions) are integrated to collect high-resolution semantic information for accurate boundary localization. These pathways are paired with a difficulty-guided cross-entropy loss function and a contour regression task to enhance the quality of boundary detection. Extensive experiments on a pelvic CT image dataset, a multi-modal brain tumor dataset, and a cell segmentation dataset show the effectiveness of our method for 2D/3D semantic segmentation and 2D instance segmentation, respectively. Our experimental results also show that besides increasing the network complexity, raising the resolution of semantic feature maps can largely affect the overall model performance. For different tasks, finding a balance between these two factors can further improve the performance of the corresponding network.

As a metric to measure the performance of an online method, dynamic regret with switching cost has drawn much attention for online decision making problems. Although the sublinear regret has been provided in much previous research, we still have little knowledge about the relation between the dynamic regret and the switching cost . In the article, we investigate the relation for two classic online settings: Online Algorithms (OA) and Online Convex Optimization (OCO). We provide a new theoretical analysis framework that shows an interesting observation; that is, the relation between the switching cost and the dynamic regret is different for settings of OA and OCO. Specifically, the switching cost has significant impact on the dynamic regret in the setting of OA. But it does not have an impact on the dynamic regret in the setting of OCO. Furthermore, we provide a lower bound of regret for the setting of OCO, which is same with the lower bound in the case of no switching cost. It shows that the switching cost does not change the difficulty of online decision making problems in the setting of OCO.

Deep clustering gains superior performance than conventional clustering by jointly performing feature learning and cluster assignment. Although numerous deep clustering algorithms have emerged in various applications, most of them fail to learn robust cluster-oriented features which in turn hurts the final clustering performance. To solve this problem, we propose a two-stage deep clustering algorithm by incorporating data augmentation and self-paced learning. Specifically, in the first stage, we learn robust features by training an autoencoder with examples that are augmented by random shifting and rotating the given clean examples. Then, in the second stage, we encourage the learned features to be cluster-oriented by alternatively finetuning the encoder with the augmented examples and updating the cluster assignments of the clean examples. During finetuning the encoder, the target of each augmented example in the loss function is the center of the cluster to which the clean example is assigned. The targets may be computed incorrectly, and the examples with incorrect targets could mislead the encoder network. To stabilize the network training, we select most confident examples in each iteration by utilizing the adaptive self-paced learning. Extensive experiments validate that our algorithm outperforms the state of the arts on four image datasets.

Multiple kernel clustering (MKC) has been intensively studied during the last few decades. Even though they demonstrate promising clustering performance in various applications, existing MKC algorithms do not sufficiently consider the intrinsic neighborhood structure among base kernels, which could adversely affect the clustering performance. In this paper, we propose a simple yet effective neighbor-kernel-based MKC algorithm to address this issue. Specifically, we first define a neighbor kernel, which can be utilized to preserve the block diagonal structure and strengthen the robustness against noise and outliers among base kernels. After that, we linearly combine these base neighbor kernels to extract a consensus affinity matrix through an exact-rank-constrained subspace segmentation. The naturally possessed block diagonal structure of neighbor kernels better serves the subsequent subspace segmentation, and in turn, the extracted shared structure is further refined through subspace segmentation based on the combined neighbor kernels. In this manner, the above two learning processes can be seamlessly coupled and negotiate with each other to achieve better clustering. Furthermore, we carefully design an efficient iterative optimization algorithm with proven convergence to address the resultant optimization problem. As a by-product, we reveal an interesting insight into the exact-rank constraint in ridge regression by careful theoretical analysis: it back-projects the solution of the unconstrained counterpart to its principal components. Comprehensive experiments have been conducted on several benchmark data sets, and the results demonstrate the effectiveness of the proposed algorithm.

Incomplete multi-view clustering (IMVC) optimally fuses multiple pre-specified incomplete views to improve clustering performance. Among various excellent solutions, the recently proposed multiple kernel k-means with incomplete kernels (MKKM-IK) forms a benchmark, which redefines IMVC as a joint optimization problem where the clustering and kernel matrix imputation tasks are alternately performed until convergence. Though demonstrating promising performance in various applications, we observe that the manner of kernel matrix imputation in MKKM-IK would incur intensive computational and storage complexities, overcomplicated optimization and limitedly improved clustering performance. In this paper, we propose an Efficient and Effective Incomplete Multi-view Clustering (EE-IMVC) algorithm to address these issues. Instead of completing the incomplete kernel matrices, EE-IMVC proposes to impute each incomplete base matrix generated by incomplete views with a learned consensus clustering matrix. We carefully develop a three-step iterative algorithm to solve the resultant optimization problem with linear computational complexity and theoretically prove its convergence. Further, we conduct comprehensive experiments to study the proposed EE-IMVC in terms of clustering accuracy, running time, evolution of the learned consensus clustering matrix and the convergence. As indicated, our algorithm significantly and consistently outperforms some state-of-the-art algorithms with much less running time and memory.

Efficient detection of outliers from massive data with a high outlier ratio is challenging but not explicitly discussed yet. In such a case, existing methods either suffer from poor robustness or require expensive computations. This paper proposes a Low-rank based Efficient Outlier Detection (LEOD) framework to achieve favorable robustness against high outlier ratios with much cheaper computations. Specifically, it is worth highlighting the following aspects of LEOD: (1) Our framework exploits the low-rank structure embedded in the similarity matrix and considers inliers/outliers equally based on this low-rank structure, which facilitates us to encourage satisfying robustness with low computational cost later; (2) A novel re-weighting algorithm is derived as a new general solution to the constrained eigenvalue problem, which is a major bottleneck for the optimization process. Instead of the high space and time complexity (O((2n)2)/O((2n)3)) required by the classic solution, our algorithm enjoys O(n) space complexity and a faster optimization speed in the experiments; (3) A new alternative formulation is proposed for further acceleration of the solution process, where a cheap closed-form solution can be obtained. Experiments show that LEOD achieves strong robustness under an outlier ratio from 20% to 60%, while it is at most 100 times more memory efficient and 1000 times faster than its previous counterpart that attains comparable performance. The codes of LEOD are publicly available at https://github.com/demonzyj56/LEOD.

Existing deep neural networks mainly focus on learning transformation invariant features. However, it is the equivariant features that are more adequate for general purpose tasks. Unfortunately, few work has been devoted to learning equivariant features. To fill this gap, in this paper, we propose an affine equivariant autoencoder to learn features that are equivariant to the affine transformation in an unsupervised manner. The objective consists of the self-reconstruction of the original example and affine transformed example, and the approximation of the affine transformation function, where the reconstruction makes the encoder a valid feature extractor and the approximation encourages the equivariance. Extensive experiments are conducted to validate the equivariance and discriminative ability of the features learned by our affine equivariant autoencoder.

Multi-view clustering (MVC) optimally integrates complementary information from different views to improve clustering performance. Although demonstrating promising performance in many applications, we observe that most of existing methods directly combine multiple views to learn an optimal similarity for clustering. These methods would cause intensive computational complexity and over-complicated optimization. In this paper, we theoretically uncover the connection between existing k-means clustering and the alignment between base partitions and consensus partition. Based on this observation, we propose a simple but effective multi-view algorithm termed {Multi-view Clustering via Late Fusion Alignment Maximization (MVC-LFA)}. In specific, MVC-LFA proposes to maximally align the consensus partition with the weighted base partitions. Such a criterion is beneficial to significantly reduce the computational complexity and simplify the optimization procedure. Furthermore, we design a three-step iterative algorithm to solve the new resultant optimization problem with theoretically guaranteed convergence. Extensive experiments on five multi-view benchmark datasets demonstrate the effectiveness and efficiency of the proposed MVC-LFA.

Video anomaly detection is a valuable but challenging task, especially in the field of surveillance videos for public safety. Almost all existing methods tackle the problem under the supervised setting and only a few attempts are conducted on the unsupervised learning. To avoid the cost of labeling training videos, this paper proposes to discriminate anomaly by a novel two-stage framework in a fully unsupervised manner. Unlike previous unsupervised approaches using local change detection to discover abnormality, our method enjoys the global information from video context by considering the pair-wise similarity of all video events. In this way, our method formulates video anomaly detection as an extension of unsupervised one-class learning, which has not been explored in the literature of video anomaly detection. Specifically, our method consists of two stages: The first stage of our kernel-based method, named Low-rank based Unsupervised One-class Learning with Ridge Regression (LR-UOCL-RR), reformulates the optimization goal of UOCL with ridge regression to avoid expensive computation, which enables our method to handle massive unlabeled data from videos. In the second stage, the estimated normal video events from the first stage are fed into the one-class support vector machine to refine the profile around normal events and enhance the performance. The experimental results conducted on two challenging video benchmarks indicate that our method is considerably superior, up to 15:7% AUC gain, to the state-of-the-art methods in the unsupervised anomaly detection task and even better than several supervised approaches.

Despite the wide success of deep neural networks (DNN), little progress has been made on end-to-end unsupervised outlier detection (UOD) from high dimensional data like raw images. In this paper, we propose a framework named E^3Outlier, which can perform UOD in a both effective and end-to-end manner: First, instead of the commonly-used autoencoders in previous end-to-end UOD methods, E^3Outlier for the first time leverages a discriminative DNN for better representation learning, by using surrogate supervision to create multiple pseudo classes from original unlabelled data. Next, unlike classic UOD that utilizes data characteristics like density or proximity, we exploit a novel property named inlier priority to enable end-to-end UOD by discriminative DNN. We demonstrate theoretically and empirically that the intrinsic class imbalance of inliers/outliers will make the network prioritize minimizing inliers' loss when inliers/outliers are indiscriminately fed into the network for training, which enables us to differentiate outliers directly from DNN's outputs. Finally, based on inlier priority, we propose the negative entropy based score as a simple and effective outlierness measure. Extensive evaluations show that E^3Outlier significantly advances UOD performance by up to 30% AUROC against state-of-the-art counterparts, especially on relatively difficult benchmarks.

The k-means clustering is arguably the most popular clustering technique, which has been applied to a wide range of applications. Lloyd’s algorithm is the most popular algorithm for the k-means problem due to its simplicity, geometric intuition and effectiveness. However, in a naive implementation of Lloyd’s algorithm, we need to compute the Euclidean distances between all data points and all cluster centers in each iteration. This prevents the algorithm from being scalable to large datasets and becomes the main bottleneck. To overcome the problem, this paper proposes two scalable k-means algorithms, Scalable Lloyd’s k-means and Scalable Mini-Batch k-means. They are distributed extensions of Lloyd’s algorithm and the mini-batch k-means, respectively. The two algorithms are all use the data-parallel technique to scale beyond computational and memory limits of a single machine. Meanwhile, they are all based on the parameter server abstraction that facilitates the data-parallel computation. The first algorithm can find better quality of solutions, while the second one converges to a modest solution faster. They both have good scalability and totally do in-memory computation. In addition, we propose a new aggregation method for Scalable Mini-Batch k-means. Extensive experiments conducted on four large-scale datasets show that our proposed algorithms have good convergence performance and achieve almost ideal speedup.

Incomplete multi-view clustering optimally integrates a group of pre-specified incomplete views to improve clustering performance. Among various excellent solutions, multiple kernel $k$k-means with incomplete kernels forms a benchmark, which redefines the incomplete multi-view clustering as a joint optimization problem where the imputation and clustering are alternatively performed until convergence. However, the comparatively intensive computational and storage complexities preclude it from practical applications. To address these issues, we propose Late Fusion Incomplete Multi-view Clustering (LF-IMVC) which effectively and efficiently integrates the incomplete clustering matrices generated by incomplete views. Specifically, our algorithm jointly learns a consensus clustering matrix, imputes each incomplete base matrix, and optimizes the corresponding permutation matrices. We develop a three-step iterative algorithm to solve the resultant optimization problem with linear computational complexity and theoretically prove its convergence. Further, we conduct comprehensive experiments to study the proposed LF-IMVC in terms of clustering accuracy, running time, advantages of late fusion multi-view clustering, evolution of the learned consensus clustering matrix, parameter sensitivity and convergence. As indicated, our algorithm significantly and consistently outperforms some state-of-the-art algorithms with much less running time and memory.

Recently, network lasso has dawn much attention due to its remarkable performance on simultaneous clustering and optimization. However, it usually suffers from the imperfect data (noise, missing values, etc.), and yields sub-optimal solutions. The reason is that it finds the similar instances according to their features directly, which is usually impacted by the imperfect data, and thus returns sub-optimal results. In this paper, we propose triangle lasso to avoid its disadvantage for graph datasets. In a graph dataset, each instance is represented by a vertex. If two instances have many common adjacent vertices, they tend to become similar. Although some instances are profiled by the imperfect data, it is still able to find the similar counterparts. Furthermore, we develop an efficient algorithm based on Alternating Direction Method of Multipliers (ADMM) to obtain a moderately accurate solution. In addition, we present a dual method to obtain the accurate solution with the low additional time consumption. We demonstrate through extensive numerical experiments that triangle lasso is robust to the imperfect data. It usually yields a better performance than the state-of-the-art method when performing data analysis tasks in practical scenarios.

Determining the number of clusters is important but challenging, especially for data of high dimension. In this paper, we propose Deep Embedding Determination (DED), a method that can solve jointly for the unknown number of clusters and feature extraction. DED first combines the virtues of the convolutional autoencoder and the t-SNE technique to extract low dimensional embedded features. Then it determines the number of clusters using an improved density-based clustering algorithm. Our experimental evaluation on image datasets shows significant improvement over state-of-the-art methods and robustness with respect to hyperparameter settings.

It is challenging to perform k-means clustering on a large scale dataset efficiently. One of the reasons is that k-means needs to scan a batch of training data to update the cluster centers at every iteration, which is time-consuming. In the paper, we propose a variance reduced k-mean VRKM, which outperforms the state-of-the-art method, and obtain 4× speedup for large-scale clustering. The source code is available on https://github.com/YaweiZhao/VRKM_sofia-ml.

Deep Embedded Clustering (DEC) surpasses traditional clustering algorithms by jointly performing feature learning and cluster assignment. Although a lot of variants have emerged, they all ignore a crucial ingredient, \emph{data augmentation}, which has been widely employed in supervised deep learning models to improve the generalization. To fill this gap, in this paper, we propose the framework of Deep Embedded Clustering with Data Augmentation (DEC-DA). Specifically, we first train an autoencoder with the augmented data to construct the initial feature space. Then we constrain the embedded features with a clustering loss to further learn clustering-oriented features. The clustering loss is composed of the target (pseudo label) and the actual output of the feature learning model, where the target is computed by using clean (non-augmented) data, and the output by augmented data. This is analogous to supervised training with data augmentation and expected to facilitate unsupervised clustering too. Finally, we instantiate five DEC-DA based algorithms. Extensive experiments validate that incorporating data augmentation can improve the clustering performance by a large margin. Our DEC-DA algorithms become the new state of the art on various datasets.

The recently proposed multiple kernel k-means with incomplete kernels (MKKM-IK) optimally integrates a group of pre-specified incomplete kernel matrices to improve clustering performance. Though it demonstrates promising performance in various applications, we observe that it does not \emph{sufficiently consider the local structure among data and indiscriminately forces all pairwise sample similarity to equally align with their ideal similarity values}. This could make the incomplete kernels less effectively imputed, and in turn adversely affect the clustering performance. In this paper, we propose a novel localized incomplete multiple kernel k-means (LI-MKKM) algorithm to address this issue. Different from existing MKKM-IK, LI-MKKM only requires the similarity of a sample to its k-nearest neighbors to align with their ideal similarity values. This helps the clustering algorithm to focus on closer sample pairs that shall stay together and avoids involving unreliable similarity evaluation for farther sample pairs. We carefully design a three-step iterative algorithm to solve the resultant optimization problem and theoretically prove its convergence. Comprehensive experiments on eight benchmark datasets demonstrate that our algorithm significantly outperforms the state-of-the-art comparable algorithms proposed in the recent literature, verifying the advantage of considering local structure.

Abnormal event detection in video surveillance is a valuable but challenging problem. Most methods adopt a supervised setting that requires collecting videos with only normal events for training. However, very few attempts are made under unsupervised setting that detects abnormality without priorly knowing normal events. Existing unsupervised methods detect drastic local changes as abnormality, which overlooks the global spatio-temporal context. This paper proposes a novel unsupervised approach, which not only avoids manually specifying normality for training as supervised methods do, but also takes the whole spatio-temporal context into consideration. Our approach consists of two stages: First, normality estimation stage trains an autoencoder and estimates the normal events globally from the entire unlabeled videos by a self-adaptive reconstruction loss thresholding scheme. Second, normality modeling stage feeds the estimated normal events from the previous stage into one-class support vector machine to build a refined normality model, which can further exclude abnormal events and enhance abnormality detection performance. Experiments on various benchmark datasets reveal that our method is not only able to outperform existing unsupervised methods by a large margin (up to 14.2% AUC gain), but also favorably yields comparable or even superior performance to state-of-the-art supervised methods.

With the increasing demand of big data technology, there has been a growing interest of introducing high performance computing in computer science curriculum. One challenge in helping students understand the nature of efficiency and scalability issues in high performance computing is the lack of opportunities for them to be engaged in large-scale applications that run on supercomputer system architecture. This poster presents a collection of example projects that have been used in a parallel computing course in multiple universities in China, including National University of Defense Technology, Sun Yat-sen University and Hunan University. These projects were adopted from a wide range of scientific computing applications such as CFD, text mining of biomedical literature and so on. The large-scale computing resource for courses is supported by two National Supercomputing Centers, one in Guangzhou and the other in Changsha. The poster describes the background, objective, structure, task, practice process and outcome for each project. It also discusses the impact on student understanding all kinds of key topics and major challenges related to computational efficiency and scalability. Such projects build a positive practical environment to make students indulge in doing all kinds of interesting and helpful trials to validate their assumptions, especially when they have different perspectives or results for one problem. The poster presents our design evaluation rubric to reflect the effectiveness of our practice, as well as the statistics about the students" achievements for the last three semesters.

In image retrieval, the bag‐of‐visual‐words model‐based approaches combined with the spatial verification (SP) post‐processing step have achieved considerable progress. However, in practice, especially for retrieving landmark images, the authors have observed that this baseline suffers from the problem of burst matches. This issue is caused by repetitive visual patterns that appear frequently among images. Local features derived from these burst patterns can redundantly match others, resulting in many invalid matches that vote over‐estimated similarity scores for irrelevant images. Essentially, this problem can be mainly attributed to two reasons, (i) the non‐exclusive matching leads to one‐to‐many matches, (ii) the SP fails to filter burst matches that are closely located. To tackle this problem, a burstiness detection approach using geometric and visual word information of local features is proposed. Firstly, a geometric filtering strategy is employed to remove matches that are not consistent with global scale variation. Then, the one‐to‐one matching strategy is applied to detect and eliminate one‐to‐many matches. Finally, a down‐weighting burstiness strategy is adopted to penalise the voting weight of burst matches. Experimental results on three public datasets demonstrate that the proposed approach can achieve a comparable or even better accuracy over other popular approaches.

Learning appropriate metric is critical for effectively capturing complex data characteristics. The metric learning of categorical data with hierarchical coupling relationships and local heterogeneous distributions is very challenging yet rarely explored. This paper proposes a Heterogeneous mEtric Learning with hIerarchical Couplings (HELIC for short) for this type of categorical data. HELIC captures both low-level value-to-attribute and high-level attribute-to-class hierarchical couplings, and reveals the intrinsic heterogeneities embedded in each level of couplings. Theoretical analyses of the effectiveness and generalization error bound verify that HELIC effectively represents the above complexities. Extensive experiments on 30 data sets with diverse characteristics demonstrate that HELIC-enabled classification significantly enhances the accuracy (up to 40.93 percent), compared with five state-of-the-art baselines.

Multiple kernel clustering (MKC) algorithms optimally combine a group of pre-specified base kernels to improve clustering performance. However, existing MKC algorithms cannot efficiently address the situation where some rows and columns of base kernels are absent. This paper proposes a simple while effective algorithm to address this issue. Different from existing approaches where incomplete kernels are firstly imputed and a standard MKC algorithm is applied to the imputed kernels, our algorithm integrates imputation and clustering into a unified learning procedure. Specifically, we perform multiple kernel clustering directly with the presence of incomplete kernels, which are treated as auxiliary variables to be jointly optimized. Our algorithm does not require that there be at least one complete base kernel over all the samples. Also, it adaptively imputes incomplete kernels and combines them to best serve clustering. A three-step iterative algorithm with proved convergence is designed to solve the resultant optimization problem. Extensive experiments are conducted on four benchmark data sets to compare the proposed algorithm with existing imputation-based methods. Our algorithm consistently achieves superior performance and the improvement becomes more significant with increasing missing ratio, verifying the effectiveness and advantages of the proposed joint imputation and clustering.

Multiple kernel $k$-means (MKKM) aims to improve clustering performance by learning an optimal kernel, which is usually assumed to be a linear combination of a group of pre-specified base kernels. However, we observe that this assumption could: i) cause limited kernel representation capability; and ii) not sufficiently consider the negotiation between the process of learning the optimal kernel and that of clustering, leading to unsatisfying clustering performance. To address these issues, we propose an optimal neighborhood kernel clustering (ONKC) algorithm to enhance the representability of the optimal kernel and strengthen the negotiation between kernel learning and clustering. We theoretically justify this ONKC by revealing its connection with existing MKKM algorithms. Furthermore, this justification shows that existing MKKM algorithms can be viewed as a special case of our approach and indicates the extendability of the proposed ONKC for designing better clustering algorithms. An efficient algorithm with proved convergence is designed to solve the resultant optimization problem. Extensive experiments have been conducted to evaluate the clustering performance of the proposed algorithm. As demonstrated, our algorithm significantly outperforms the state-of-the-art ones in the literature, verifying the effectiveness and advantages of ONKC.

Deep clustering learns deep feature representations that favor clustering task using neural networks. Some pioneering work proposes to simultaneously learn embedded features and perform clustering by explicitly defining a clustering oriented loss. Though promising performance has been demonstrated in various applications, we observe that a vital ingredient has been overlooked by these work that the defined clustering loss may corrupt feature space, which leads to non-representative meaningless features and this in turn hurts clustering performance. To address this issue, in this paper, we propose the Improved Deep Embedded Clustering (IDEC) algorithm to take care of data structure preservation. Specifically, we manipulate feature space to scatter data points using a clustering loss as guidance. To constrain the manipulation and maintain the local structure of data generating distribution, an under-complete autoencoder is applied. By integrating the clustering loss and autoencoder's reconstruction loss, IDEC can jointly optimize cluster labels assignment and learn features that are suitable for clustering with local structure preservation. The resultant optimization problem can be effectively solved by mini-batch stochastic gradient descent and backpropagation. Experiments on image and text datasets empirically validate the importance of local structure preservation and the effectiveness of our algorithm.

Stochastic gradient descent (SGD) is a commonly used technique in large-scale machine learning tasks, but its convergence is slow due to the inherent variance. In recent years, a popular method, Stochastic Variance Reduced Gradient (SVRG), addresses this shortcoming via computing the full gradient of the entire dataset in each epoch. However, conventional SVRG and its variants usually need to identify a hyperparameter - the epoch size, which is essential to the convergence performance. Few previous studies discuss how to systematically find a suitable value for that hyper-parameter, which makes it hard to gain a good convergence performance in practical machine learning applications. In this paper, we propose a new stochastic gradient descent named AESVRG, which introduces variance reduction and computes the full gradient adaptively. Its enhanced implementation, AESVRG+, has a convergence performance that can outplay existing SVRG with fine-tuned epoch sizes. An extensive evaluation illustrates the significant performance improvement of our method.

In this paper, we focus on retrieving video by an image querying. Current approaches involve extracting hand- craft features from each key-frame of videos, which is memory cost. We propose to use deep feature deriving from deep neural network to tackle this issue. Specifically, deep feature is employed to detect shots consisting of similar key-frames and represent them by different aggregation strategies, which can avoid saving redundant key-frames of videos. In addition, to discount the contribution of background, we propose a two-way localization approach, which searches the best matched regions between query and video key-frames. Then, the updated similarity built upon the best matched regions is utilized to re-rank initial retrieval results for further refinement. Experimental results over the public CNN2h dataset demonstrate the effectiveness of the proposed approach.

Automatic identification of abnormal cervical cells, including feature representation, feature combination and classification strategy, is highly demanded in women's annual cervical cancer screenings. However, previous methods only deal with one or two of these three phases, and currently there is few complete framework for this problem. A novel three‐phrase boosting framework is proposed for the detection of abnormal cells from cervical smear images. First, the authors extract 160 dimensional features with respect to each cervical cell from three aspects, including cytology morphology, chromatin pathology and region intensity. In particular, 106 dimensional chromatin pathology features are newly adopted to describe the nucleus textural transformation. Second, an adaptive feature combination method is introduced to select the optimal feature patterns, which can combine all features using a reinforced margin‐based approach with the heuristic knowledge. Finally, a two‐stage classification strategy is presented to reduce erroneous classification abnormal cells using two different classifiers. Experimental results achieve state‐of‐the‐art performance and the proposed framework outperforms the other 16 compared detection methods.

One-class classification (OCC) models a set of target data from one class to detect outliers. OCC approaches like one-class support vector machine (OCSVM) and support vector data description (SVDD) have wide practical applications. Recently, one-class extreme learning machine (OCELM), which inherits the fast learning speed of original ELM and achieves equivalent or higher data description performance than OCSVM and SVDD, is proposed as a promising alternative. However, OCELM faces the same thorny parameter selection problem as OCSVM and SVDD. It significantly affects the performance of OCELM and remains under-explored. This paper proposes minimal spanning tree (MST)-GEN, an automatic way to select proper parameters for OCELM. Specifically, we first build a n -round MST to model the structure and distribution of the given target set. With information from n -round MST, a controllable number of pseudo outliers are generated by edge pattern detection and a novel "repelling" process, which readily overcomes two fundamental problems in previous outlier generation methods: where and how many pseudo outliers should be generated. Unlike previous methods that only generate pseudo outliers, we further exploit n -round MST to generate pseudo target data, so as to avoid the time-consuming cross-validation process and accelerate the parameter selection. Extensive experiments on various datasets suggest that the proposed method can select parameters for OCELM in a highly efficient and accurate manner when compared with existing methods, which enables OCELM to achieve better OCC performance in OCC applications. Furthermore, our experiments show that MST-GEN can also be favorably applied to other prevalent OCC methods like OCSVM and SVDD.

Multiple kernel k-means (MKKM) clustering aims to optimally combine a group of pre-specified kernels to improve clustering performance. However, we observe that existing MKKM algorithms do not sufficiently consider the correlation among these kernels. This could result in selecting mutually redundant kernels and affect the diversity of information sources utilized for clustering, which finally hurts the clustering performance. To address this issue, this paper proposes an MKKM clustering with a novel, effective matrix-induced regularization to reduce such redundancy and enhance the diversity of the selected kernels. We theoretically justify this matrix-induced regularization by revealing its connection with the commonly used kernel alignment criterion. Furthermore, this justification shows that maximizing the kernel alignment for clustering can be viewed as a special case of our approach and indicates the extendability of the proposed matrix-induced regularization for designing better clustering algorithms. As experimentally demonstrated on five challenging MKL benchmark data sets, our algorithm significantly improves existing MKKM and consistently outperforms the state-of-the-art ones in the literature, verifying the effectiveness and advantages of incorporating the proposed matrix-induced regularization.

In an abnormal cervical cell detection system the discriminated abilities of different features are not same so the optimized combination method of all features is an essential component to this system. Feature selection can improve each feature utilization ratio and the performance of the classification problem. The previous efforts of cervical abnormal cell detection are mainly focused on changing feature space into a new one by using a binary weight vector. In this work, the binary weight values are extended to the multiple weight values. According to the statistical distribution situation of the data, an adaptive margin-based weighted feature selection method is proposed in this paper. This method performs best compared with the other 3 methods. The experimental result achieves 96% accuracy in a real-world cervical smear image dataset.

Correlation tracker has made a huge success in visual object tracking. However, it is mainly because that the tracker cannot catch the occurrence of appearance changes, tracking based on correlation filters often drifts due to the unexpected appearance changes caused by occlusion, deformation and background clutter. In this paper, we propose a new method to detect the case when the tracker encountered the unexpected appearance changes. This method uses the following points: 1) Filter response curve would decreases dramatically when target suffers heavy appearance changes. 2) Features extracted from deeper layers of convolutional neural networks (CNNs) have more semantics information and features extracted from shadower layers have more spatial information. Extensive experimental results on several public benchmark datasets show that the proposed method can deal with the appearance changes effectively.

Domain adaptation (DA) aims to eliminate the difference between the distribution of labeled source domain on which a classifier is trained and that of unlabeled or partly labeled target domain to which the classifier is to be applied. Compared with the semi-supervised domain adaptation where some labeled data from target domain is utilized to help train the classifier, the unsupervised domain adaptation where no labels can be seen from the target domain is without doubt more challenging. Most published approaches suffer from high complexity of designment or implementation. In this paper, we propose a simple method for unsupervised domain adaptation which minimizes domain shift by projecting each instance from source and target domains into a common feature space using a linear kernel function. Our method is extremely simple without hyper-parameters (it can be implemented in two lines of Matlab code) but still outperforms the state-of-the-art domain adaptation approaches on standard benchmark datasets.

With the widespread use of surveillance cameras, massive video data analysis has become an extremely labor-intensive work. In this paper, we propose an efficient approach to detect video anomaly in crowded scenes based on Spatially Localized Histogram of Optical Flow (SL-HOF) descriptor and foreground classification. For motion description, the new SL-HOF descriptor can not only preserve classic HOF descriptor's favorable capability of characterizing the motion velocity and direction of foreground in crowded scene, but also depicts the spatial distribution of optical flow, which implicitly encodes the structure and local motion information of foreground objects in videos. SL-HOF is shown to significantly outperform other classic video descriptors. To further boost the performance of anomaly localization, we then introduce Robust PCA based foreground classification to discriminate anomalous foreground texture. Instead of computationally expensive approaches like l1-norm Sparse Coding, we adopt classic one-class SVM (OCSVM) to model normal video events and detect outliers (anomaly). Our experiments on the challenging UCSD datasets show our approach can achieve state-of-the-art results when compared to existing video anomaly detection methods.

In clustering applications, multiple views of the data are often available. Although clustering could be done within each view independently, exploiting information across views is promising to gain clustering accuracy improvement. A common assumption in the field of multi-view learning is that the clustering results from multiple views should be consistent with a latent clustering. However, the potential noise among some views would make this assumption difficult to be satisfied, which finally hurts the clustering performance. To address this issue, we propose a novel clustering algorithm where the intrinsic clustering is found by maximizing the sum of weighted similarities between clusterings of different views. Weights that indicate the qualities of views are learned simultaneously along with the latent clustering and clusterings of different views. A three-step alternative algorithm is designed to solve the problem efficiently. Empirical comparisons with a number of baselines on various datasets confirm the efficacy of our approach.

Smart video analysis is attracting increasing attention with the pervasive use of surveillance camera. In this paper, we address video anomaly detection by Uniform Local Gradient Pattern based Optical Flow (ULGP-OF) descriptor and one-class extreme learning machine (OCELM). Using the proposed ULGP-OF descriptor, we naturally combine the robust 2D image texture descriptor LGP with video optical flow to jointly descibe the texture and motion characteristics of video. ULGP-OF significantly outperforms other frequently-used classic video decriptors by a 6% to 10% EER reduction. As to normal video event modeling, the newly emergent ELM is introduced for the first time to tackle the unbearable training time incurred by massive training data from video streams. Compared to classic data description algorithms like one-class SVM (OCSVM) and sparse coding, OCELM can yield competitive results with a significant improvement in learning speed, which makes our approach more applicable to large-scale video analysis and easier for updating when video data are explosively generated in this day and age. Moreover, by adopting consistency-based criteria, only one parameter needs to be appointed for OCELM before training, which renders our approach much more parameter-free than other anomaly detection techniques like sparse coding. Experiments on UCSD ped1 and ped2 datasets demonstrate the effectiveness of our approach.

Data sharing among multiple sampling tasks significantly reduces energy consumption and communication cost in low-power wireless sensor networks (WSNs). Conventional proposals have already scheduled the discrete point sampling tasks to decrease the amount of sampled data. However, less effort has been expended for applications that generate continuous interval sampling tasks. Moreover, most pioneering work limits its view to schedule sampling intervals of tasks on a single sensor node and neglects the process of task allocation in WSNs. Therefore, the gained efforts in prior work cannot benefit a large-scale WSN because the performance of a scheduling method is sensitive to the strategy of task allocation. Broadening the scope to an entire network, this article is the first work to maximize data sharing among continuous interval sampling tasks by jointly optimizing task allocation and scheduling of sampling intervals in WSNs. First, we formalize the joint optimization problem and prove it NP-hard. Second, we present the COMBINE operation, which is the crucial ingredient of our solution. COMBINE is a 2-factor approximate algorithm for maximizing data sharing among overlapping tasks. Furthermore, our heuristic named CATS is proposed. CATS is 2-factor approximate algorithm for jointly allocating tasks and scheduling sampling intervals so as to maximize data sharing in the entire network. Extensive empirical study is conducted on a testbed of 50 sensor nodes to evaluate the effectiveness of our methods. In addition, the scalability of our methods is verified by utilizing TOSSIM, a widely used simulation tool. The experimental results indicate that our methods successfully reduce the volume of sampled data and decrease energy consumption significantly.

Multiple kernel learning (MKL) optimally combines the multiple channels of each sample to improve classification performance. However, existing MKL algorithms cannot effectively handle the situation where some channels are missing, which is common in practical applications. This paper proposes an absent MKL (AMKL) algorithm to address this issue. Different from existing approaches where missing channels are firstly imputed and then a standard MKL algorithm is deployed on the imputed data, our algorithm directly classifies each sample with its observed channels. In specific, we define a margin for each sample in its own relevant space, which corresponds to the observed channels of that sample. The proposed AMKL algorithm then maximizes the minimum of all sample-based margins, and this leads to a difficult optimization problem. We show that this problem can be reformulated as a convex one by applying the representer theorem. This makes it readily be solved via existing convex optimization packages. Extensive experiments are conducted on five MKL benchmark data sets to compare the proposed algorithm with existing imputation-based methods. As observed, our algorithm achieves superior performance and the improvement is more significant with the increasing missing ratio.

Existing multiple kernel learning (MKL) algorithms \textit{indiscriminately} apply a same set of kernel combination weights to all samples. However, the utility of base kernels could vary across samples and a base kernel useful for one sample could become noisy for another. In this case, rigidly applying a same set of kernel combination weights could adversely affect the learning performance. To improve this situation, we propose a sample-adaptive MKL algorithm, in which base kernels are allowed to be adaptively switched on/off with respect to each sample. We achieve this goal by assigning a latent binary variable to each base kernel when it is applied to a sample. The kernel combination weights and the latent variables are jointly optimized via margin maximization principle. As demonstrated on five benchmark data sets, the proposed algorithm consistently outperforms the comparable ones in the literature.

The Environmental/Economic Dispatch EED puzzle of power system is actually a classic constrained multi-objective optimization problem in evolutionary optimization category. However, most of its properties have not been researched by its aboriginal Pateto Front. In a meanwhile, the multi-objective evolutionary algorithm based on decomposition(MOEA/D) is a well-known new rising yet powerful method in multi-objective evolutionary optimization domain, but how to run it under constrained conditions has not been testified sufficiently because it is not easy to embed traditional skills to process constraints in such special frame as MOEA/D. Different from non-dominated sorting relationship as well as simply aggregation, this paper proposes a new multi-objective evolutionary approach motivated by decomposition idea and some equality constrained optimization approaches to handle EED problem. The standard IEEE 30 bus six-generator test system is adopted to test the performance of the new algorithm with several simple parameter setting. Experimental results have shown the new method surpasses or performs similarly to many state-of-the-art multi-objective evolutionary algorithms. The high-quality experimental results have validated the efficiency and applicability of the proposed approach. It has good reason to believe that the new algorithm has a promising space over the real-world multi-objective optimization problems.

In this paper, we propose an unsupervised feature selection framework which simultaneously preserves the local geometric structure and global discriminative structure of data. Also, the spectral clustering algorithm is incorporated into this framework to exploit the discriminative structure. To demonstrate the generality of our framework, we instantiate our framework into two specific algorithms by characterizing the local geometric structure of data with two well-known models, i.e., locally linear embedding and linear preserve projection. After that, we provide an efficient algorithm with proved convergence to solve the resultant optimization problem. Comprehensive experiments have been conducted on eleven benchmark data sets and the results demonstrate the superior performance of our framework.

In this paper, we propose a binary feature selection framework in kernel spaces, where each feature is projected into kernel spaces and a binary classification task is constructed in this space. Subsequently, the features are selected according to the normal vector of the learned classifier, which reflects the importance of each feature. To achieve the effect of feature selection, an £i-norm regularization is imposed on the normal vector to enforce its sparsity. Also, our framework can be naturally extended to the semi-supervised feature selection scenario via the well-known manifold regularization technique. Furthermore, the issue of eliminating the potential redundancy among the selected features is well discussed. Finally, we provide some theoretical results which guarantee the feasibility of the proposed framework. Comprehensive experiments have been conducted on six benchmark data sets and the results demonstrate the performance of our framework.

Optical flow estimation is a fundamental task of many computer vision applications. In this paper, we propose a fast simple algorithm to compute optical flow based on the 3-D gradient in video sequences. Although the algorithm does not provide highly accurate results, it is computationally simple and fast, and the output is applicable for many applications. The basic idea is that points will form trajectories in video sequences, and the trajectory between two frames of each point is approximated as a straight line, which is the tangent of the trajectory in our algorithm. Therefore, the optical flow of each point is the projecting line of the straight line, which represents its trajectory, in the image plane. Experimental results show that the proposed algorithm is efficient and effective, and is of satisfying accuracy on angle. It is able to provide effective optical flow results for real-time applications.

To achieve effective and efficient detection of Alzheimer's disease (AD), many machine learning methods have been introduced into this realm. However, the general case of limited training samples, as well as different feature representations typically makes this problem challenging. In this paper, we propose a novel multiple kernel-learning framework to combine multimodal features for AD classification, which is scalable and easy to implement. Contrary to the usual way of solving the problem in the dual, we look at the optimization from a new perspective. By conducting Fourier transform on the Gaussian kernel, we explicitly compute the mapping function, which leads to a more straightforward solution of the problem in the primal. Furthermore, we impose the mixed L21 norm constraint on the kernel weights, known as the group lasso regularization, to enforce group sparsity among different feature modalities. This actually acts as a role of feature modality selection, while at the same time exploiting complementary information among different kernels. Therefore, it is able to extract the most discriminative features for classification. Experiments on the ADNI dataset demonstrate the effectiveness of the proposed method.

The recent literature indicates that preserving global pairwise sample similarity is of great importance for feature selection and that many existing selection criteria essentially work in this way. In this paper, we argue that besides global pairwise sample similarity, the local geometric structure of data is also critical and that these two factors play different roles in different learning scenarios. In order to show this, we propose a global and local structure preservation framework for feature selection (GLSPFS) which integrates both global pairwise sample similarity and local geometric data structure to conduct feature selection. To demonstrate the generality of our framework, we employ methods that are well known in the literature to model the local geometric data structure and develop three specific GLSPFS-based feature selection algorithms. Also, we develop an efficient optimization algorithm with proven global convergence to solve the resulting feature selection problem. A comprehensive experimental study is then conducted in order to compare our feature selection algorithms with many state-of-the-art ones in supervised, unsupervised, and semisupervised learning scenarios. The result indicates that: 1) our framework consistently achieves statistically significant improvement in selection performance when compared with the currently used algorithms; 2) in supervised and semisupervised learning scenarios, preserving global pairwise similarity is more important than preserving local geometric data structure; 3) in the unsupervised scenario, preserving local geometric data structure becomes clearly more important; and 4) the best feature selection performance is always obtained when the two factors are appropriately integrated. In summary, this paper not only validates the advantages of the proposed GLSPFS framework but also gains more insight into the information to be preserved in different feature selection tasks.

Integrating radius information has been demonstrated by recent work on multiple kernel learning (MKL) as a promising way to improve kernel learning performance. Directly integrating the radius of the minimum enclosing ball (MEB) into MKL as it is, however, not only incurs significant computational overhead but also possibly adversely affects the kernel learning performance due to the notorious sensitivity of this radius to outliers. Inspired by the relationship between the radius of the MEB and the trace of total data scattering matrix, this paper proposes to incorporate the latter into MKL to improve the situation. In particular, in order to well justify the incorporation of radius information, we strictly comply with the radius-margin bound of support vector machines (SVMs) and thus focus on the l2-norm soft-margin SVM classifier. Detailed theoretical analysis is conducted to show how the proposed approach effectively preserves the merits of incorporating the radius of the MEB and how the resulting optimization is efficiently solved. Moreover, the proposed approach achieves the following advantages over its counterparts: 1) more robust in the presence of outliers or noisy training samples; 2) more computationally efficient by avoiding the quadratic optimization for computing the radius at each iteration; and 3) readily solvable by the existing off-the-shelf MKL packages. Comprehensive experiments are conducted on University of California, Irvine, protein subcellular localization, and Caltech-101 data sets, and the results well demonstrate the effectiveness and efficiency of our approach.

Learning an optimal kernel plays a pivotal role in kernel-based methods. Recently, an approach called optimal neighborhood kernel learning (ONKL) has been proposed, showing promising classification performance. It assumes that the optimal kernel will reside in the neighborhood of a "pre-specified" kernel. Nevertheless, how to specify such a kernel in a principled way remains unclear. To solve this issue, this paper treats the pre-specified kernel as an extra variable and jointly learns it with the optimal neighborhood kernel and the structure parameters of support vector machines. To avoid trivial solutions, we constrain the pre-specified kernel with a parameterized model. We first discuss the characteristics of our approach and in particular highlight its adaptivity. After that, two instantiations are demonstrated by modeling the pre-specified kernel as a common Gaussian radial basis function kernel and a linear combination of a set of base kernels in the way of multiple kernel learning (MKL), respectively. We show that the optimization in our approach is a min-max problem and can be efficiently solved by employing the extended level method and Nesterov's method. Also, we give the probabilistic interpretation for our approach and apply it to explain the existing kernel learning methods, providing another perspective for their commonness and differences. Comprehensive experimental results on 13 UCI data sets and another two real-world data sets show that via the joint learning process, our approach not only adaptively identifies the pre-specified kernel, but also achieves superior classification performance to the original ONKL and the related MKL algorithms.

Data security, which is concerned with the confidentiality, integrity and availability of data, is still challenging the application of wireless mesh networks (WMNs). In this paper, we focus on a special type of denial-of-service attack, called selective forwarding or grey hole attack. When this attack is launched at the gateways of a WMN where data tend to aggregate, it could lead to severe damages due to loss of sensitive data. Most existing proposals that focus on detecting stand-alone attackers via channel overhearing are ineffective against collusive attackers. In this paper, we propose a forwarding assessment based detection (FADE) scheme to mitigate collaborative grey hole attacks. Specifically, FADE detects sophisticated attacks by means of forwarding assessments aided by two-hop acknowledgement monitoring. Moreover, FADE can coexist with contemporary link security techniques. We analyze the optimal detection threshold that minimizes the sum of false positive rate and false negative rate of FADE, considering the network dynamics due to degraded channel quality or medium access collisions. Extensive simulation results are presented to demonstrate the adaptability of FADE to network dynamics and its effectiveness in detecting collaborative grey hole attacks.

The recently proposed TCP-targeted Low-rate Distributed Denial-of-Service (LDDoS) attacks send fewer packets to attack legitimate flows by exploiting the vulnerability in TCP’s congestion control mechanism. They are difficult to detect while causing severe damage to TCP-based applications. Existing approaches can only detect the presence of an LDDoS attack, but fail to identify LDDoS flows. In this paper, we propose a novel metric – Congestion Participation Rate (CPR) – and a CPR-based approach to detect and filter LDDoS attacks by their intention to congest the network. The major innovation of the CPR-base approach is its ability to identify LDDoS flows. A flow with a CPR higher than a predefined threshold is classified as an LDDoS flow, and consequently all of its packets will be dropped. We analyze the effectiveness of CPR theoretically by quantifying the average CPR difference between normal TCP flows and LDDoS flows and showing that CPR can differentiate them. We conduct ns-2 simulations, test-bed experiments, and Internet traffic trace analysis to validate our analytical results and evaluate the performance of the proposed approach. Experimental results demonstrate that the proposed CPR-based approach is substantially more effective compared to an existing Discrete Fourier Transform (DFT)-based approach – one of the most efficient approaches in detecting LDDoS attacks. We also provide experimental guidance to choose the CPR threshold in practice.

A robust fingerprint segmentation technique using adaptive threshold after Log-Gabor filtering and orientation reliability is proposed. The Log-Gabor filter turns the non-ridge areas of fingerprint image dark, but makes the ridge areas brighter than non-ridge areas. The gray features of filtered image are robust in spite of different gray features in original fingerprint images. An adaptive threshold according to the histogram is robust to exclude non-ridge areas. And Orientation Reliability is defined on the orientations of blocks to discriminate the disordered ridge like areas. Then fusion of the two segmentations and post-processing are introduced. Experiments show that the proposed composite segmentation technique is effective and robust to different contrast areas and disordered ridge areas in one image.

Most of existing dimensionality reduction methods obtain the low-dimensional embedding via preserving a certain property of the data, such as locality, neighborhood relationship. However, the intrinsic cluster structure of data, which plays a key role in analyzing and utilizing the data, has been ignored by the state-of-the-art dimensionality reduction methods. Hence, in this paper we propose a novel dimensionality reduction method called Cluster Preserving Embedding(CPE), in which the cluster structure of original data is preserved via preserving the robust path-based similarity between pairwise points. We present two different methods to preserve this similarity. One is the Multidimensional Scaling(MDS) way, which tries to preserve similarity matrix accurately, the other one is a Laplacian-style way, which preserves the topological partial order of the similarity rather than similarity itself. Encouraging experimental results on a toy data set and handwritten digits from MNIST database demonstrate the effectiveness of our Cluster Preserving Embedding method.

Distributed Denial of Service (DDoS) attack is one of main threats to Internet security. Due to the spatio-temporal properties of the attack, it is possible to detect the attack at its early stage. In this paper, we propose a novel method of DDoS threat assessment based on network vulnerability analysis. Both the multi-phase character in the temporal dimension and the impacts in the spatial dimension are concerned in our method. We use three metrics to assess threat, namely the ratio of progress, botnet size, and bots distribution. Experimental results show that our method is sensitive to the changes of attack states, and is easy to be implemented in an early warning system because of its simplicity.

Fingerprint is one of the biometrics used to identify a person. Alignment is an important step in fingerprint recognition, affecting greatly the speed and accuracy of matching. Eight types of Special ridges are introduced to align two fingerprints. The ridge with maximum of sampled curvature is used as reference ridges for initial alignment. And corresponding special ridges paired by topology get aligned by their features. The alignment parameters of translation and rotation finally come from all aligned special ridge pairs. Experiments show that alignment using special ridges is fast and robust.

A biometric identification procedure usually contains two stages: registration and authentication. Most biometric systems capture multiple samples of the same biometric trait (e.g., eight impressions of a person’s left index finger) at the stage of registration. As a result, it is essential to select several samples as templates. This paper proposes two algorithms maximum match scores (MMS) and greedy maximum match scores (GMMS) based on match scores for template selection. The proposed algorithms need not involve the specific details about the biometric data. Therefore, they are more flexible and can be used in various biometric systems. The two algorithms are compared with Random and sMDIST on the database of FVC2006DB1A, and the experimental results show that the proposed approaches can improve the accuracy of biometric system efficiently.

This paper describes the clustering problem first, and then utilizes the genetic algorithm to implement the optimization of clustering methods. Based on the optimized clustering on the sample data, we get various categories of the relation between traffics and attack amounts, and then builds up several prediction sub-models about DoS attack. Furthermore, according to the Bayesian method, we deduce discrete probability calculation about each sub-model and then get the distribution discrete probability prediction model for DoS attack.

Active learning is an important approach to reduce data-collection costs for inductive learning problems by sampling only the most informative instances for labeling. We focus here on the sampling criterion for how to select these most informative instances. Three contributions are made in this paper. First, in contrast to the leading sampling strategy of halving the volume of version space, we present the sampling strategy of reducing the volume of version space by more than half with the assumption of target function being chosen from nonuniform distribution over version space. Second, we propose the idea of sampling the instances that would be most possibly misclassified. Third, we develop a sampling method named CBMPMS (Committee Based Most Possible Misclassification Sampling) which samples the instances that have the largest probability to be misclassified by the current classifier. Comparing the proposed CBMPMS method with the existing active learning methods, when the classifiers achieve the same accuracy, the former method will sample fewer times than the latter ones. The experiments show that the proposed method outperforms the traditional sampling methods on most selected datasets.

For detecting malicious codes, a classification method of support vector machine (SVM) based on rough set theory (RST) is proposed. The original sample data is preprocessed with the knowledge reduction algorithm of RST, and the redundant features and conflicting samples are eliminated from the working sample dataset to reduce space dimension of sample data. Then the preprocessed sample data is used as training sample data of SVM. By utilizing SVM, the generalizing ability of detection system is still good even the sample dataset size is small. Experiment results show that the proposed detection system needs few priori knowledge and can improve the training speed and precision of classification.

Fingerprint minutiae are prevalently used in fingerprint recognition systems. The extraction of fingerprint minutiae is heavily affected by the quality of fingerprint images. This leads to the incorporation of a fingerprint enhancement module in fingerprint recognition systems to make the system robust with respect to the quality of input fingerprint images. Most of existing enhancement methods suffer from two main kinds of defects: (1) time consuming and thus unusable in time critical applications; and (2) blocky and directional effects in the enhanced image. This paper proposes an improved fingerprint enhancement scheme based on the Gabor filter tuning its frequency to the average frequency of the input image and changing its shape from square to circle and dynamically adjusting the filter's size based on the average frequency. This scheme can enhance the fingerprint image rapidly and overcome the blocky and directional effects and does improve the performance of minutiae detection.

Link bandwidth utilization is obviously critical for numerous network management tasks. Using the flow-conservation law, we could reduce the number of activated monitor agents. The problem of efficiently monitoring link-bandwidth based on flow-conservation law could be reduced to weak vertex cover problem, which is NP-hard. In this paper, we demonstrate an approximation preserving reduction from the vertex cover problem to weak vertex cover problem. Due to this reduction, it follows that it is very difficult to get an approximation algorithm with approximation ratio lower than 2 for weak vertex cover problem. Using the primal-dual method, we give an approximation algorithm with approximation ratio 2 to solve the problem. The effectiveness of our monitoring algorithm is validated by simulations evaluation over a wide range of network topologies. We also demonstrate the problem of weak vertex cover with blackout vertices could be reduce to weak vertex cover problem. Hence we could use the approximation algorithms for weak vertex cover problem to solve the problem of weak vertex cover with blackout vertices.