Efficient automatic exact motif discovery algorithms for biological sequences

ObjectiveThis paper presents an algorithm for the solution of the motif discovery problem (MDP).Methods and materialsMotif discovery problem can be considered in two cases: motifs with insertions/deletions, and motifs without insertions/deletions. The first group motifs can be found by stochastic and approximated methods. The second group can be found by using stochastic and approximated methods, but also deterministic method. We proved that the second group motifs can be found with a deterministic algorithm, and so, it can be said that the second motifs finding is a P-type problem as proved in this paper.Results and conclusionsAn algorithm was proposed in this paper for motif discovery problem. The proposed algorithm finds all motifs which are occurred in the sequence at least two times, and it also finds motifs of various sizes. Due to this case, this algorithm is regarded as Automatic Exact Motif Discovery Algorithm. All motifs of different sizes can be found with this algorithm, and this case was proven in this paper. It shown that automatic exact motif discovery is a P-type problem in this paper. The application of the proposed algorithm has been shown that this algorithm is superior to MEME, MEME3, Motif Sampler, WEEDER, CONSENSUS, AlignACE.     

Matricial gradient for the least-squares residual and its application to optimal model fitting

To improve the model vector functions g_i ,-(t) or the model matrix M for L ₂ optimization and approximation of empirical data, the matricial gradient of the ordinary least-squares residual and the weighted least-squares residual is used. Acceleration and optimization of convergence is investigated. The optimal model fitting is also studied in the case of inequality constraint models and in the case of additional collocation point restrictions.     

基于元学习思想的算法选择问题综述

算法选择实际上可视为一种学习任务.鉴于此,首先分析基于元学习思想的算法选择框架;然后从数据集特征和元算法两个角度对基于元学习思想的算法选择方法进行归纳总结;最后分析基于元学习思想的算法选择存在的问题,并指出未来发展方向.     

元迁移学习在少样本跨域图像分类中的研究

目的 现有基于元学习的主流少样本学习方法假设训练任务和测试任务服从相同或相似的分布,然而在分布差异较大的跨域任务上,这些方法面临泛化能力弱、分类精度差等挑战。同时,基于迁移学习的少样本学习方法没有考虑到训练和测试阶段样本类别不一致的情况,在训练阶段未能留下足够的特征嵌入空间。为了提升模型在有限标注样本困境下的跨域图像分类能力,提出简洁的元迁移学习（compressed meta transfer learning,CMTL）方法。方法 基于元学习,对目标域中的支持集使用数据增强策略,构建新的辅助任务微调元训练参数,促使分类模型更加适用于域差异较大的目标任务。基于迁移学习,使用自压缩损失函数训练分类模型,以压缩源域中基类数据所占据的特征嵌入空间,微调阶段引导与源域分布差异较大的新类数据有更合适的特征表示。最后,将以上两种策略的分类预测融合视为最终的分类结果。结果 使用mini-ImageNet作为源域数据集进行训练,分别在EuroSAT(EuropeanSatellite)、ISIC(InternationalSkinImagingCollaboration)、CropDiseas(Cr...     

Learning bidirectional asymmetric similarity for collaborative filtering via matrix factorization

Memory-based collaborative filtering (CF) aims at predicting the rating of a certain item for a particular user based on the previous ratings from similar users and/or similar items. Previous studies in finding similar users and items have several drawbacks. First, they are based on user-defined similarity measurements, such as Pearson Correlation Coefficient (PCC) or Vector Space Similarity (VSS), which are, for the most part, not adaptive and optimized for specific applications and data. Second, these similarity measures are restricted to symmetric ones such that the similarity between A and B is the same as that for B and A, although symmetry may not always hold in many real world applications. Third, they typically treat the similarity functions between users and functions between items separately. However, in reality, the similarities between users and between items are inter-related. In this paper, we propose a novel unified model for users and items, known as Similarity Learning based Collaborative Filtering (SLCF) , based on a novel adaptive bidirectional asymmetric similarity measurement. Our proposed model automatically learns asymmetric similarities between users and items at the same time through matrix factorization. Theoretical analysis shows that our model is a novel generalization of singular value decomposition (SVD). We show that, once the similarity relation is learned, it can be used flexibly in many ways for rating prediction. To take full advantage of the model, we propose several strategies to make the best use of the proposed similarity function for rating prediction. The similarity can be used either to improve the memory-based approaches or directly in a model based CF approaches. In addition, we also propose an online version of the rating prediction method to incorporate new users and new items. We evaluate SLCF using three benchmark datasets, including MovieLens, EachMovie and Netflix, through which we show that our methods can outperform many state-of-the-art baselines.     

Regular matrix transformations and rates of convergence of positive linear operators

Abstract This paper investigates the effects of matrix summability methods on the A-statistical approximation of sequences of positive linear operators defined on the space of all 2π-periodic and continuous functions on the whole real axis. The two main tools used in this paper are A-statistical convergence and the modulus of continuity. Keywords: Regular infinite matrices, A-statistical convergence, rates of A-statistical convergence, positive linear operators, the Korovkin theorem, modulus of continuity. Mathematics Subject Classification (2000): 41A25, 41A36     

The problem of freedom on certain subsemigroups of the submonoid of left singular languages

In this paper, we discuss the properties of ? _L ′?=?{L′?∈?M|LL′?∈?S _l }, where M is the monoid of languages and S _l is the set of left singular languages in M. The following result is proved: when|A|?≥?2, for any L?∈?M, ? _L ′ is not free.     

Definite clause programs are canonical (over a suitable domain)

For each first-order languageL with a nonempty Herbrand universe, we construct an algebraC interpreting the function symbols ofL that is a model of the Clark equality theory with languageL and is canonical in the sense that for every definite clause programP in the languageL,T _P ^C is the greatest fixed point ofT _P ^C . The universe of individuals inC is a quotient of the set of terms ofL and is, a fortiori, countable ifL is countable. If contains at least one function symbol of arity at least 2, then the graphs of partial recursive functions onC, suitably defined, are representable in a natural way as individuals inC.Research sponsored in part by U.S. Air Force Contract F30602-85-C-0008.     

Performance analysis of probabilistic action systems

Formal notations like B or action systems support a notion of refinement. Refinement relates an abstract specification A to a concrete specification C that is as least as deterministic. Knowing A and C one proves that C refines, or implements, specification A. In this study we consider specification A as given and concern ourselves with a way to find a good candidate for implementation C. To this end we classify all implementations of an abstract specification according to their performance. We distinguish performance from correctness. Concrete systems that do not meet the abstract specification correctly are excluded. Only the remaining correct implementations C are considered with respect to their performance. A good implementation of a specification is identified by having some optimal behaviour in common with it. In other words, a good refinement corresponds to a reduction of non-optimal behaviour. This also means that the abstract specification sets a boundary for the performance of any implementation. We introduce the probabilistic action system formalism which combines refinement with performance. In our current study we measure performance in terms of long-run expected average-cost. Performance is expressed by means of probability and expected costs. Probability is needed to express uncertainty present in physical environments. Expected costs express physical or abstract quantities that describe a system. They encode the performance objective. The behaviour of probabilistic action systems is described by traces of expected costs. A corresponding notion of refinement and simulation-based proof rules are introduced. Probabilistic action systems are based on discrete-time Markov decision processes. Numerical methods solving the optimisation problems posed by Markov decision processes are well-known, and used in a software tool that we have developed. The tool computes an optimal behaviour of a specification A thus assisting in the search for a good implementation C.Received September 2002 Accepted in revised form January 2004 by E.C.R. Hehner     

结合记忆与迁移学习的小样本学习

小样本学习是视觉识别中的一个受关注的领域,旨在通过少量的数据来学习新的视觉概念。为了解决小样本问题,一些元学习方法提出从大量辅助任务中学习可迁移的知识并将其应用于目标任务上。为了更好地对知识进行迁移,提出了一种基于记忆的迁移学习方法。提出一种权重分解策略,将部分权重分解为冻结权重与可学习权重,在迁移学习中通过固定冻结权重,仅更新可学习权重的方式来减少模型需要学习的参数。通过一个额外的记忆模块来存储之前任务的经验,在学习新任务时,这些经验被用来初始化模型的参数状态,以此更好地进行迁移学习。通过在miniImageNet、tieredImageNet以及CUB数据集上的实验结果表明,相对于其他先进的方法,该方法在小样本分类任务上取得了具有竞争力甚至是更好的表现。     

Effects of dialogue design on automatic teller machine (ATM) usability: Transaction times and card loss

Unobtrusive observation of automatic teller machine (ATM) use was carried out to compare the efficiency and error profiles of two ATM interfaces in current use. Transaction times for the same transaction differed by 39%. Frequency of forgetting cards in the ATM differed by 96-100%. The differences were attributed to the sequencing of sub tasks with respect to the goal state. The cost of a lack of ergonomics in the less efficient interface was estimated conservatively to be US$1.7 million due to task sequencing, and between US$2 million and US$4.5 million from forgetting cards in the ATM.     

Local Approximability of Max-Min and Min-Max Linear Programs

In a max-min LP, the objective is to maximise ω subject to A x≤1, C x≥ω 1, and x≥0. In a min-max LP, the objective is to minimise ρ subject to A x≤ρ 1, C x≥1, and x≥0. The matrices A and C are nonnegative and sparse: each row a _i of A has at most Δ _I positive elements, and each row c _k of C has at most Δ _K positive elements.     

Measures on MV-algebras

 We study sequentially continuous measures on semisimple M V-algebras. Let A be a semisimple M V-algebra and let I be the interval [0,1] carrying the usual Łukasiewicz M V-algebra structure and the natural sequential convergence. Each separating set H of M V-algebra homomorphisms of A into I induces on A an initial sequential convergence. Semisimple M V-algebras carrying an initial sequential convergence induced by a separating set of M V-algebra homomorphisms into I are called I-sequential and, together with sequentially continuous M V-algebra homomorphisms, they form a category SM(I). We describe its epireflective subcategory ASM(I) consisting of absolutely sequentially closed objects and we prove that the epireflection sends A into its distinguished σ-completion σ _H (A). The epireflection is the maximal object in SM(I) which contains A as a dense subobject and over which all sequentially continuous measures can be continuously extended. We discuss some properties of σ _H (A) depending on the choice of H. We show that the coproducts in the category of D-posets [9] of suitable families of I-sequential M V-algebras yield a natural model of probability spaces having a quantum nature. The motivation comes from probability: H plays the role of elementary events, the embedding of A into σ _H (A) generalizes the embedding of a field of events A into the generated σ-field σ(A), and it can be viewed as a fuzzyfication of the corresponding results for Boolean algebras in [8, 11, 14]. Sequentially continuous homomorphisms are dual to generalized measurable maps between the underlying sets of suitable bold algebras [13] and, unlike in the Loomis–Sikorski Theorem, objects in ASM(I) correspond to the generated tribes (no quotient is needed, no information about the elementary events is lost). Finally, D-poset coproducts lift fuzzy events, random functions and probability measures to events, random functions and probability measures of a quantum nature. Supported by VEGA Grant 2/7193/01     

Integral-type generalizations of operators obtained from certain multivariate polynomials

Abstract In this work, we mainly focus on the Kantorovich-type (integral-type) generalizations of the positive linear operators obtained from the Chan-Chyan-Srivastava multivariable polynomials. Using the notion of A-statistical convergence, we obtain various approximation theorems including a statistical Korovkin-type result and rates of A-statistical convergence with the help of the modulus of continuity, Lipschitz class functionals and Peetre’s K-functionals. We also introduce an sth order generalization of our approximating operators. Keywords. Chan-Chyan-Srivastava multivariable polynomials, Korovkin approximation theorem, Kantorovich-type operators, A-statistical convergence, modulus of continuity, Lipschitz class functional, Peetre’s K-functional Mathematics Subject Classification (2000): Primary: 41A25; 41A36, Secondary: 33C45     

Calculating the Galois Group of Y′ = = = AY + + + B,Y′ = = = AY Completely Reducible

We consider a special case of the problem of computing the Galois group of a system of linear ordinary differential equations Y′ = MY, M C (x)^{n × n}. We assume that C is a computable, characteristic-zero, algebraically closed constant field with a factorization algorithm. There exists a decision procedure, due to Compoint and Singer, to compute the group in case the system is completely reducible. Berman and Singer (1999, J. Pure Appl. Algebr., 139, 3–23) address the case in which M = [yjsco5390x.gif M 1 * 0 M 2 ], Y′ = M_iY completely reducible for i = 1, 2. Their article shows how to reduce that case to the case of an inhomogeneous system Y′ = AY + B, A C (x)^{n × n}, B C (x)ⁿ, Y′ = AY completely reducible. Their article further presents a decision procedure to reduce this inhomogeneous case to the case of the associated homogeneous system Y′ = AY. The latter reduction involves using a cyclic-vector algorithm to find an equivalent inhomogeneous scalar equation L(y) = b,L C(x)[ D ], b C (x), then computing a certain set of factorizations of L in C(x)[D ]; this set is very large and difficult to compute in general. In this article, we give a new and more efficient algorithm to reduce the case of a system Y′ = AY + B,Y′ = AY completely reducible, to that of the associated homogeneous systemY′ = AY. The new method’s improved efficiency comes from replacing the large set of factorizations required by the Berman–Singer method with a single block-diagonal decomposition of the coefficient matrix satisfying certain properties.     

代表特征网络的小样本学习方法

目的 小样本学习任务旨在仅提供少量有标签样本的情况下完成对测试样本的正确分类。基于度量学习的小样本学习方法通过将样本映射到嵌入空间,计算距离得到相似性度量以预测类别,但未能从类内多个支持向量中归纳出具有代表性的特征以表征类概念,限制了分类准确率的进一步提高。针对该问题,本文提出代表特征网络,分类效果提升显著。方法 代表特征网络通过类代表特征的度量学习策略,利用类中支持向量集学习得到的代表特征有效地表达类概念,实现对测试样本的正确分类。具体地说,代表特征网络包含两个模块,首先通过嵌入模块提取抽象层次高的嵌入向量,然后堆叠嵌入向量经过代表特征模块得到各个类代表特征。随后通过计算测试样本嵌入向量与各类代表特征的距离以预测类别,最后使用提出的混合损失函数计算损失以拉大嵌入空间中相互类别间距减少相似类别错分情况。结果 经过广泛实验,在Omniglot、miniImageNet和Cifar100数据集上都验证了本文模型不仅可以获得目前已知最好的分类准确率,而且能够保持较高的训练效率。结论 代表特征网络可以从类中多个支持向量有效地归纳出代表特征用于对测试样本的分类,对比直接使用支持向量进行分类具有更好的鲁棒性,进一步提高了小样本条件下的分类准确率。     

On Nonnegative matrices generating a finite multiplicative monoid

Square nonnegative matrices with the property that the multiplicative monoid M(A) generated by the matrix A is finite are characterized in several ways. At first, the least general upper bound for the cardinality of M(A) is derived. Then it is shown that any square nonnegative matrix is cogredient to a lower triangular block form with the diagonal consisting of three blocks L, A ₀, and M where L and M are strictly lower triangular, A ₀ has no zero rows or columns, and M(A) is finite if and only if. M(A ₀) is so. Several criteria for, M(A ₀) to be finite are presented. One of the normal forms of A applies very well to the characterization of the nonnegative solutions of each of the matrix equations X ^k = 0, X ^k = 1, X ^k = X, and X ^k = X ^T where k > 1 is an integer. It also leads to a polynomial time algorithm for deciding whether or not M(A) is finite, if the entries of A are nonnegative rationals.     

A theorem on atomicity in distributed algorithms

Reasoning about a distributed algorithm is simplified if we can ignore the time needed to send and deliver messages and can instead pretend that a process sends a collection of messages as a single atomic action, with the messages delivered instantaneously as part of the action. A theorem is derived that proves the validity of such reasoning for a large class of algorithms. It generalizes and corrects a well-known folk theorem about when an operation in a multiprocess program can be considered atomic.List of notations A The set of program actions - A The algorithm under consideration - A The reduced version of algorithmA - A The action obtained by executing the operationA as an atomic action - C The set of state components - d[i] A variable of the Distance-Finding Algorithm - L An operation ofA, as in C2 - The operation obtained by adding toL the actions that deliver messages sent byL - N _p(S) The set of possible next actions of processp from states - P The correctness property - R An operation ofA, as in C2 - S The set of states - S ₀ The set of initial states - S _c The range of values of state componentc - X An action ofA, as in C2 - Usually denotes an execution ofA - The execution ofA that corresponds to an execution ofA When snow conditions are poor,Dr. L. Lamport works at Digital Equipment Corporation's Systems Research Center. As an undergraduate, he took a course in atomic physics.     

Prudence in vacillatory language identification

This paper settles a question about prudent vacillatory identification of languages. Consider a scenario in which an algorithmic deviceM is presented with all and only the elements of a languageL, andM conjectures a sequence, possibly infinite, of grammars. Three different criteria for success ofM onL have been extensively investigated in formal language learning theory. IfM converges to a single correct grammar forL, then the criterion of success is Gold's seminal notion ofTxtEx-identification. IfM converges to a finite number of correct grammars forL, then the criterion of success is calledTxtFex-identification. Further, ifM, after a finite number of incorrect guesses, outputs only correct grammars forL (possibly infinitely many distinct grammars), then the criterion of success is known asTxtBc-identification. A learning machine is said to beprudent according to a particular criterion of success just in case the only grammars it ever conjectures are for languages that it can learn according to that criterion. This notion was introduced by Osherson, Stob, and Weinstein with a view to investigating certain proposals for characterizing natural languages in linguistic theory. Fulk showed that prudence does not restrictTxtEx-identification, and later Kurtz and Royer showed that prudence does not restrictTxtBc-identification. This paper shows that prudence does not restrictTxtFex-identification.     

UNIQUENESS CONDITIONS OF CL-STRUCTURES IN GL-STRUCTURE EQUIVALENCE CLASSES OF SYSTEM RECONSTRUCTABILITY ANALYSIS

This paper first introduces the basic notions of overall systems with logical relations, their subsystems, structure representation graphs, sets of H-structures and G-structures with logical relations S _H ^L and S _G ^L, immediate refinement and aggregate with logical relations, structure-graph mappings r_V ^L, r_G ^L, etc., and the notions of inclusiveness with logical relations, upper bounding and lower bounding with logical relations. Then it proves the sufficient conditions under which representation graphs R ^L form a lattice. By defining the least upper bound and largest lower bound of (R^L, ) and recommending a lemma on distributivity, this paper proves the sufficient conditions under which G-structures with logical relations form Boolean lattices. Finally after defining the M-structures and C-structures with logical relations, i.e. M-structures and C-structures, this paper proposes the sufficient conditions for the uniqueness of C-structures in G-structure equivalence classes, and proves that the C ^L-structure is the least refined GL-structure in equivalence class S _G ^L/r _G ^L.