Local noncuppability in R/M

Given any [c],[a],[d]∈R/M such that [d]≤[a]≤[c], [a] is locally noncuppable between [c] and [d] if [d]<[a]≤[c]and [a] ∨ [b] < [c] for any [b]∈R/M such that [d]≤ [ b ] < [ c ]. It will be shown that given any nonzero [ c ] ∈ R/M, there are [ a ], [ d ] ∈R/M such that [d]<[a]≤[c] and[a] is locally noncuppable between [c] and[d].     

The Difference between Polynomial-Time Many-One and Truth-Table Reducibilities on Distributional Problems

In this paper we separate many-one reducibility from truth-table reducibility for distributional problems in DistNP under the hypothesis that P ≠ NP . As a first example we consider the 3-Satisfiability problem (3SAT) with two different distributions on 3CNF formulas. We show that 3SAT with a version of the standard distribution is truth-table reducible but not many-one reducible to 3SAT with a less redundant distribution unless P = NP . We extend this separation result and define a distributional complexity class C with the following properties: (1) C is a subclass of DistNP, this relation is proper unless P = NP. (2) C contains DistP, but it is not contained in AveP unless DistNP \subseteq AveZPP. (3) C has a ≤ ^p _m -complete set. (4) C has a ≤ ^p _tt -complete set that is not ≤ ^p _m -complete unless P = NP. This shows that under the assumption that P ≠ NP, the two completeness notions differ on some nontrivial subclass of DistNP.     

Correlation between the gradients of the quadratic functional and its clipped prototype

Applicability of clipping of quadratic functional E = −0.5x ⁺ Tx + Bx in the minimization problem is considered (here x is the configurational vector and B ∈ R ^N is real valued vector). The probability that the gradient of this functional and the gradient of clipped functional ɛ = −0.5x ⁺ τx + bx are collinear is shown to be very high (the matrix τ is obtained by clipping of original matrix T: τ_ij = sgnT _ij ). It allows the conclusion that minimization of functional ɛ implies minimization of functional E. We can therefore replace the laborious process of minimizing functional E by the minimization of its clipped prototype ɛ. Use of the clipped functional allows sixteen-times reduction of the computation time and computer memory usage.     

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.     

Some consequences on the planar three-index transportation problem

In this study, some algebraic characterizations of the coefficient matrix A of the planar three-index transportation problem are derived and the equivalent formulation of this problem is obtained using the Kronecker product. It is shown that eigenvectors of the matrix G ⁺ G are characterized in terms of eigenvectors of the matrix A ⁺ A , where G ⁺ is the Moore–Penrose inverse of the coefficient matrix G of the equivalent problem.     

Generation of robust root loci for linear systems with parametric uncertainties in an ellipsoid

Given a parametric polynomial family p(s; Q) := {ⁿ _k=0 a_k (q)s^k : q ] Q}, Q R ^m , the robust root locus of p(s; Q) is defined as the two-dimensional zero set _p,Q := {s ] C:p(s; q) = 0 for some q ] Q}. In this paper we are concerned with the problem of generating robust root loci for the parametric polynomial family p(s; E) whose polynomial coefficients depend polynomially on elements of the parameter vector q ] E which lies in an m-dimensional ellipsoid E. More precisely, we present a computational technique for testing the zero inclusion/exclusion of the value set p(z; E) for a fixed point z in C, and then apply an integer-labelled pivoting procedure to generate the boundary of each subregion of the robust root locus _p,E . The proposed zero inclusion/exclusion test algorithm is based on using some simple sufficient conditions for the zero inclusion and exclusion of the value set p(z,E) and subdividing the domain E iteratively. Furthermore, an interval method is incorporated in the algorithm to speed up the process of zero inclusion/exclusion test by reducing the number of zero inclusion test operations. To illustrate the effectiveness of the proposed algorithm for the generation of robust root locus, an example is provided.     

PP-Lowness and a Simple Definition of AWPP

Abstract. We show that the counting classes AWPP and APP [FFKL], [L] are more robust than previously thought. Our results identify a sufficient condition for a language to be low for PP, and we show that this condition is at least as weak as other previously studied criteria. We extend a result of K?bler et al. by proving that all sparse co-C ₌ P languages are in APP, and are thus PP-low. Our results also imply that AWPP ⊂eq APP, and thus APP contains many other established subclasses of PP-low, thereby reducing several different lowness results to membership in APP. We also show that AWPP and APP are Σ ⁰ ₂ -definable classes. Some of our results are reminiscent of amplifying certainty in probabilistic computation.     

Strong separation of learning classes

Abstract

Suppose LC ₁ and LC ₂ are two machine learning classes each based on a criterion of success. Suppose, for every machine which learns a class of functions according to the LC ₂ criterion of success, there is a machine which learns this class according to the LC ₂ criterion. In the case where the converse does not hold LC, is said to be separated from LC ₂. It is shown that for many such separated learning classes from the literature a much stronger separation holds: (?𝒞∈LC ₁) (?𝒞' ∈LC ₂ - LC ₁(( [' ?𝒞] It is also shown that there is a pair of separated learning classes from the literature for which the stronger separation above does not hold. A philosophical heuristic toward the design of artificially intelligent learning programs is presented with each strong separation result.     

Extending the cooper minimal pair theorem

In the study of cappable and noncappable properties of the recursively enumerable(r.e.)degrees.Lempp suggested a conjecture which asserts that for all r.e.degrees and b,if a ≮b then there exists an r.e.degree c such that c≤a and c≮b and c is cappable.We shall prove in this paper that this conjecture holds under the condition that a is high.Working below a high r.e.degree h,we show that for any r.e.degree b with h≮b,there exist r.e.degrees a0 and a1 and such that a0,a1≮b,a0,a1≤h,and a0 and a1 from a minimal pair.     

Feature space versus empirical kernel map and row kernel space in SVMs

In machine-learning technologies, the support vector machine (SV machine, SVM) is a brilliant invention with many merits, such as freedom from local minima, the widest possible margins separating different clusters, and a solid theoretical foundation. In this paper, we first explore the linear separability relationships between the high-dimensional feature space H and the empirical kernel map U as well as between H and the space of kernel outputs K. Second, we investigate the relations of the distances between separating hyperplanes and SVs in H and U, and derive an upper bound for the margin width in K. Third, as an application, we show experimentally that the separating hyperplane in H can be slightly adjusted through U. The experiments reveal that existing SVM training can linearly separate the data in H with considerable success. The results in this paper allow us to visualize the geometry of H by studying U and K.     

Model Checking Abilities of Agents: A Closer Look

Alternating-time temporal logic (atl) is a logic for reasoning about open computational systems and multi-agent systems. It is well known that atl model checking is linear in the size of the model. We point out, however, that the size of an atl model is usually exponential in the number of agents. When the size of models is defined in terms of states and agents rather than transitions, it turns out that the problem is (1) Δ ₃ ^P -complete for concurrent game structures, and (2) Δ ₂ ^P -complete for alternating transition systems. Moreover, for “Positive atl” that allows for negation only on the level of propositions, model checking is (1) Σ ₂ ^P -complete for concurrent game structures, and (2) NP-complete for alternating transition systems. We show a nondeterministic polynomial reduction from checking arbitrary alternating transition systems to checking turn-based transition systems, We also discuss the determinism assumption in alternating transition systems, and show that it can be easily removed. In the second part of the paper, we study the model checking complexity for formulae of atl with imperfect information (atl _ir ). We show that the problem is Δ ₂ ^P -complete in the number of transitions and the length of the formula (thereby closing a gap in previous work of Schobbens in Electron. Notes Theor. Comput. Sci. 85(2), 2004). Then, we take a closer look and use the same fine structure complexity measure as we did for atl with perfect information. We get the surprising result that checking formulae of atl _ir is also Δ ₃ ^P -complete in the general case, and Σ ₂ ^P -complete for “Positive atl _ir ”. Thus, model checking agents’ abilities for both perfect and imperfect information systems belongs to the same complexity class when a finer-grained analysis is used.     

A generalized Schur-type algorithm for the joint factorization of a structured matrix and its inverse

A Schur-type algorithm is presented for the simultaneous triangular factorization of a given (non-degenerate) structured matrix and its inverse. The algorithm takes the displacement generator of a Hermitian, strongly regular matrixR as an input, and computes the displacement generator of the inverse matrixR ⁻¹ as an output. From these generators we can directly deduce theLD ⁻¹ L ^* (lower-diagonal-upper) decomposition ofR, and theUD ⁻¹ U ^* (upper-diagonallower) decomposition ofR ⁻¹. The computational complexity of the algorithm isO(rn ²) operations, wheren andr denote the size and the displacement rank ofR, respectively. Moreover, this method is especially suited for parallel (systolic array) implementations: usingn processors the algorithm can be carried out inO(n) steps.     

Competitive Analysis of On-Line Disk Scheduling

In this paper we study three popular on-line disk scheduling algorithms, FCFS, SSTF, and LOOK, using competitive analysis. Our results show that, in a competitive sense, the performance of LOOK is better than those of SSTF and FCFS. As a by-product, our analysis also reveals quantitatively the role played by the size of the window, which in our model is a waiting buffer that holds a fixed number of requests waiting to be serviced next. The window, in some sense, offers the lookahead ability which is mentioned in several on-line problems. Received February 1997, and in revised form November 1997, and in final form February 1998.     

Lie group continual meta learning algorithm

Humans can use acquired experience to learn new skills quickly and without forgetting the knowledge they already have. However, the neural network cannot do continual learning like humans, because it is easy to fall into the stability-plasticity dilemma and lead to catastrophic forgetting. Since meta-learning with the already acquired knowledge as a priori can directly optimize the final goal, this paper proposes LGCMLA (Lie Group Continual Meta Learning Algorithm) based on meta-learning, this algorithm is an improvement of CMLA (Continual Meta Learning Algorithm) proposed by Jiang et al. On the one hand, LGCMLA enhances the continuity between tasks by changing the inner-loop update rule (from using random initialization parameters for each task to using the updated parameters of the previous task for the subsequent task). On the other hand, it uses orthogonal groups to limit the parameter space and adopts the natural Riemannian gradient descent to accelerate the convergence speed. It not only corrects the shortcomings of poor convergence and stability of CMLA, but also further improves the generalization performance of the model and solves the stability-plasticity dilemma more effectively. Experiments on miniImageNet, tieredImageNet and Fewshot-CIFAR100 (Canadian Institute For Advanced Research) datasets prove the effectiveness of LGCMLA. Especially compared to MAML (Model-Agnostic Meta-Learning) with standard four-layer convolution, the accuracy of 1 shot and 5 shot is improved by 16.4% and 17.99% respectively under the setting of 5-way on miniImageNet.

     

An efficient method for computing leading eigenvalues and eigenvectors of large asymmetric matrices

An efficient method for computing a given number of leading eigenvalues (i.e., having largest real parts) and the corresponding eigenvectors of a large asymmetric matrixM is presented. The method consists of three main steps. The first is a filtering process in which the equationx = Mx is solved for an arbitrary initial conditionx(0) yielding:x(t)=e ^Mt x(0). The second step is the construction of (n+1) linearly independent vectorsv _m =M ^m x, 0mn orv _m =e ^mMt x ( being a short time interval). By construction, the vectorsv _m are combinations of only a small number of leading eigenvectors ofM. The third step consists of an analysis of the vectors {v _m } that yields the eigenvalues and eigenvectors. The proposed method has been successfully tested on several systems. Here we present results pertaining to the Orr-Sommerfeld equation. The method should be useful for many computations in which present methods are too slow or necessitate excessive memory. In particular, we believe it is well suited for hydrodynamic and mechanical stability investigations.     

正交约束多头自注意力的场景文本识别

目的 场景文本识别（scene text recognition，STR）是计算机视觉中的一个热门研究领域。最近，基于多头自注意力机制的视觉Transformer （vision Transformer，ViT）模型被提出用于STR，以实现精度、速度和计算负载的平衡。然而，没有机制可以保证不同的自注意力头确实捕捉到多样性的特征，这将导致使用多头自注意力机制的ViT模型在多样性极强的场景文本识别任务中表现不佳。针对这个问题，提出了一种新颖的正交约束来显式增强多个自注意力头之间的多样性，提高多头自注意力对不同子空间信息的捕获能力，在保证速度和计算效率的同时进一步提高网络的精度。方法 首先提出了针对不同自注意力头上Q （query）、K （key）和V （value）特征的正交约束，这可以使不同的自注意力头能够关注到不同的查询子空间、键子空间、值子空间的特征，关注不同子空间的特征可以显式地使不同的自注意力头捕捉到更具差异的特征。还提出了针对不同自注意力头上Q 、K 和V 特征线性变换权重的正交约束，这将为Q、K和V特征的学习提供正交权重空间的解决方案，并在网络训练中带来隐式正则化的效果。结果 实验在7个数据集上与基准方法进行比较，在规则数据集Street View Text （SVT）上精度提高了0.5%；在不规则数据集CUTE80 （CT）上精度提高了1.1%；在7个公共数据集上的整体精度提升了0.5%。结论 提出的即插即用的正交约束能够提高多头自注意力机制在STR任务中的特征捕获能力，使ViT模型在STR任务上的识别精度得到提高。本文代码已公开： https：//github.com/lexiaoyuan/XViTSTR。     

Statistical model development and estimation of suspended particulate matter concentrations with Landsat 8 OLI images of Dongting Lake,China

Suspended particulate matter (SPM) is a dominant water constituent of case-II waters, and SPM concentration (C_SPM) is a key parameter describing water quality. This study, using Landsat 8 Operational Land Imager (OLI) images, aimed to develop the C_SPM retrieval models and further to estimate the C_SPM values of Dongting Lake. One Landsat 8 OLI image and 53 C_SPM measurements were employed to calibrate Landsat 8-based C_SPM retrieval models. The C_SPM values derived from coincident Landsat 8 OLI and Moderate Resolution Imaging Spectroradiometer (MODIS) images were compared to validate calibrated Landsat 8-based C_SPM models. After the best stable Landsat 8-based C_SPM retrieval model was further validated using an independent Landsat 8 OLI image and its coincident C_SPM measurements, it was applied to four Landsat 8 OLI images to retrieve the C_SPM values in the South and East Dongting Lake. Model calibration results showed that two exponential models of the red band explained 61% (estimated standard error (SE) = 7.96 mg l^–1) and 67% (SE = 6.79 mg l^–1) of the variation of C_SPM; two exponential models of the red:panchromatic band ratio obtained 81% (SE = 5.48 mg l^–1) and 77% (SE = 4.96 mg l^–1) fitting accuracy; and four exponential and quadratic models of the infrared band explained 72–83% of the variation of C_SPM (SE = 5.18–5.52 mg l^–1). By comparing the MODIS- and Landsat 8-based C_SPM values, an exponential model of the Landsat 8 OLI red band (C_SPM = 1.1034 × exp(23.61 × R)) obtained the best consistent C_SPM estimations with the MODIS-based model (r = 0.98, p < 0.01), and its further validation result using an independent Landsat 8 OLI image showed a significantly strong correlation between the measured and estimated C_SPM values at a significance level of 0.05 (r = 0.91, p < 0.05). The C_SPM spatiotemporal distribution derived from four Landsat 8 images revealed a clear spatial distribution pattern of C_SPM in the South and East Dongting Lake, which was caused by natural and anthropogenic factors together. This study confirmed the potential of Landsat 8 OLI images in retrieving C_SPM and provided a foundation for retrieving the spatial distribution of C_SPM accurately from this new data source in Dongting Lake.     

Detection of Redundant Code Using R 2 D 2

We present the R ² D ² redundancy detector. R ² D ² identifies redundant code fragments in large software systems written in Lisp. For each pair of code fragments, R ² D ² uses a combination of techniques ranging from syntax-based analysis to semantics-based analysis, that detects positive and negative evidences regarding the redundancy of the analyzed code fragments. These evidences are combined according to a well-defined model and sufficiently redundant fragments are reported to the user. R ² D ² explores several techniques and heuristics to operate within reasonable time and space bounds and is designed to be extensible.     

More on the controllability of linear time-invariant systems

This study shows that a controllable system [xdot] = Ax + Bu, where x is an n-vector, can be driven from an arbitrary initial condition x(0) = x₀ to an arbitrary final condition x(t_f = x_f by a polynomial control function of degree M = 2r + 1, where r = n ? rank (B), through a polynomial trajectory of degree M. A simple algorithm for finding u by solving a set of linear equations, the solution of which yields the polynomial coefficients, is given.