OpenRaiser/Intern-Atlas huggingface dataset:
Notes on "Notes on the Synthesis of Form": Dawning Insights in Early Christopher Alexander
Venue: arXiv cs.SE 2023
Year: 2023

This essay is a picaresque -- a first-person narrative relating the adventures of a rogue (me) sifting through the mind of Christopher Alexander as he left behind formalized design thinking in favor of a more intuitive, almost spiritual process. The work of Christopher Alexander is familiar to many computer scientists: for some it's patterns, for some it's the mystical **quality without a name** and "Nature of Order"; for many more it's "Notes on the Synthesis of Form" -- Alexander's formalized design method and foreshadowing ideas about cohesion and coupling in software. Since the publication of "Design Patterns" by Gamma et al. in 1994, there have been hundreds of books published about design / software patterns, thousands of published pattern languages, and tens of thousands of published patterns. "Notes," published in 1964, was quickly followed by one of Alexander's most important essays, "A City is Not a Tree," in which he repudiates the formal method described in "Notes," and his Preface to the paperback edition of "Notes" in 1971 repeats the repudiation. For many close readers of Alexander, this discontinuity is startling and unexplained. When I finally read "Notes" in 2015, I was struck by the detailed worked example, along with a peculiar mathematical treatment of the method, and a hint that the modularization presented in the example was reckoned by a computer program he had written -- all in the late 1950s and early 1960s. Because of my fascination with metaheuristic optimization, I couldn't resist trying to replicate his experimental results. Computers and their programs relish dwelling on flaws in your thinking -- Alexander was not exempt. By engaging in hermeneutics and software archeology, I was able to uncover / discover the trajectory of his thinking as he encountered failures and setbacks with his computer programs. My attempted replication also failed, and that led me to try to unearth the five different programs he wrote, understand them, and figure out how one led to the next. They are not described in published papers, only in internal reports. My search for these reports led to their being made available on the Net. What I found in my voyage were the early parts of a chain of thought that started with cybernetics, mathematics, and a plain-spoken computer; passed through "A City is Not a Tree"; paused to "make God appear in the middle of a field"; and ended with this fundamental design goal: **I try to make the volume of the building so that it carries in it all feeling. To reach this feeling, I try to make the building so that it carries my eternal sadness. It comes, as nearly as I can in a building, to the point of tears.**
Symmetries of structures that fail to interpret something finite
Venue: arXiv cs.LO 2023
Year: 2023

We investigate structural implications arising from the condition that a given directed graph does not interpret, in the sense of primitive positive interpretation with parameters or orbits, every finite structure. Our results generalize several theorems from the literature and yield further algebraic invariance properties that must be satisfied in every such graph. Algebraic properties of this kind are tightly connected to the tractability of constraint satisfaction problems, and we obtain new such properties even for infinite countably categorical graphs. We balance these positive results by showing the existence of a countably categorical hypergraph that fails to interpret some finite structure, while still lacking some of the most essential algebraic invariance properties known to hold for finite structures.
HL Dataset: Visually-grounded Description of Scenes, Actions and Rationales
Venue: arXiv cs.CL 2023
Year: 2023

Current captioning datasets focus on object-centric captions, describing the visible objects in the image, e.g. "people eating food in a park". Although these datasets are useful to evaluate the ability of Vision & Language models to recognize and describe visual content, they do not support controlled experiments involving model testing or fine-tuning, with more high-level captions, which humans find easy and natural to produce. For example, people often describe images based on the type of scene they depict ('people at a holiday resort') and the actions they perform ('people having a picnic'). Such descriptions draw on personal experience and commonsense assumptions. We present the High-Level Dataset a dataset extending 14997 images from the COCO dataset, aligned with a new set of 134,973 human-annotated (high-level) captions collected along three axes: scenes, actions, and rationales. We further extend this dataset with confidence scores collected from an independent set of readers, as well as a set of narrative captions generated synthetically, by combining each of the three axes. We describe this dataset and analyse it extensively. We also present baseline results for the High-Level Captioning task.
From Circuits to SoC Processors: Arithmetic Approximation Techniques & Embedded Computing Methodologies for DSP Acceleration
Venue: arXiv cs.AR 2023
Year: 2023

The computing industry is forced to find alternative design approaches and computing platforms to sustain increased power efficiency, while providing sufficient performance. Among the examined solutions, Approximate Computing, Hardware Acceleration, and Heterogeneous Computing have gained great momentum. In this Dissertation, we introduce design solutions and methodologies, built on top of the preceding computing paradigms, for the development of energy-efficient DSP and AI accelerators. In particular, we adopt the promising paradigm of Approximate Computing and apply new approximation techniques in the design of arithmetic circuits. The proposed arithmetic approximation techniques involve bit-level optimizations, inexact operand encodings, and skipping of computations, while they are applied in both fixed- and floating-point arithmetic. We also conduct an extensive exploration on combinations among the approximation techniques and propose a low-overhead scheme for seamlessly adjusting the approximation degree of our circuits at runtime. Based on our methodology, these arithmetic approximation techniques are then combined with hardware design techniques to implement approximate ASIC- and FPGA-based DSP and AI accelerators. Moreover, we propose methodologies for the efficient mapping of DSP/AI kernels on distinctive embedded devices, i.e., the space-grade FPGAs and the heterogeneous VPUs. On the one hand, we cope with the decreased flexibility of space-grade technology and the technical challenges that arise in new FPGA tools. On the other hand, we unlock the full potential of heterogeneity by exploiting all the diverse processors and memories. Based on our methodology, we efficiently map computer vision algorithms onto the radiation-hardened NanoXplore's FPGAs and accelerate DSP & CNN kernels on Intel's Myriad VPUs.
Engineering Massively Parallel MST Algorithms
Venue: arXiv cs.DC 2023
Year: 2023

We develop and extensively evaluate highly scalable distributed-memory algorithms for computing minimum spanning trees (MSTs). At the heart of our solutions is a scalable variant of Boruvka's algorithm. For partitioned graphs with many local edges, we improve this with an effective form of contracting local parts of the graph during a preprocessing step. We also adapt the filtering concept of the best practical sequential algorithm to develop a massively parallel Filter-Boruvka algorithm that is very useful for graphs with poor locality and high average degree. Our experiments indicate that our algorithms scale well up to at least 65 536 cores and are up to 800 times faster than previous distributed MST algorithms.
Grading and Ranking Large number of candidates
Venue: arXiv cs.GT 2023
Year: 2023

It is common that a jury must grade a set of candidates in a cardinal scale such as {1,2,3,4,5} or an ordinal scale such as {Great, Good, Average, Bad }. When the number of candidates is very large such as hotels (BOOKING), restaurants (GOOGLE), apartments (AIRBNB), drivers (UBER), or papers (EC), it is unreasonable to assume that each jury member will provide a separate grade for each candidate. Each jury member is more likely to abstain for some candidates, cast a blank vote, or be associated at random, or as a function of its expertise, with only a small subset of the candidates and is asked to grade each of those. Extending the classical theory, we study aggregation methods in which a voter will not be eligible to grade all the candidates, and the candidates are not eligible for the same sets of voters. Moreover, each candidate on which they are eligible, the voter will have the choice between: a blank vote, grade the candidate, or abstain. Assuming single-peaked preferences over the grades, we axiomatically characterise a broad class of strategy-proof grading mechanisms satisfying axioms such as unanimity, anonymity, neutrality, participation or consistency. Finally, when a strict ranking is necessary (to distinguish let say between two borderline papers in a conference), some tie-breaking rules, extending the leximin and majority judgment, are defined and are shown to be equivalent to some strategy-proof grading functions on a richer space of outcome. Our paper will propose new rules, called phantom-proxy mechanisms, to aggregate the votes in the examples above or others, which differ from the usual average mark, that are easily manipulable. Moreover, the phantom-proxy are able to reduce the injustices caused by some candidates juries too generous or severe.
Federated Nearest Neighbor Machine Translation
Venue: arXiv cs.CL 2023
Year: 2023

To protect user privacy and meet legal regulations, federated learning (FL) is attracting significant attention. Training neural machine translation (NMT) models with traditional FL algorithm (e.g., FedAvg) typically relies on multi-round model-based interactions. However, it is impractical and inefficient for machine translation tasks due to the vast communication overheads and heavy synchronization. In this paper, we propose a novel federated nearest neighbor (FedNN) machine translation framework that, instead of multi-round model-based interactions, leverages one-round memorization-based interaction to share knowledge across different clients to build low-overhead privacy-preserving systems. The whole approach equips the public NMT model trained on large-scale accessible data with a $k$-nearest-neighbor ($$kNN) classifier and integrates the external datastore constructed by private text data in all clients to form the final FL model. A two-phase datastore encryption strategy is introduced to achieve privacy-preserving during this process. Extensive experiments show that FedNN significantly reduces computational and communication costs compared with FedAvg, while maintaining promising performance in different FL settings.
DisCO: Portrait Distortion Correction with Perspective-Aware 3D GANs
Venue: arXiv cs.CV 2023
Year: 2023

Close-up facial images captured at short distances often suffer from perspective distortion, resulting in exaggerated facial features and unnatural/unattractive appearances. We propose a simple yet effective method for correcting perspective distortions in a single close-up face. We first perform GAN inversion using a perspective-distorted input facial image by jointly optimizing the camera intrinsic/extrinsic parameters and face latent code. To address the ambiguity of joint optimization, we develop starting from a short distance, optimization scheduling, reparametrizations, and geometric regularization. Re-rendering the portrait at a proper focal length and camera distance effectively corrects perspective distortions and produces more natural-looking results. Our experiments show that our method compares favorably against previous approaches qualitatively and quantitatively. We showcase numerous examples validating the applicability of our method on in-the-wild portrait photos. We will release our code and the evaluation protocol to facilitate future work.
Characterizing Novelty in the Military Domain
Venue: arXiv cs.AI 2023
Year: 2023

A critical factor in utilizing agents with Artificial Intelligence (AI) is their robustness to novelty. AI agents include models that are either engineered or trained. Engineered models include knowledge of those aspects of the environment that are known and considered important by the engineers. Learned models form embeddings of aspects of the environment based on connections made through the training data. In operation, however, a rich environment is likely to present challenges not seen in training sets or accounted for in engineered models. Worse still, adversarial environments are subject to change by opponents. A program at the Defense Advanced Research Project Agency (DARPA) seeks to develop the science necessary to develop and evaluate agents that are robust to novelty. This capability will be required, before AI has the role envisioned within mission critical environments. As part of the Science of AI and Learning for Open-world Novelty (SAIL-ON), we are mapping possible military domain novelty types to a domain-independent ontology developed as part of a theory of novelty. Characterizing the possible space of novelty mathematically and ontologically will allow us to experiment with agent designs that are coming from the DARPA SAIL-ON program in relevant military environments. Utilizing the same techniques as being used in laboratory experiments, we will be able to measure agent ability to detect, characterize, and accommodate novelty.
Auto-HeG: Automated Graph Neural Network on Heterophilic Graphs
Venue: arXiv cs.LG 2023
Year: 2023

Graph neural architecture search (NAS) has gained popularity in automatically designing powerful graph neural networks (GNNs) with relieving human efforts. However, existing graph NAS methods mainly work under the homophily assumption and overlook another important graph property, i.e., heterophily, which exists widely in various real-world applications. To date, automated heterophilic graph learning with NAS is still a research blank to be filled in. Due to the complexity and variety of heterophilic graphs, the critical challenge of heterophilic graph NAS mainly lies in developing the heterophily-specific search space and strategy. Therefore, in this paper, we propose a novel automated graph neural network on heterophilic graphs, namely Auto-HeG, to automatically build heterophilic GNN models with expressive learning abilities. Specifically, Auto-HeG incorporates heterophily into all stages of automatic heterophilic graph learning, including search space design, supernet training, and architecture selection. Through the diverse message-passing scheme with joint micro-level and macro-level designs, we first build a comprehensive heterophilic GNN search space, enabling Auto-HeG to integrate complex and various heterophily of graphs. With a progressive supernet training strategy, we dynamically shrink the initial search space according to layer-wise variation of heterophily, resulting in a compact and efficient supernet. Taking a heterophily-aware distance criterion as the guidance, we conduct heterophilic architecture selection in the leave-one-out pattern, so that specialized and expressive heterophilic GNN architectures can be derived. Extensive experiments illustrate the superiority of Auto-HeG in developing excellent heterophilic GNNs to human-designed models and graph NAS models.
Targeted Search Control in AlphaZero for Effective Policy Improvement
Venue: arXiv cs.AI 2023
Year: 2023

AlphaZero is a self-play reinforcement learning algorithm that achieves superhuman play in chess, shogi, and Go via policy iteration. To be an effective policy improvement operator, AlphaZero's search requires accurate value estimates for the states appearing in its search tree. AlphaZero trains upon self-play matches beginning from the initial state of a game and only samples actions over the first few moves, limiting its exploration of states deeper in the game tree. We introduce Go-Exploit, a novel search control strategy for AlphaZero. Go-Exploit samples the start state of its self-play trajectories from an archive of states of interest. Beginning self-play trajectories from varied starting states enables Go-Exploit to more effectively explore the game tree and to learn a value function that generalizes better. Producing shorter self-play trajectories allows Go-Exploit to train upon more independent value targets, improving value training. Finally, the exploration inherent in Go-Exploit reduces its need for exploratory actions, enabling it to train under more exploitative policies. In the games of Connect Four and 9x9 Go, we show that Go-Exploit learns with a greater sample efficiency than standard AlphaZero, resulting in stronger performance against reference opponents and in head-to-head play. We also compare Go-Exploit to KataGo, a more sample efficient reimplementation of AlphaZero, and demonstrate that Go-Exploit has a more effective search control strategy. Furthermore, Go-Exploit's sample efficiency improves when KataGo's other innovations are incorporated.
Best-of-Three-Worlds Linear Bandit Algorithm with Variance-Adaptive Regret Bounds
Venue: arXiv cs.LG 2023
Year: 2023

This paper proposes a linear bandit algorithm that is adaptive to environments at two different levels of hierarchy. At the higher level, the proposed algorithm adapts to a variety of types of environments. More precisely, it achieves best-of-three-worlds regret bounds, i.e., of ${O}(\sqrt{T \log T})$ for adversarial environments and of $O(\frac{\log T}{Δ_{\min}} + \sqrt{\frac{C \log T}{Δ_{\min}}})$ for stochastic environments with adversarial corruptions, where $T$, $Δ_{\min}$, and $C$ denote, respectively, the time horizon, the minimum sub-optimality gap, and the total amount of the corruption. Note that polynomial factors in the dimensionality are omitted here. At the lower level, in each of the adversarial and stochastic regimes, the proposed algorithm adapts to certain environmental characteristics, thereby performing better. The proposed algorithm has data-dependent regret bounds that depend on all of the cumulative loss for the optimal action, the total quadratic variation, and the path-length of the loss vector sequence. In addition, for stochastic environments, the proposed algorithm has a variance-adaptive regret bound of $O(\frac{σ^2 \log T}{Δ_{\min}})$ as well, where $σ^2$ denotes the maximum variance of the feedback loss. The proposed algorithm is based on the SCRiBLe algorithm. By incorporating into this a new technique we call scaled-up sampling, we obtain high-level adaptability, and by incorporating the technique of optimistic online learning, we obtain low-level adaptability.
Calibration of NYURay, a 3D mmWave and sub-THz Ray Tracer using Indoor, Outdoor, and Factory Channel Measurements
Venue: arXiv cs.IT 2023
Year: 2023

Ray tracing is a powerful tool that can be used to predict wireless channel characteristics, reducing the need for extensive channel measurements for channel characterization, evaluation of performance of sensing applications such as position location, and wireless network deployment. In this work, NYURay, a 3D mmWave and sub-THz ray tracer, is introduced, which is calibrated to wireless channel propagation measurements conducted at 28, 73, and 140 GHz, in indoor office, outdoor, and factory environments. We present an accurate yet low-complexity calibration procedure to obtain electrical properties of materials in any environment by modeling the reflection coefficient of building materials to be independent of the angle of incidence, a simplification shown to be quite effective in [1] over 30 years ago. We show that after calibration, NYURay can accurately predict individual directional multipath signal power. The standard deviation in the error of the directional multipath power predicted by the ray tracer compared to the directional measured power was less than 3 dB in indoor office environments and less than 2 dB in outdoor and factory environments.
Emotion Prediction Oriented method with Multiple Supervisions for Emotion-Cause Pair Extraction
Venue: arXiv cs.CL 2023
Year: 2023

Emotion-cause pair extraction (ECPE) task aims to extract all the pairs of emotions and their causes from an unannotated emotion text. The previous works usually extract the emotion-cause pairs from two perspectives of emotion and cause. However, emotion extraction is more crucial to the ECPE task than cause extraction. Motivated by this analysis, we propose an end-to-end emotion-cause extraction approach oriented toward emotion prediction (EPO-ECPE), aiming to fully exploit the potential of emotion prediction to enhance emotion-cause pair extraction. Considering the strong dependence between emotion prediction and emotion-cause pair extraction, we propose a synchronization mechanism to share their improvement in the training process. That is, the improvement of emotion prediction can facilitate the emotion-cause pair extraction, and then the results of emotion-cause pair extraction can also be used to improve the accuracy of emotion prediction simultaneously. For the emotion-cause pair extraction, we divide it into genuine pair supervision and fake pair supervision, where the genuine pair supervision learns from the pairs with more possibility to be emotion-cause pairs. In contrast, fake pair supervision learns from other pairs. In this way, the emotion-cause pairs can be extracted directly from the genuine pair, thereby reducing the difficulty of extraction. Experimental results show that our approach outperforms the 13 compared systems and achieves new state-of-the-art performance.
Annotating Covert Hazardous Driving Scenarios Online: Utilizing Drivers' Electroencephalography (EEG) Signals
Venue: arXiv cs.HC 2023
Year: 2023

As autonomous driving systems prevail, it is becoming increasingly critical that the systems learn from databases containing fine-grained driving scenarios. Most databases currently available are human-annotated; they are expensive, time-consuming, and subject to behavioral biases. In this paper, we provide initial evidence supporting a novel technique utilizing drivers' electroencephalography (EEG) signals to implicitly label hazardous driving scenarios while passively viewing recordings of real-road driving, thus sparing the need for manual annotation and avoiding human annotators' behavioral biases during explicit report. We conducted an EEG experiment using real-life and animated recordings of driving scenarios and asked participants to report danger explicitly whenever necessary. Behavioral results showed the participants tended to report danger only when overt hazards (e.g., a vehicle or a pedestrian appearing unexpectedly from behind an occlusion) were in view. By contrast, their EEG signals were enhanced at the sight of both an overt hazard and a covert hazard (e.g., an occlusion signalling possible appearance of a vehicle or a pedestrian from behind). Thus, EEG signals were more sensitive to driving hazards than explicit reports. Further, the Time-Series AI (TSAI) successfully classified EEG signals corresponding to overt and covert hazards. We discuss future steps necessary to materialize the technique in real life.