OpenRaiser/Intern-Atlas huggingface dataset:
Beyond Transactional Democracy: A Study of Civic Tech in Canada
Venue: arXiv cs.CY 2023
Year: 2023

Technologies are increasingly enrolled in projects to involve civilians in the work of policy-making, often under the label of 'civic technology'. But conventional forms of participation through transactions such as voting provide limited opportunities for engagement. In response, some civic tech groups organize around issues of shared concern to explore new forms of democratic technologies. How does their work affect the relationship between publics and public servants? This paper explores how a Civic Tech Toronto creates a platform for civic engagement through the maintenance of an autonomous community for civic engagement and participation that is casual, social, nonpartisan, experimental, and flexible. Based on two years of action research, including community organizing, interviews, and observations, this paper shows how this grassroots civic tech group creates a civic platform that places a diverse range of participants in contact with the work of public servants, helping to build capacities and relationships that prepare both publics and public servants for the work of participatory democracy. The case shows that understanding civic tech requires a lens beyond the mere analysis or production of technical artifacts. As a practice for making technologies that is social and participatory, civic tech creates alternative modes of technology development and opportunities for experimentation and learning, and it can reconfigure the roles of democratic participants.
Achieving Better Regret against Strategic Adversaries
Venue: arXiv cs.LG 2023
Year: 2023

We study online learning problems in which the learner has extra knowledge about the adversary's behaviour, i.e., in game-theoretic settings where opponents typically follow some no-external regret learning algorithms. Under this assumption, we propose two new online learning algorithms, Accurate Follow the Regularized Leader (AFTRL) and Prod-Best Response (Prod-BR), that intensively exploit this extra knowledge while maintaining the no-regret property in the worst-case scenario of having inaccurate extra information. Specifically, AFTRL achieves $O(1)$ external regret or $O(1)$ \emph{forward regret} against no-external regret adversary in comparison with $O(\sqrt{T})$ \emph{dynamic regret} of Prod-BR. To the best of our knowledge, our algorithm is the first to consider forward regret that achieves $O(1)$ regret against strategic adversaries. When playing zero-sum games with Accurate Multiplicative Weights Update (AMWU), a special case of AFTRL, we achieve \emph{last round convergence} to the Nash Equilibrium. We also provide numerical experiments to further support our theoretical results. In particular, we demonstrate that our methods achieve significantly better regret bounds and rate of last round convergence, compared to the state of the art (e.g., Multiplicative Weights Update (MWU) and its optimistic counterpart, OMWU).
On the Planning Abilities of Large Language Models (A Critical Investigation with a Proposed Benchmark)
Venue: arXiv cs.AI 2023
Year: 2023

Intrigued by the claims of emergent reasoning capabilities in LLMs trained on general web corpora, in this paper, we set out to investigate their planning capabilities. We aim to evaluate (1) how good LLMs are by themselves in generating and validating simple plans in commonsense planning tasks (of the type that humans are generally quite good at) and (2) how good LLMs are in being a source of heuristic guidance for other agents--either AI planners or human planners--in their planning tasks. To investigate these questions in a systematic rather than anecdotal manner, we start by developing a benchmark suite based on the kinds of domains employed in the International Planning Competition. On this benchmark, we evaluate LLMs in three modes: autonomous, heuristic and human-in-the-loop. Our results show that LLM's ability to autonomously generate executable plans is quite meager, averaging only about 3% success rate. The heuristic and human-in-the-loop modes show slightly more promise. In addition to these results, we also make our benchmark and evaluation tools available to support investigations by research community.
DeFi and NFTs Hinder Blockchain Scalability
Venue: arXiv cs.CR 2023
Year: 2023

Many classical blockchains are known to have an embarrassingly low transaction throughput, down to Bitcoin's notorious seven transactions per second limit.Various proposals and implementations for increasing throughput emerged in the first decade of blockchain research. But how much concurrency is possible? In their early days, blockchains were mostly used for simple transfers from user to user. More recently, however, decentralized finance (DeFi) and NFT marketplaces have completely changed what is happening on blockchains. Both are built using smart contracts and have gained significant popularity. Transactions on DeFi and NFT marketplaces often interact with the same smart contracts. We believe this development has transformed blockchain usage. In our work, we perform a historical analysis of Ethereum's transaction graph. We study how much interaction between transactions there was historically and how much there is now. We find that the rise of DeFi and NFT marketplaces has led to an increase in "centralization" in the transaction graph. More transactions are now interconnected: currently there are around 200 transactions per block with 4000 interdependencies between them. We further find that the parallelizability of Ethereum's current interconnected transaction workload is limited. A speedup exceeding a factor of five is currently unrealistic.
Language Model Analysis for Ontology Subsumption Inference
Venue: arXiv cs.CL 2023
Year: 2023

Investigating whether pre-trained language models (LMs) can function as knowledge bases (KBs) has raised wide research interests recently. However, existing works focus on simple, triple-based, relational KBs, but omit more sophisticated, logic-based, conceptualised KBs such as OWL ontologies. To investigate an LM's knowledge of ontologies, we propose OntoLAMA, a set of inference-based probing tasks and datasets from ontology subsumption axioms involving both atomic and complex concepts. We conduct extensive experiments on ontologies of different domains and scales, and our results demonstrate that LMs encode relatively less background knowledge of Subsumption Inference (SI) than traditional Natural Language Inference (NLI) but can improve on SI significantly when a small number of samples are given. We will open-source our code and datasets.
Transaction Fee Mining and Mechanism Design
Venue: arXiv cs.GT 2023
Year: 2023

Transaction fees represent a major incentive in many blockchain systems as a way to incentivize processing transactions. Unfortunately, they also introduce an enormous amount of incentive asymmetry compared to alternatives like fixed block rewards. We analyze some of the incentive compatibility issues that arise from transaction fees, which relate to the bids that users submit, the allocation rules that miners use to choose which transactions to include, and where they choose to mine in the context of longest-chain consensus. We start by surveying a variety of mining attacks including undercutting, fee sniping, and fee-optimized selfish mining. Then, we move to analyzing mechanistic notions of user incentive compatibility, myopic miner incentive compatibility, and off-chain-agreement-proofness, as well as why they are provably incompatible in their full form. Then, we discuss weaker notions of nearly and $γ$-weak incentive compatibility, and how all of these forms of incentive compatibility hold or fail in the trustless auctioneer setup of blockchains, examining classical mechanisms as well as more recent ones such as Ethereum's EIP-1559 mechanism and \cite{chung}'s burning second-price auction. Throughout, we generalize and interrelate existing notions, provide new unifying perspectives and intuitions on analysis, and discuss both specific and overarching open problems for future work.
Insights on the Next Generation WLAN: High Experiences (HEX)
Venue: arXiv cs.NI 2023
Year: 2023

Wireless local area network (WLAN) witnesses a very fast growth in the past 20 years by taking the maximum throughput as the key technical objective. However, the quality of experience (QoE) is the most important concern of wireless network users. In this article, we point out that poor QoE is the most challenging problem of the current WLAN, and further analyze the key technical problems that cause the poor QoE of WLAN, including fully distributed networking architecture, chaotic random access, awkward ``high capability'', coarse-grained QoS architecture, ubiquitous and complicated interference, ``no place'' for artificial intelligence (AI), and heavy burden of standard evolving. To the best of our knowledge, this is the first work to point out that poor QoE is the most challenging problem of the current WLAN, and the first work to systematically analyze the technical problems that cause the poor QoE of WLAN. We highly suggest that achieving high experiences (HEX) be the key objective of the next generation WLAN.
DiffFashion: Reference-based Fashion Design with Structure-aware Transfer by Diffusion Models
Venue: arXiv cs.CV 2023
Year: 2023

Image-based fashion design with AI techniques has attracted increasing attention in recent years. We focus on a new fashion design task, where we aim to transfer a reference appearance image onto a clothing image while preserving the structure of the clothing image. It is a challenging task since there are no reference images available for the newly designed output fashion images. Although diffusion-based image translation or neural style transfer (NST) has enabled flexible style transfer, it is often difficult to maintain the original structure of the image realistically during the reverse diffusion, especially when the referenced appearance image greatly differs from the common clothing appearance. To tackle this issue, we present a novel diffusion model-based unsupervised structure-aware transfer method to semantically generate new clothes from a given clothing image and a reference appearance image. In specific, we decouple the foreground clothing with automatically generated semantic masks by conditioned labels. And the mask is further used as guidance in the denoising process to preserve the structure information. Moreover, we use the pre-trained vision Transformer (ViT) for both appearance and structure guidance. Our experimental results show that the proposed method outperforms state-of-the-art baseline models, generating more realistic images in the fashion design task. Code and demo can be found at https://github.com/Rem105-210/DiffFashion.
The Role of Semantic Parsing in Understanding Procedural Text
Venue: arXiv cs.CL 2023
Year: 2023

In this paper, we investigate whether symbolic semantic representations, extracted from deep semantic parsers, can help reasoning over the states of involved entities in a procedural text. We consider a deep semantic parser~(TRIPS) and semantic role labeling as two sources of semantic parsing knowledge. First, we propose PROPOLIS, a symbolic parsing-based procedural reasoning framework. Second, we integrate semantic parsing information into state-of-the-art neural models to conduct procedural reasoning. Our experiments indicate that explicitly incorporating such semantic knowledge improves procedural understanding. This paper presents new metrics for evaluating procedural reasoning tasks that clarify the challenges and identify differences among neural, symbolic, and integrated models.
SEAM: Searching Transferable Mixed-Precision Quantization Policy through Large Margin Regularization
Venue: arXiv cs.CV 2023
Year: 2023

Mixed-precision quantization (MPQ) suffers from the time-consuming process of searching the optimal bit-width allocation i.e., the policy) for each layer, especially when using large-scale datasets such as ISLVRC-2012. This limits the practicality of MPQ in real-world deployment scenarios. To address this issue, this paper proposes a novel method for efficiently searching for effective MPQ policies using a small proxy dataset instead of the large-scale dataset used for training the model. Deviating from the established norm of employing a consistent dataset for both model training and MPQ policy search stages, our approach, therefore, yields a substantial enhancement in the efficiency of MPQ exploration. Nonetheless, using discrepant datasets poses challenges in searching for a transferable MPQ policy. Driven by the observation that quantization noise of sub-optimal policy exerts a detrimental influence on the discriminability of feature representations -- manifesting as diminished class margins and ambiguous decision boundaries -- our method aims to identify policies that uphold the discriminative nature of feature representations, i.e., intra-class compactness and inter-class separation. This general and dataset-independent property makes us search for the MPQ policy over a rather small-scale proxy dataset and then the policy can be directly used to quantize the model trained on a large-scale dataset. Our method offers several advantages, including high proxy data utilization, no excessive hyper-parameter tuning, and high searching efficiency. We search high-quality MPQ policies with the proxy dataset that has only 4% of the data scale compared to the large-scale target dataset, achieving the same accuracy as searching directly on the latter, improving MPQ searching efficiency by up to 300 times.
Scheduling Coflows for Minimizing the Makespan in Identical Parallel Networks
Venue: arXiv cs.DS 2023
Year: 2023

With the rapid advancement of technology, parallel computing applications have become increasingly popular and are commonly executed in large data centers. These applications involve two phases: computation and communication, which are executed repeatedly to complete the work. However, due to the ever-increasing demand for computing power, large data centers are struggling to meet the massive communication demands. To address this problem, coflow has been proposed as a networking abstraction that captures communication patterns in data-parallel computing frameworks. This paper focuses on the coflow scheduling problem in identical parallel networks, where the primary objective is to minimize the makespan, which is the maximum completion time of coflows. It is considered one of the most significant $\mathcal{NP}$-hard problems in large data centers. In this paper, we consider two problems: flow-level scheduling and coflow-level scheduling. In the flow-level scheduling problem, distinct flows can be transferred through different network cores, whereas in the coflow-level scheduling problem, all flows must be transferred through the same network core. To address the flow-level scheduling problem, this paper proposes two algorithms: a $(3-\tfrac{2}{m})$-approximation algorithm and a $(\tfrac{8}{3}-\tfrac{2}{3m})$-approximation algorithm, where $m$ represents the number of network cores. For the coflow-level scheduling problem, this paper proposes a $(2m)$-approximation algorithm. Finally, we conduct simulations on our proposed algorithm and Weaver's algorithm, as presented in Huang \textit{et al.} (2020) in the 2020 IEEE International Parallel and Distributed Processing Symposium (IPDPS). We also validate the effectiveness of the proposed algorithms on heterogeneous parallel networks.
Learning gain differences between ChatGPT and human tutor generated algebra hints
Venue: arXiv cs.CY 2023
Year: 2023

Large Language Models (LLMs), such as ChatGPT, are quickly advancing AI to the frontiers of practical consumer use and leading industries to re-evaluate how they allocate resources for content production. Authoring of open educational resources and hint content within adaptive tutoring systems is labor intensive. Should LLMs like ChatGPT produce educational content on par with human-authored content, the implications would be significant for further scaling of computer tutoring system approaches. In this paper, we conduct the first learning gain evaluation of ChatGPT by comparing the efficacy of its hints with hints authored by human tutors with 77 participants across two algebra topic areas, Elementary Algebra and Intermediate Algebra. We find that 70% of hints produced by ChatGPT passed our manual quality checks and that both human and ChatGPT conditions produced positive learning gains. However, gains were only statistically significant for human tutor created hints. Learning gains from human-created hints were substantially and statistically significantly higher than ChatGPT hints in both topic areas, though ChatGPT participants in the Intermediate Algebra experiment were near ceiling and not even with the control at pre-test. We discuss the limitations of our study and suggest several future directions for the field. Problem and hint content used in the experiment is provided for replicability.
Distributed Symmetry Breaking on Power Graphs via Sparsification
Venue: arXiv cs.DS 2023
Year: 2023

In this paper, we present efficient distributed algorithms for classical symmetry breaking problems, maximal independent sets (MIS) and ruling sets, in power graphs. We work in the standard CONGEST model of distributed message passing, where the communication network is abstracted as a graph $G$. Typically, the problem instance in CONGEST is identical to the communication network $G$, that is, we perform the symmetry breaking in $G$. In this work, we consider a setting where the problem instance corresponds to a power graph $G^k$, where each node of the communication network $G$ is connected to all of its $k$-hop neighbors. Our main contribution is a deterministic polylogarithmic time algorithm for computing $k$-ruling sets of $G^k$, which (for $k>1$) improves exponentially on the current state-of-the-art runtimes. The main technical ingredient for this result is a deterministic sparsification procedure which may be of independent interest. On top of being a natural family of problems, ruling sets (in power graphs) are well-motivated through their applications in the powerful shattering framework [BEPS JACM'16, Ghaffari SODA'19] (and others). We present randomized algorithms for computing maximal independent sets and ruling sets of $G^k$ in essentially the same time as they can be computed in $G$. We also revisit the shattering algorithm for MIS [BEPS JACM'16] and present different approaches for the post-shattering phase. Our solutions are algorithmically and analytically simpler (also in the LOCAL model) than existing solutions and obtain the same runtime as [Ghaffari SODA'16].
Take a Prior from Other Tasks for Severe Blur Removal
Venue: arXiv cs.CV 2023
Year: 2023

Recovering clear structures from severely blurry inputs is a challenging problem due to the large movements between the camera and the scene. Although some works apply segmentation maps on human face images for deblurring, they cannot handle natural scenes because objects and degradation are more complex, and inaccurate segmentation maps lead to a loss of details. For general scene deblurring, the feature space of the blurry image and corresponding sharp image under the high-level vision task is closer, which inspires us to rely on other tasks (e.g. classification) to learn a comprehensive prior in severe blur removal cases. We propose a cross-level feature learning strategy based on knowledge distillation to learn the priors, which include global contexts and sharp local structures for recovering potential details. In addition, we propose a semantic prior embedding layer with multi-level aggregation and semantic attention transformation to integrate the priors effectively. We introduce the proposed priors to various models, including the UNet and other mainstream deblurring baselines, leading to better performance on severe blur removal. Extensive experiments on natural image deblurring benchmarks and real-world images, such as GoPro and RealBlur datasets, demonstrate our method's effectiveness and generalization ability.
Few-shot learning approaches for classifying low resource domain specific software requirements
Venue: arXiv cs.CL 2023
Year: 2023

With the advent of strong pre-trained natural language processing models like BERT, DeBERTa, MiniLM, T5, the data requirement for industries to fine-tune these models to their niche use cases has drastically reduced (typically to a few hundred annotated samples for achieving a reasonable performance). However, the availability of even a few hundred annotated samples may not always be guaranteed in low resource domains like automotive, which often limits the usage of such deep learning models in an industrial setting. In this paper we aim to address the challenge of fine-tuning such pre-trained models with only a few annotated samples, also known as Few-shot learning. Our experiments focus on evaluating the performance of a diverse set of algorithms and methodologies to achieve the task of classifying BOSCH automotive domain textual software requirements into 3 categories, while utilizing only 15 annotated samples per category for fine-tuning. We find that while SciBERT and DeBERTa based models tend to be the most accurate at 15 training samples, their performance improvement scales minimally as the number of annotated samples is increased to 50 in comparison to Siamese and T5 based models.
SCONNA: A Stochastic Computing Based Optical Accelerator for Ultra-Fast, Energy-Efficient Inference of Integer-Quantized CNNs
Venue: arXiv cs.AR 2023
Year: 2023

The acceleration of a CNN inference task uses convolution operations that are typically transformed into vector-dot-product (VDP) operations. Several photonic microring resonators (MRRs) based hardware architectures have been proposed to accelerate integer-quantized CNNs with remarkably higher throughput and energy efficiency compared to their electronic counterparts. However, the existing photonic MRR-based analog accelerators exhibit a very strong trade-off between the achievable input/weight precision and VDP operation size, which severely restricts their achievable VDP operation size for the quantized input/weight precision of 4 bits and higher. The restricted VDP operation size ultimately suppresses computing throughput to severely diminish the achievable performance benefits. To address this shortcoming, we for the first time present a merger of stochastic computing and MRR-based CNN accelerators. To leverage the innate precision flexibility of stochastic computing, we invent an MRR-based optical stochastic multiplier (OSM). We employ multiple OSMs in a cascaded manner using dense wavelength division multiplexing, to forge a novel Stochastic Computing based Optical Neural Network Accelerator (SCONNA). SCONNA achieves significantly high throughput and energy efficiency for accelerating inferences of high-precision quantized CNNs. Our evaluation for the inference of four modern CNNs at 8-bit input/weight precision indicates that SCONNA provides improvements of up to 66.5x, 90x, and 91x in frames-per-second (FPS), FPS/W and FPS/W/mm2, respectively, on average over two photonic MRR-based analog CNN accelerators from prior work, with Top-1 accuracy drop of only up to 0.4% for large CNNs and up to 1.5% for small CNNs. We developed a transaction-level, event-driven python-based simulator for the evaluation of SCONNA and other accelerators (https://github.com/uky-UCAT/SC_ONN_SIM.git).