OpenRaiser/Intern-Atlas huggingface dataset:
Extracting and Analyzing Hidden Graphs from Relational Databases
Venue: arXiv cs.DB 2017
Year: 2017

Analyzing interconnection structures among underlying entities or objects in a dataset through the use of graph analytics has been shown to provide tremendous value in many application domains. However, graphs are not the primary representation choice for storing most data today, and in order to have access to these analyses, users are forced to extract data from their data stores, construct the requisite graphs, and then load them into some graph engine in order to execute their graph analysis task. Moreover, these graphs can be significantly larger than the initial input stored in the database, making it infeasible to construct or analyze such graphs in memory. In this paper we address both of these challenges by building a system that enables users to declaratively specify graph extraction tasks over a relational database schema and then execute graph algorithms on the extracted graphs. We propose a declarative domain-specific language for this purpose, and pair it up with a novel condensed, in-memory representation that significantly reduces the memory footprint of these graphs, permitting analysis of larger-than-memory graphs. We present a general algorithm for creating this condensed representation for a large class of graph extraction queries against arbitrary schemas. We observe that the condensed representation suffers from a duplication issue, that results in inaccuracies for most graph algorithms. We then present a suite of in-memory representations that handle this duplication in different ways and allow trading off the memory required and the computational cost for executing different graph algorithms. We introduce novel deduplication algorithms for removing this duplication in the graph, which are of independent interest for graph compression, and provide a comprehensive experimental evaluation over several real-world and synthetic datasets illustrating these trade-offs.
Signal Shaping for Two-User Gaussian Multiple Access Channels with Computation: Beyond the Cut-Set Bound
Venue: arXiv cs.IT 2017
Year: 2017

In this paper, we investigate the signal shaping in a two-user discrete time memoryless Gaussian multiple-access channel (MAC) with computation. It is shown that by optimizing input probability distribution, the transmission rate per transmitter is beyond the cut-set bound. In contrast with the single-user discrete memoryless channel, the Maxwell-Boltzmann distribution is no longer a good approximation to the optimal input probability distribution for this discrete-time Gaussian MAC with computation. Specifically, we derive and analyze the mutual information for this channel. Because of the computation in the destination, the mutual information is not concave in general on the input probability distribution, and then primal-dual interior-point method is used to solve this non-convex problem. Finally, some good input probability distributions for 16-ary pulse amplitude modulation (PAM) constellation are obtained and achieve $4.0349$ dB gain over the cut-set bound for the target transmission rate $3.0067$ bits/(channel use).
Case Study of a highly automated Layout Analysis and OCR of an incunabulum: 'Der Heiligen Leben' (1488)
Venue: arXiv cs.CV 2017
Year: 2017

This paper provides the first thorough documentation of a high quality digitization process applied to an early printed book from the incunabulum period (1450-1500). The entire OCR related workflow including preprocessing, layout analysis and text recognition is illustrated in detail using the example of 'Der Heiligen Leben', printed in Nuremberg in 1488. For each step the required time expenditure was recorded. The character recognition yielded excellent results both on character (97.57%) and word (92.19%) level. Furthermore, a comparison of a highly automated (LAREX) and a manual (Aletheia) method for layout analysis was performed. By considerably automating the segmentation the required human effort was reduced significantly from over 100 hours to less than six hours, resulting in only a slight drop in OCR accuracy. Realistic estimates for the human effort necessary for full text extraction from incunabula can be derived from this study. The printed pages of the complete work together with the OCR result is available online ready to be inspected and downloaded.
What Are People Tweeting about Zika? An Exploratory Study Concerning Symptoms, Treatment, Transmission, and Prevention
Venue: arXiv cs.SI 2017
Year: 2017

The purpose of this study was to do a dataset distribution analysis, a classification performance analysis, and a topical analysis concerning what people are tweeting about four disease characteristics: symptoms, transmission, prevention, and treatment. A combination of natural language processing and machine learning techniques were used to determine what people are tweeting about Zika. Specifically, a two-stage classifier system was built to find relevant tweets on Zika, and then categorize these into the four disease categories. Tweets in each disease category were then examined using latent dirichlet allocation (LDA) to determine the five main tweet topics for each disease characteristic. Results 1,234,605 tweets were collected. Tweets by males and females were similar (28% and 23% respectively). The classifier performed well on the training and test data for relevancy (F=0.87 and 0.99 respectively) and disease characteristics (F=0.79 and 0.90 respectively). Five topics for each category were found and discussed with a focus on the symptoms category. Through this process, we demonstrate how misinformation can be discovered so that public health officials can respond to the tweets with misinformation.
On rescheduling due to machine disruption while to minimize the total weighted completion time
Venue: arXiv cs.DS 2017
Year: 2017

We investigate a single machine rescheduling problem that arises from an unexpected machine unavailability, after the given set of jobs has already been scheduled to minimize the total weighted completion time. Such a disruption is represented as an unavailable time interval and is revealed to the production planner before any job is processed; the production planner wishes to reschedule the jobs to minimize the alteration to the originally planned schedule, which is measured as the maximum time deviation between the original and the new schedules for all the jobs. The objective function in this rescheduling problem is to minimize the sum of the total weighted completion time and the weighted maximum time deviation, under the constraint that the maximum time deviation is bounded above by a given value. That is, the maximum time deviation is taken both as a constraint and as part of the objective function. We present a pseudo-polynomial time exact algorithm and a fully polynomial time approximation scheme, the latter of which is the best possible given that the general problem is NP-hard.
ACIA, not ACID: Conditions, Properties and Challenges
Venue: arXiv cs.DC 2017
Year: 2017

Although ACID is the previous golden rule for transaction support, durability is now not a basic requirement for data storage. Rather, high availability is becoming the first-class property required by online applications. We show that high availability of data is almost surely a stronger property than durability. We thus propose ACIA (Atomicity, Consistency, Isolation, Availability) as the new standard for transaction support. Essentially, the shift from ACID to ACIA is due to the change of assumed conditions for data management. Four major condition changes exist. With ACIA transactions, more diverse requirements can be flexibly supported for applications through the specification of consistency levels, isolation levels and fault tolerance levels. Clarifying the ACIA properties enables the exploitation of techniques used for ACID transactions, as well as bringing about new challenges for research.
Non-colocated Time-Reversal MUSIC: High-SNR Distribution of Null Spectrum
Venue: arXiv cs.IT 2017
Year: 2017

We derive the asymptotic distribution of the null spectrum of the well-known Multiple Signal Classification (MUSIC) in its computational Time-Reversal (TR) form. The result pertains to a single-frequency non-colocated multistatic scenario and several TR-MUSIC variants are here investigated. The analysis builds upon the 1st-order perturbation of the singular value decomposition and allows a simple characterization of null-spectrum moments (up to the 2nd order). This enables a comparison in terms of spectrums stability. Finally, a numerical analysis is provided to confirm the theoretical findings.
The Role of Transmitter Cooperation in Linear Interference Networks with Block Erasures
Venue: arXiv cs.IT 2017
Year: 2017

In this work, we explore the potential and optimal use of transmitter cooperation in wireless interference networks with deep fading conditions. We consider a linear interference network with K transmitter-receiver pairs, where each transmitter can be connected to two neighboring receivers. Long-term fluctuations (shadow fading) in the wireless channel can lead to any link being erased with probability p. Each receiver is interested in one unique message that can be available at two transmitters. The considered rate criterion is the average per user degrees of freedom (puDoF) as K goes to infinity. Prior to this work, the optimal assignment of messages to transmitters were identified in the two limits as p goes to 0 and as p goes to 1. We identify new schemes that achieve average puDoF values that are higher than the state of the art for a significant part of the range 0 < p < 1. The key idea to our results is to understand that the role of cooperation shifts from increasing the probability of delivering a message to its intended destination at high values of p, to interference cancellation at low values of p. Our schemes are based on an algorithm that achieves the optimal DoF value in any network realization, when restricted to a given message assignment as well as the use of zero-forcing schemes.
Quotients in monadic programming: Projective algebras are equivalent to coalgebras
Venue: arXiv cs.LO 2017
Year: 2017

In monadic programming, datatypes are presented as free algebras, generated by data values, and by the algebraic operations and equations capturing some computational effects. These algebras are free in the sense that they satisfy just the equations imposed by their algebraic theory, and remain free of any additional equations. The consequence is that they do not admit quotient types. This is, of course, often inconvenient. Whenever a computation involves data with multiple representatives, and they need to be identified according to some equations that are not satisfied by all data, the monadic programmer has to leave the universe of free algebras, and resort to explicit destructors. We characterize the situation when these destructors are preserved under all operations, and the resulting quotients of free algebras are also their subalgebras. Such quotients are called *projective*. Although popular in universal algebra, projective algebras did not attract much attention in the monadic setting, where they turn out to have a surprising avatar: for any given monad, a suitable category of projective algebras is equivalent with the category of coalgebras for the comonad induced by any monad resolution. For a monadic programmer, this equivalence provides a convenient way to implement polymorphic quotients as coalgebras. The dual correspondence of injective coalgebras and all algebras leads to a different family of quotient types, which seems to have a different family of applications. Both equivalences also entail several general corollaries concerning monadicity and comonadicity.
Tight Inefficiency Bounds for Perception-Parameterized Affine Congestion Games
Venue: arXiv cs.GT 2017
Year: 2017

Congestion games constitute an important class of non-cooperative games which was introduced by Rosenthal in 1973. In recent years, several extensions of these games were proposed to incorporate aspects that are not captured by the standard model. Examples of such extensions include the incorporation of risk sensitive players, the modeling of altruistic player behavior and the imposition of taxes on the resources. These extensions were studied intensively with the goal to obtain a precise understanding of the inefficiency of equilibria of these games. In this paper, we introduce a new model of congestion games that captures these extensions (and additional ones) in a unifying way. The key idea here is to parameterize both the perceived cost of each player and the social cost function of the system designer. Intuitively, each player perceives the load induced by the other players by an extent of ρ, while the system designer estimates that each player perceives the load of all others by an extent of σ. The above mentioned extensions reduce to special cases of our model by choosing the parameters ρ and σ accordingly. As in most related works, we concentrate on congestion games with affine latency functions here. Despite the fact that we deal with a more general class of congestion games, we manage to derive tight bounds on the price of anarchy and the price of stability for a large range of pa- rameters. Our bounds provide a complete picture of the inefficiency of equilibria for these perception-parameterized congestion games. As a result, we obtain tight bounds on the price of anarchy and the price of stability for the above mentioned extensions. Our results also reveal how one should "design" the cost functions of the players in order to reduce the price of anar- chy.
Exponential Source/Channel Duality
Venue: arXiv cs.IT 2017
Year: 2017

We propose a source/channel duality in the exponential regime, where success/failure in source coding parallels error/correctness in channel coding, and a distortion constraint becomes a log-likelihood ratio (LLR) threshold. We establish this duality by first deriving exact exponents for lossy coding of a memoryless source P, at distortion D, for a general i.i.d. codebook distribution Q, for both encoding success (R < R(P,Q,D)) and failure (R > R(P,Q,D)). We then turn to maximum likelihood (ML) decoding over a memoryless channel P with an i.i.d. input Q, and show that if we substitute P=QP, Q=Q, and D=0 under the LLR distortion measure, then the exact exponents for decoding-error (R < I(Q, P)) and strict correct-decoding (R > I(Q, P)) follow as special cases of the exponents for source encoding success/failure, respectively. Moreover, by letting the threshold D take general values, the exact random-coding exponents for erasure (D > 0) and list decoding (D < 0) under the simplified Forney decoder are obtained. Finally, we derive the exact random-coding exponent for Forney's optimum tradeoff erasure/list decoder, and show that at the erasure regime it coincides with Forney's lower bound and with the simplified decoder exponent.
Alpha Fair Coded Caching
Venue: arXiv cs.IT 2017
Year: 2017

The performance of existing \emph{coded caching} schemes is sensitive to worst channel quality, a problem which is exacerbated when communicating over fading channels. In this paper we address this limitation in the following manner: \emph{in short-term}, we allow transmissions to subsets of users with good channel quality, avoiding users with fades, while \emph{in long-term} we ensure fairness across the different users.Our online scheme combines (i) joint scheduling and power control for the broadcast channel with fading, and (ii) congestion control for ensuring the optimal long-term average performance. We restrict the caching operations to the decentralized scheme of \cite{maddah2013decentralized}, and subject to this restriction we prove that our scheme has near-optimal overall performance with respect to the convex alpha-fairness coded caching optimization. By tuning the coefficient alpha, the operator can differentiate user performance with respect to video delivery rates achievable by coded caching. We demonstrate via simulations our scheme's superiority over legacy coded caching and unicast opportunistic scheduling, which are identified as special cases of our general framework.
Pose Invariant Embedding for Deep Person Re-identification
Venue: arXiv cs.CV 2017
Year: 2017

Pedestrian misalignment, which mainly arises from detector errors and pose variations, is a critical problem for a robust person re-identification (re-ID) system. With bad alignment, the background noise will significantly compromise the feature learning and matching process. To address this problem, this paper introduces the pose invariant embedding (PIE) as a pedestrian descriptor. First, in order to align pedestrians to a standard pose, the PoseBox structure is introduced, which is generated through pose estimation followed by affine transformations. Second, to reduce the impact of pose estimation errors and information loss during PoseBox construction, we design a PoseBox fusion (PBF) CNN architecture that takes the original image, the PoseBox, and the pose estimation confidence as input. The proposed PIE descriptor is thus defined as the fully connected layer of the PBF network for the retrieval task. Experiments are conducted on the Market-1501, CUHK03, and VIPeR datasets. We show that PoseBox alone yields decent re-ID accuracy and that when integrated in the PBF network, the learned PIE descriptor produces competitive performance compared with the state-of-the-art approaches.
Ethical Considerations in Artificial Intelligence Courses
Venue: arXiv cs.AI 2017
Year: 2017

The recent surge in interest in ethics in artificial intelligence may leave many educators wondering how to address moral, ethical, and philosophical issues in their AI courses. As instructors we want to develop curriculum that not only prepares students to be artificial intelligence practitioners, but also to understand the moral, ethical, and philosophical impacts that artificial intelligence will have on society. In this article we provide practical case studies and links to resources for use by AI educators. We also provide concrete suggestions on how to integrate AI ethics into a general artificial intelligence course and how to teach a stand-alone artificial intelligence ethics course.
A Variational Characterization of Rényi Divergences
Venue: arXiv cs.IT 2017
Year: 2017

Atar, Chowdhary and Dupuis have recently exhibited a variational formula for exponential integrals of bounded measurable functions in terms of Rényi divergences. We develop a variational characterization of the Rényi divergences between two probability distributions on a measurable sace in terms of relative entropies. When combined with the elementary variational formula for exponential integrals of bounded measurable functions in terms of relative entropy, this yields the variational formula of Atar, Chowdhary and Dupuis as a corollary. We also develop an analogous variational characterization of the Rényi divergence rates between two stationary finite state Markov chains in terms of relative entropy rates. When combined with Varadhan's variational characterization of the spectral radius of square matrices with nonnegative entries in terms of relative entropy, this yields an analog of the variational formula of Atar, Chowdary and Dupuis in the framework of finite state Markov chains.
Private Information Retrieval from MDS Coded Data with Colluding Servers: Settling a Conjecture by Freij-Hollanti et al.
Venue: arXiv cs.IT 2017
Year: 2017

A $(K, N, T, K_c)$ instance of the MDS-TPIR problem is comprised of $K$ messages and $N$ distributed servers. Each message is separately encoded through a $(K_c, N)$ MDS storage code. A user wishes to retrieve one message, as efficiently as possible, while revealing no information about the desired message index to any colluding set of up to $T$ servers. The fundamental limit on the efficiency of retrieval, i.e., the capacity of MDS-TPIR is known only at the extremes where either $T$ or $K_c$ belongs to $\{1,N\}$. The focus of this work is a recent conjecture by Freij-Hollanti, Gnilke, Hollanti and Karpuk which offers a general capacity expression for MDS-TPIR. We prove that the conjecture is false by presenting as a counterexample a PIR scheme for the setting $(K, N, T, K_c) = (2,4,2,2)$, which achieves the rate $3/5$, exceeding the conjectured capacity, $4/7$. Insights from the counterexample lead us to capacity characterizations for various instances of MDS-TPIR including all cases with $(K, N, T, K_c) = (2,N,T,N-1)$, where $N$ and $T$ can be arbitrary.
A Mood Value for Fair Resource Allocations
Venue: arXiv cs.NI 2017
Year: 2017

In networking and computing, resource allocation is typically addressed using classical sharing protocols as, for instance, the proportional division rule, the max-min fair allocation , or other solutions inspired by cooperative game theory. In this paper, we argue that, describing the resource allocation problem as a cooperative game, such classical resource allocation approaches, as well as associated notions of fairness, show important limitations. We identify in the individual satisfaction rate the key aspect of the challenge of defining a new notion of fairness and, consequently, a resource allocation algorithm more appropriate for the cooperative context. We generalize the concept of user satisfaction considering the set of admissible solutions for bankruptcy games. We adapt the Jain's fairness index to include the new user satisfaction rate. Accordingly, we propose a new allocation rule we call 'Mood Value'. For each user it equalizes our novel game-theoretic definition of user satisfaction with respect to a distribution of the resource. We test the mood value and the new fairness index through extensive simulations showing how they better support the fairness analysis.
Beyond the EULA: Improving consent for data mining
Venue: arXiv cs.CY 2017
Year: 2017

Companies and academic researchers may collect, process, and distribute large quantities of personal data without the explicit knowledge or consent of the individuals to whom the data pertains. Existing forms of consent often fail to be appropriately readable and ethical oversight of data mining may not be sufficient. This raises the question of whether existing consent instruments are sufficient, logistically feasible, or even necessary, for data mining. In this chapter, we review the data collection and mining landscape, including commercial and academic activities, and the relevant data protection concerns, to determine the types of consent instruments used. Using three case studies, we use the new paradigm of human-data interaction to examine whether these existing approaches are appropriate. We then introduce an approach to consent that has been empirically demonstrated to improve on the state of the art and deliver meaningful consent. Finally, we propose some best practices for data collectors to ensure their data mining activities do not violate the expectations of the people to whom the data relate.
On the Degrees-of-Freedom of the MIMO Three-Way Channel with Intermittent Connectivity
Venue: arXiv cs.IT 2017
Year: 2017

The degrees-of-freedom (DoF) of the multi-antenna three-way channel (3WC) with an intermittent node is studied. Special attention is given to the impact of adaptation. A nonadaptive transmission scheme based on interference alignment, zero-forcing, and erasure-channel treatment is proposed, and its corresponding DoF region is derived. Then, it is shown that this scheme achieves the sum-DoF of the intermittent channel, in addition to the DoF region of the nonintermittent one. Thus, adaptation is not necessary from those perspectives. To the contrary, it is shown that adaptation is necessary for achieving the DoF region of the intermittent case. This is shown by deriving an outer bound for the intermittent channel with nonadaptive encoding, and giving a counterexample of an adaptive scheme which achieves DoF tuples outside this bound. This highlights the importance of cooperation in this intermittent network.