OpenRaiser/Intern-Atlas huggingface dataset:
Deep Learning for Instance Retrieval: A Survey
Venue: arXiv cs.CV 2022
Year: 2022

In recent years a vast amount of visual content has been generated and shared from many fields, such as social media platforms, medical imaging, and robotics. This abundance of content creation and sharing has introduced new challenges, particularly that of searching databases for similar content-Content Based Image Retrieval (CBIR)-a long-established research area in which improved efficiency and accuracy are needed for real-time retrieval. Artificial intelligence has made progress in CBIR and has significantly facilitated the process of instance search. In this survey we review recent instance retrieval works that are developed based on deep learning algorithms and techniques, with the survey organized by deep network architecture types, deep features, feature embedding and aggregation methods, and network fine-tuning strategies. Our survey considers a wide variety of recent methods, whereby we identify milestone work, reveal connections among various methods and present the commonly used benchmarks, evaluation results, common challenges, and propose promising future directions.
Variational Nested Dropout
Venue: arXiv cs.LG 2022
Year: 2022

Nested dropout is a variant of dropout operation that is able to order network parameters or features based on the pre-defined importance during training. It has been explored for: I. Constructing nested nets: the nested nets are neural networks whose architectures can be adjusted instantly during testing time, e.g., based on computational constraints. The nested dropout implicitly ranks the network parameters, generating a set of sub-networks such that any smaller sub-network forms the basis of a larger one. II. Learning ordered representation: the nested dropout applied to the latent representation of a generative model (e.g., auto-encoder) ranks the features, enforcing explicit order of the dense representation over dimensions. However, the dropout rate is fixed as a hyper-parameter during the whole training process. For nested nets, when network parameters are removed, the performance decays in a human-specified trajectory rather than in a trajectory learned from data. For generative models, the importance of features is specified as a constant vector, restraining the flexibility of representation learning. To address the problem, we focus on the probabilistic counterpart of the nested dropout. We propose a variational nested dropout (VND) operation that draws samples of multi-dimensional ordered masks at a low cost, providing useful gradients to the parameters of nested dropout. Based on this approach, we design a Bayesian nested neural network that learns the order knowledge of the parameter distributions. We further exploit the VND under different generative models for learning ordered latent distributions. In experiments, we show that the proposed approach outperforms the nested network in terms of accuracy, calibration, and out-of-domain detection in classification tasks. It also outperforms the related generative models on data generation tasks.
Tropical Support Vector Machines: Evaluations and Extension to Function Spaces
Venue: arXiv cs.LG 2022
Year: 2022

Support Vector Machines (SVMs) are one of the most popular supervised learning models to classify using a hyperplane in an Euclidean space. Similar to SVMs, tropical SVMs classify data points using a tropical hyperplane under the tropical metric with the max-plus algebra. In this paper, first we show generalization error bounds of tropical SVMs over the tropical projective torus. While the generalization error bounds attained via Vapnik-Chervonenkis (VC) dimensions in a distribution-free manner still depend on the dimension, we also show numerically and theoretically by extreme value statistics that the tropical SVMs for classifying data points from two Gaussian distributions as well as empirical data sets of different neuron types are fairly robust against the curse of dimensionality. Extreme value statistics also underlie the anomalous scaling behaviors of the tropical distance between random vectors with additional noise dimensions. Finally, we define tropical SVMs over a function space with the tropical metric.
The Work of Art in an Age of Mechanical Generation
Venue: arXiv cs.CY 2022
Year: 2022

Can we define what it means to be "creative," and if so, can our definition drive artificial intelligence (AI) systems to feats of creativity indistinguishable from human efforts? This mixed question is considered from technological and social perspectives. Beginning with an exploration of the value we attach to authenticity in works of art, the article considers the ability of AI to detect forgeries of renowned paintings and, in so doing, somehow reveal the quiddity of a work of art. We conclude by considering whether evolving technical capability can revise traditional relationships among art, artist, and the market.
An Automated Theorem Proving Framework for Information-Theoretic Results
Venue: arXiv cs.IT 2022
Year: 2022

We present a versatile automated theorem proving framework capable of automated discovery, simplification and proofs of inner and outer bounds in network information theory, deduction of properties of information-theoretic quantities (e.g. Wyner and Gács-Körner common information), and discovery of non-Shannon-type inequalities, under a unified framework. Our implementation successfully generated proofs for 32 out of 56 theorems in Chapters 1-14 of the book Network Information Theory by El Gamal and Kim. Our framework is based on the concept of existential information inequalities, which provides an axiomatic framework for a wide range of problems in information theory.
Adversarial Learning with Cost-Sensitive Classes
Venue: arXiv cs.LG 2022
Year: 2022

It is necessary to improve the performance of some special classes or to particularly protect them from attacks in adversarial learning. This paper proposes a framework combining cost-sensitive classification and adversarial learning together to train a model that can distinguish between protected and unprotected classes, such that the protected classes are less vulnerable to adversarial examples. We find in this framework an interesting phenomenon during the training of deep neural networks, called Min-Max property, that is, the absolute values of most parameters in the convolutional layer approach zero while the absolute values of a few parameters are significantly larger becoming bigger. Based on this Min-Max property which is formulated and analyzed in a view of random distribution, we further build a new defense model against adversarial examples for adversarial robustness improvement. An advantage of the built model is that it performs better than the standard one and can combine with adversarial training to achieve an improved performance. It is experimentally confirmed that, regarding the average accuracy of all classes, our model is almost as same as the existing models when an attack does not occur and is better than the existing models when an attack occurs. Specifically, regarding the accuracy of protected classes, the proposed model is much better than the existing models when an attack occurs.
Subgraph nomination: Query by Example Subgraph Retrieval in Networks
Venue: arXiv cs.LG 2022
Year: 2022

This paper introduces the subgraph nomination inference task, in which example subgraphs of interest are used to query a network for similarly interesting subgraphs. This type of problem appears time and again in real world problems connected to, for example, user recommendation systems and structural retrieval tasks in social and biological/connectomic networks. We formally define the subgraph nomination framework with an emphasis on the notion of a user-in-the-loop in the subgraph nomination pipeline. In this setting, a user can provide additional post-nomination light supervision that can be incorporated into the retrieval task. After introducing and formalizing the retrieval task, we examine the nuanced effect that user-supervision can have on performance, both analytically and across real and simulated data examples.
On the differential privacy of dynamic location obfuscation with personalized error bounds
Venue: arXiv cs.CR 2022
Year: 2022

Geo-indistinguishability and expected inference error are two complementary notions for location privacy. The joint guarantee of differential privacy (indistinguishability) and distortion privacy (inference error) limits the information leakage. In this paper, we analyze the differential privacy of PIVE, a dynamic location obfuscation mechanism proposed by Yu, Liu and Pu (NDSS 2017), and show that PIVE fails to offer either of the privacy guarantees on adaptive Protection Location Sets (PLSs) as claimed. Specifically, we demonstrate that different PLSs could intersect with one another due to the defined search algorithm, and then different apriori locations in the same PLS could have different protection diameters. As a result, we can show that the proof of local differential privacy for PIVE is problematic. Besides, the condition introduced in PIVE is confirmed to be not sufficient for bounding expected inference errors in general, which makes the user-defined inference error threshold invalid. To address these issues, we propose a couple of correction approaches, analyze theoretically their satisfied privacy characteristics and detail their respective merits and demerits.
Fairness through Social Welfare Optimization
Venue: arXiv cs.AI 2022
Year: 2022

We propose social welfare optimization as a general paradigm for formalizing fairness in AI systems. We argue that optimization models allow formulation of a wide range of fairness criteria as social welfare functions, while enabling AI to take advantage of highly advanced solution technology. Rather than attempting to reduce bias between selected groups, one can achieve equity across all groups by incorporating fairness into the social welfare function. This also allows a fuller accounting of the welfare of the individuals involved. We show how to integrate social welfare optimization with both rule-based AI and machine learning, using either an in-processing or a post-processing approach. We present empirical results from a case study as a preliminary examination of the validity and potential of these integration strategies.
Quantum game theory and the complexity of approximating quantum Nash equilibria
Venue: arXiv cs.CC 2022
Year: 2022

This paper is concerned with complexity theoretic aspects of a general formulation of quantum game theory that models strategic interactions among rational agents that process and exchange quantum information. In particular, we prove that the computational problem of finding an approximate Nash equilibrium in a broad class of quantum games is, like the analogous problem for classical games, included in (and therefore complete for) the complexity class PPAD. Our main technical contribution, which facilitates this inclusion, is an extension of prior methods in computational game theory to strategy spaces that are characterized by semidefinite programs.
Secrecy: Secure collaborative analytics on secret-shared data
Venue: arXiv cs.DB 2022
Year: 2022

We present a relational MPC framework for secure collaborative analytics on private data with no information leakage. Our work targets challenging use cases where data owners may not have private resources to participate in the computation, thus, they need to securely outsource the data analysis to untrusted third parties. We define a set of oblivious operators, explain the secure primitives they rely on, and analyze their costs in terms of operations and inter-party communication. We show how these operators can be composed to form end-to-end oblivious queries, and we introduce logical and physical optimizations that dramatically reduce the space and communication requirements during query execution, in some cases from quadratic to linear or from linear to logarithmic with respect to the cardinality of the input. We implement our framework on top of replicated secret sharing in a system called Secrecy and evaluate it using real queries from several MPC application areas. Our experiments demonstrate that the proposed optimizations can result in over 1000x lower execution times compared to baseline approaches, enabling Secrecy to outperform state-of-the-art frameworks and compute MPC queries on millions of input rows with a single thread per party.
Identification over Additive Noise Channels in the Presence of Feedback
Venue: arXiv cs.IT 2022
Year: 2022

We analyze deterministic message identification via channels with non-discrete additive white noise and with a noiseless feedback link under both average power and peak power constraints. The identification task is part of Post Shannon Theory. The consideration of communication systems beyond Shannon's approach is useful in order to increase the efficiency of information transmission for certain applications. We propose a coding scheme that first generates infinite common randomness between the sender and the receiver. If the channel has a positive message transmission feedback capacity, for given error thresholds and sufficiently large blocklength this common randomness is then used to construct arbitrarily large deterministic identification codes. In particular, the deterministic identification feedback capacity is infinite regardless of the scaling (exponential, doubly exponential, etc.) chosen for the capacity definition. Clearly, if randomized encoding is allowed in addition to the use of feedback, these results continue to hold.
Fair Dynamic Rationing
Venue: arXiv cs.GT 2022
Year: 2022

We study the allocative challenges that governmental and nonprofit organizations face when tasked with equitable and efficient rationing of a social good among agents whose needs (demands) realize sequentially and are possibly correlated. As one example, early in the COVID-19 pandemic, the Federal Emergency Management Agency faced overwhelming, temporally scattered, a priori uncertain, and correlated demands for medical supplies from different states. In such contexts, social planners aim to maximize the minimum fill rate across sequentially arriving agents, where each agent's fill rate is determined by an irrevocable, one-time allocation. For an arbitrarily correlated sequence of demands, we establish upper bounds on the expected minimum fill rate (ex-post fairness) and the minimum expected fill rate (ex-ante fairness) achievable by any policy. Our upper bounds are parameterized by the number of agents and the expected demand-to-supply ratio, yet we design a simple adaptive policy called projected proportional allocation (PPA) that simultaneously achieves matching lower bounds for both objectives (ex-post and ex-ante fairness), for any set of parameters. Our PPA policy is transparent and easy to implement, as it does not rely on distributional information beyond the first conditional moments. Despite its simplicity, we demonstrate that the PPA policy provides significant improvement over the canonical class of non-adaptive target-fill-rate policies. We complement our theoretical developments with a numerical study motivated by the rationing of COVID-19 medical supplies based on a standard SEIR modeling approach that is commonly used to forecast pandemic trajectories. In such a setting, our PPA policy significantly outperforms its theoretical guarantee as well as the optimal target-fill-rate policy.
Blockchain-based Transparency Framework for Privacy Preserving Third-party Services
Venue: arXiv cs.CR 2022
Year: 2022

Increasingly, information systems rely on computational, storage, and network resources deployed in third-party facilities such as cloud centers and edge nodes. Such an approach further exacerbates cybersecurity concerns constantly raised by numerous incidents of security and privacy attacks resulting in data leakage and identity theft, among others. These have, in turn, forced the creation of stricter security and privacy-related regulations and have eroded the trust in cyberspace. In particular, security-related services and infrastructures, such as Certificate Authorities (CAs) that provide digital certificate services and Third-Party Authorities (TPAs) that provide cryptographic key services, are critical components for establishing trust in crypto-based privacy-preserving applications and services. To address such trust issues, various transparency frameworks and approaches have been recently proposed in the literature. This paper proposes TAB framework that provides transparency and trustworthiness of third-party authority and third-party facilities using blockchain techniques for emerging crypto-based privacy-preserving applications. TAB employs the Ethereum blockchain as the underlying public ledger and also includes a novel smart contract to automate accountability with an incentive mechanism that motivates users to participate in auditing, and punishes unintentional or malicious behaviors. We implement TAB and show through experimental evaluation in the Ethereum official test network, Rinkeby, that the framework is efficient. We also formally show the security guarantee provided by TAB, and analyze the privacy guarantee and trustworthiness it provides.
VPT: Privacy Preserving Energy Trading and Block Mining Mechanism for Blockchain based Virtual Power Plants
Venue: arXiv cs.CR 2022
Year: 2022

The desire to overcome reliability issues of distributed energy resources (DERs) lead researchers to development of a novel concept named as virtual power plant (VPP). VPPs are supposed to carry out intelligent, secure, and smart energy trading among prosumers, buyers, and generating stations along with providing efficient energy management. Therefore, integrating blockchain in a decentralized VPP network emerged as a new paradigm, and recent experiments over this integration have shown fruitful results. However, this decentralization also suffers with energy management, trust, reliability, and efficiency issues due to the dynamic nature of DERs. In order to overcome this, in this paper, we first work over providing an efficient energy management strategy for VPP to enhance demand response, then we propose an energy oriented trading and block mining protocol and name it as proof of energy market (PoEM). To enhance it further, we integrate differential privacy in PoEM and propose a Private PoEM (PPoEM) model. Collectively, we propose a private decentralized VPP trading model and named it as Virtual Private Trading (VPT) model. We further carry out extensive theoretical analysis and derive step-by-step valuations for market race probability, market stability probability, energy trading expectation, winning state probability, and prospective leading time profit values. Afterwards, we carry out simulation-based experiments of our proposed model. The performance evaluation and theoretical analysis of our VPT model make it one of the most viable models for blockchain based VPP networks as compared to other state-of-the-art works.
Symmetric Sparse Boolean Matrix Factorization and Applications
Venue: arXiv cs.LG 2022
Year: 2022

In this work, we study a variant of nonnegative matrix factorization where we wish to find a symmetric factorization of a given input matrix into a sparse, Boolean matrix. Formally speaking, given $\mathbf{M}\in\mathbb{Z}^{m\times m}$, we want to find $\mathbf{W}\in\{0,1\}^{m\times r}$ such that $\| \mathbf{M} - \mathbf{W}\mathbf{W}^\top \|_0$ is minimized among all $\mathbf{W}$ for which each row is $k$-sparse. This question turns out to be closely related to a number of questions like recovering a hypergraph from its line graph, as well as reconstruction attacks for private neural network training. As this problem is hard in the worst-case, we study a natural average-case variant that arises in the context of these reconstruction attacks: $\mathbf{M} = \mathbf{W}\mathbf{W}^{\top}$ for $\mathbf{W}$ a random Boolean matrix with $k$-sparse rows, and the goal is to recover $\mathbf{W}$ up to column permutation. Equivalently, this can be thought of as recovering a uniformly random $k$-uniform hypergraph from its line graph. Our main result is a polynomial-time algorithm for this problem based on bootstrapping higher-order information about $\mathbf{W}$ and then decomposing an appropriate tensor. The key ingredient in our analysis, which may be of independent interest, is to show that such a matrix $\mathbf{W}$ has full column rank with high probability as soon as $m = \widetildeΩ(r)$, which we do using tools from Littlewood-Offord theory and estimates for binary Krawtchouk polynomials.
Pliable Index Coding via Conflict-Free Colorings of Hypergraphs
Venue: arXiv cs.IT 2022
Year: 2022

In the pliable index coding (PICOD) problem, a server is to serve multiple clients, each of which possesses a unique subset of the complete message set as side information and requests a new message which it does not have. The goal of the server is to do this using as few transmissions as possible. This work presents a hypergraph coloring approach to the scalar PICOD problem. A \textit{conflict-free coloring} of a hypergraph is known from literature as an assignment of colors to its vertices so that each hyperedge of the graph contains one uniquely colored vertex. For a given PICOD problem represented by a hypergraph consisting of messages as vertices and request-sets as hyperedges, we present achievable PICOD schemes using conflict-free colorings of the PICOD hypergraph. Various graph theoretic parameters arising out of such colorings (and some new coloring variants) then give a number of upper bounds on the optimal PICOD length, which we study in this work. Suppose the PICOD hypergraph has $m$ vertices and $n$ hyperedges, where every hyperedge overlaps with at most $Γ$ other hyperedges. We show easy to implement randomized algorithms for the following: (a) For the single request case, we give a PICOD of length $O(\log^2Γ)$. This result improves over known achievability results for some parameter ranges, (b) For the $t$-request case, we give an MDS code of length $\max(O(\log Γ\log m), O(t \log m))$. Further if the hyperedges (request sets) are sufficiently large, we give a PICOD of the same length as above, which is not based on MDS construction. In general, this gives an improvement over prior achievability results. Our codes are of near-optimal length (up to a multiplicative factor of $\log t$).
Modeling Financial Products and their Supply Chains
Venue: arXiv cs.LG 2022
Year: 2022

The objective of this paper is to explore how financial big data and machine learning methods can be applied to model and understand financial products. We focus on residential mortgage backed securities, resMBS, which were at the heart of the 2008 US financial crisis. These securities are contained within a prospectus and have a complex waterfall payoff structure. Multiple financial institutions form a supply chain to create prospectuses. To model this supply chain, we use unsupervised probabilistic methods, particularly dynamic topics models (DTM), to extract a set of features (topics) reflecting community formation and temporal evolution along the chain. We then provide insight into the performance of the resMBS securities and the impact of the supply chain through a series of increasingly comprehensive models. First, models at the security level directly identify salient features of resMBS securities that impact their performance. We then extend the model to include prospectus level features and demonstrate that the composition of the prospectus is significant. Our model also shows that communities along the supply chain that are associated with the generation of the prospectuses and securities have an impact on performance. We are the first to show that toxic communities that are closely linked to financial institutions that played a key role in the subprime crisis can increase the risk of failure of resMBS securities.