Source author record

Rustem Takhanov

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Catalog footprint

Research overview

7works
7topics
4close collaborators

Published work

7 publications

preprint2026arXiv

Deep Linear Discriminant Analysis Revisited

We show that for unconstrained Deep Linear Discriminant Analysis (LDA) classifiers, maximum-likelihood training admits pathological solutions in which class means drift together, covariances collapse, and the learned representation becomes almost non-discriminative. Conversely, cross-entropy training yields excellent accuracy but decouples the head from the underlying generative model, leading to highly inconsistent parameter estimates. To reconcile generative structure with discriminative performance, we introduce the \emph{Discriminative Negative Log-Likelihood} (DNLL) loss, which augments the LDA log-likelihood with a simple penalty on the mixture density. DNLL can be interpreted as standard LDA NLL plus a term that explicitly discourages regions where several classes are simultaneously likely. Deep LDA trained with DNLL produces clean, well-separated latent spaces, matches the test accuracy of softmax classifiers on synthetic data and standard image benchmarks, and yields substantially better calibrated predictive probabilities, restoring a coherent probabilistic interpretation to deep discriminant models.

preprint2015arXiv

Effectiveness of Structural Restrictions for Hybrid CSPs

Constraint Satisfaction Problem (CSP) is a fundamental algorithmic problem that appears in many areas of Computer Science. It can be equivalently stated as computing a homomorphism $\mbox{$\bR \rightarrow \bGamma$}$ between two relational structures, e.g.\ between two directed graphs. Analyzing its complexity has been a prominent research direction, especially for {\em fixed template CSPs} in which the right side $\bGamma$ is fixed and the left side $\bR$ is unconstrained. Far fewer results are known for the {\em hybrid} setting that restricts both sides simultaneously. It assumes that $\bR$ belongs to a certain class of relational structures (called a {\em structural restriction} in this paper). We study which structural restrictions are {\em effective}, i.e.\ there exists a fixed template $\bGamma$ (from a certain class of languages) for which the problem is tractable when $\bR$ is restricted, and NP-hard otherwise. We provide a characterization for structural restrictions that are {\em closed under inverse homomorphisms}. The criterion is based on the {\em chromatic number} of a relational structure defined in this paper; it generalizes the standard chromatic number of a graph. As our main tool, we use the algebraic machinery developed for fixed template CSPs. To apply it to our case, we introduce a new construction called a "lifted language." We also give a characterization for structural restrictions corresponding to minor-closed families of graphs, extend results to certain Valued CSPs (namely conservative valued languages), and state implications for CSPs with ordered variables, (valued) CSPs on structures with large girth, and for the maximum weight independent set problem on some restricted families of graphs including graphs with large girth.

preprint2014arXiv

Combining pattern-based CRFs and weighted context-free grammars

We consider two models for the sequence labeling (tagging) problem. The first one is a {\em Pattern-Based Conditional Random Field }(\PB), in which the energy of a string (chain labeling) x=x1…xn∈Dnx=x_1\ldots x_n\in D^n is a sum of terms over intervals [i,j][i,j] where each term is non-zero only if the substring xi…xjx_i\ldots x_j equals a prespecified word w∈Λw\in Λ. The second model is a {\em Weighted Context-Free Grammar }(\WCFG) frequently used for natural language processing. \PB and \WCFG encode local and non-local interactions respectively, and thus can be viewed as complementary. We propose a {\em Grammatical Pattern-Based CRF model }(\GPB) that combines the two in a natural way. We argue that it has certain advantages over existing approaches such as the {\em Hybrid model} of Bened{í} and Sanchez that combines {\em $\mbox{$N$-grams}$} and \WCFGs. The focus of this paper is to analyze the complexity of inference tasks in a \GPB such as computing MAP. We present a polynomial-time algorithm for general \GPBs and a faster version for a special case that we call {\em Interaction Grammars}.

preprint2012arXiv

Extensions of the Minimum Cost Homomorphism Problem

Assume DD is a finite set and RR is a finite set of functions from DD to the natural numbers. An instance of the minimum RR-cost homomorphism problem (MinHomRMinHom_R) is a set of variables VV subject to specified constraints together with a positive weight cvrc_{vr} for each combination of v∈Vv \in V and r∈Rr \in R. The aim is to find a function f:V→Df:V \rightarrow D such that ff satisfies all constraints and ∑v∈V∑r∈Rcvrr(f(v))\sum_{v \in V} \sum_{r \in R} c_{vr}r(f(v)) is minimized. This problem unifies well-known optimization problems such as the minimum cost homomorphism problem and the maximum solution problem, and this makes it a computationally interesting fragment of the valued CSP framework for optimization problems. We parameterize MinHomR(Γ)MinHom_R\left(Γ\right) by {\em constraint languages}, i.e. sets ΓΓ of relations that are allowed in constraints. A constraint language is called {\em conservative} if every unary relation is a member of it; such constraint languages play an important role in understanding the structure of constraint problems. The dichotomy conjecture for MinHomRMinHom_R is the following statement: if ΓΓ is a constraint language, then MinHomR(Γ)MinHom_R\left(Γ\right) is either polynomial-time solvable or NP-complete. For MinHomMinHom the dichotomy result has been recently obtained [Takhanov, STACS, 2010] and the goal of this paper is to expand this result to the case of MinHomRMinHom_R with conservative constraint language. For arbitrary RR this problem is still open, but assuming certain restrictions on RR we prove a dichotomy. As a consequence of this result we obtain a dichotomy for the conservative maximum solution problem.

preprint2010arXiv

A Dichotomy Theorem for General Minimum Cost Homomorphism Problem

In the constraint satisfaction problem (CSPCSP), the aim is to find an assignment of values to a set of variables subject to specified constraints. In the minimum cost homomorphism problem (MinHomMinHom), one is additionally given weights cvac_{va} for every variable vv and value aa, and the aim is to find an assignment ff to the variables that minimizes ∑vcvf(v)\sum_{v} c_{vf(v)}. Let MinHom(Γ)MinHom(Γ) denote the MinHomMinHom problem parameterized by the set of predicates allowed for constraints. MinHom(Γ)MinHom(Γ) is related to many well-studied combinatorial optimization problems, and concrete applications can be found in, for instance, defence logistics and machine learning. We show that MinHom(Γ)MinHom(Γ) can be studied by using algebraic methods similar to those used for CSPs. With the aid of algebraic techniques, we classify the computational complexity of MinHom(Γ)MinHom(Γ) for all choices of ΓΓ. Our result settles a general dichotomy conjecture previously resolved only for certain classes of directed graphs, [Gutin, Hell, Rafiey, Yeo, European J. of Combinatorics, 2008].

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.