When designing a message transmission system, from the point of view of making sure that the information transmitted is as fresh as possible, two rules of thumb seem reasonable: use small buffers and adopt a last-in-first-out policy. In this paper, we measure freshness of information using the recently adopted "age of information" performance measure. Considering it as a stochastic process operating in a stationary regime, we compute not just the first moment but the whole marginal distribution of the age of information (something important in applications) for two well-performing systems. In neither case do we allow for preemption of the message being processed because this may be difficult to implement in practice. We assume that the arrival process is Poisson and that the messages have independent sizes (service times) with common distribution. We use Palm and Markov-renewal theory to derive explicit results for Laplace transforms which, in many cases can be inverted analytically. We discuss how well the systems we analyze performs and examine how close to optimality they are. In particular, we answer an open question that was raised in [9] regarding the optimality of the system denoted as P2.
相關內容
In decentralised autonomous systems it is the interactions between individual agents which govern the collective behaviours of the system. These local-level interactions are themselves often governed by an underlying network structure. These networks are particularly important for collective learning and decision-making whereby agents must gather evidence from their environment and propagate this information to other agents in the system. Models for collective behaviours may often rely upon the assumption of total connectivity between agents to provide effective information sharing within the system, but this assumption may be ill-advised. In this paper we investigate the impact that the underlying network has on performance in the context of collective learning. Through simulations we study small-world networks with varying levels of connectivity and randomness and conclude that totally-connected networks result in higher average error when compared to networks with less connectivity. Furthermore, we show that networks of high regularity outperform networks with increasing levels of random connectivity.
This paper investigates a novel offline change-point detection problem from an information-theoretic perspective. In contrast to most related works, we assume that the knowledge of the underlying pre- and post-change distributions are not known and can only be learned from the training sequences which are available. We further require the probability of the \emph{estimation error} to decay either exponentially or sub-exponentially fast (corresponding respectively to the large and moderate deviations regimes in information theory parlance). Based on the training sequences as well as the test sequence consisting of a single change-point, we design a change-point estimator and further show that this estimator is optimal by establishing matching (strong) converses. This leads to a full characterization of the optimal confidence width (i.e., half the width of the confidence interval within which the true change-point is located at with high probability) as a function of the undetected error, under both the large and moderate deviations regimes.
The Bayesian persuasion paradigm of strategic communication models interaction between a privately-informed agent, called the sender, and an ignorant but rational agent, called the receiver. The goal is typically to design a (near-)optimal communication (or signaling) scheme for the sender. It enables the sender to disclose information to the receiver in a way as to incentivize her to take an action that is preferred by the sender. Finding the optimal signaling scheme is known to be computationally difficult in general. This hardness is further exacerbated when there is also a constraint on the size of the message space, leading to NP-hardness of approximating the optimal sender utility within any constant factor. In this paper, we show that in several natural and prominent cases the optimization problem is tractable even when the message space is limited. In particular, we study signaling under a symmetry or an independence assumption on the distribution of utility values for the actions. For symmetric distributions, we provide a novel characterization of the optimal signaling scheme. It results in a polynomial-time algorithm to compute an optimal scheme for many compactly represented symmetric distributions. In the independent case, we design a constant-factor approximation algorithm, which stands in marked contrast to the hardness of approximation in the general case.
The demand for on-device document recognition systems increases in conjunction with the emergence of more strict privacy and security requirements. In such systems, there is no data transfer from the end device to a third-party information processing servers. The response time is vital to the user experience of on-device document recognition. Combined with the unavailability of discrete GPUs, powerful CPUs, or a large RAM capacity on consumer-grade end devices such as smartphones, the time limitations put significant constraints on the computational complexity of the applied algorithms for on-device execution. In this work, we consider document location in an image without prior knowledge of the document content or its internal structure. In accordance with the published works, at least 5 systems offer solutions for on-device document location. All these systems use a location method which can be considered Hough-based. The precision of such systems seems to be lower than that of the state-of-the-art solutions which were not designed to account for the limited computational resources. We propose an advanced Hough-based method. In contrast with other approaches, it accounts for the geometric invariants of the central projection model and combines both edge and color features for document boundary detection. The proposed method allowed for the second best result for SmartDoc dataset in terms of precision, surpassed by U-net like neural network. When evaluated on a more challenging MIDV-500 dataset, the proposed algorithm guaranteed the best precision compared to published methods. Our method retained the applicability to on-device computations.
We prove an estimate of total (viscous plus modelled turbulent) energy dissipation in general eddy viscosity models for shear flows. For general eddy viscosity models, we show that the ratio of the near wall average viscosity to the effective global viscosity is the key parameter. This result is then applied to the 1-equation, URANS model of turbulence for which this ratio depends on the specification of the turbulence length scale. The model, which was derived by Prandtl in 1945, is a component of a 2-equation model derived by Kolmogorov in 1942 and is the core of many unsteady, Reynolds averaged models for prediction of turbulent flows. Away from walls, interpreting an early suggestion of Prandtl, we set \begin{equation*} l=\sqrt{2}k^{+1/2}\tau, \hspace{50mm} \end{equation*} where $\tau =$ selected time scale. In the near wall region analysis suggests replacing the traditional $l=0.41d$ ($d=$ wall normal distance) with $l=0.41d\sqrt{d/L}$ giving, e.g., \begin{equation*} l=\min \left\{ \sqrt{2}k{}^{+1/2}\tau ,\text{ }0.41d\sqrt{\frac{d}{L}} \right\} . \hspace{50mm} \end{equation*} This $l(\cdot )$ results in a simpler model with correct near wall asymptotics. Its energy dissipation rate scales no larger than the physically correct $O(U^{3}/L)$, balancing energy input with energy dissipation.
In this paper, we study the problem of minimizing the age of information when a source can transmit status updates over two heterogeneous channels. Our work is motivated by recent developments in 5G mmWave technology, where transmissions may occur over an unreliable but fast (e.g., mmWave) channel or a slow reliable (e.g., sub-6GHz) channel. The unreliable channel is modeled as a time-correlated Gilbert-Elliot channel, where information can be transmitted at a high rate when the channel is in the ''ON'' state. The reliable channel provides a deterministic but lower data rate. The scheduling strategy determines the channel to be used for transmission with the aim to minimize the time-average age of information (AoI). The optimal scheduling problem is formulated as a Markov Decision Process (MDP), which in our setting poses some significant challenges because e.g., supermodularity does not hold for part of the state space. We show that there exists a multi-dimensional threshold-based scheduling policy that is optimal for minimizing the age. A low-complexity bisection algorithm is further devised to compute the optimal thresholds. Numerical simulations are provided to compare different scheduling policies.
In this paper, we are interested in nonparametric kernel estimation of a generalized regression function, including conditional cumulative distribution and conditional quantile functions, based on an incomplete sample $(X_t, Y_t, \zeta_t)_{t\in \mathbb{ R}^+}$ copies of a continuous-time stationary ergodic process $(X, Y, \zeta)$. The predictor $X$ is valued in some infinite-dimensional space, whereas the real-valued process $Y$ is observed when $\zeta= 1$ and missing whenever $\zeta = 0$. Pointwise and uniform consistency (with rates) of these estimators as well as a central limit theorem are established. Conditional bias and asymptotic quadratic error are also provided. Asymptotic and bootstrap-based confidence intervals for the generalized regression function are also discussed. A first simulation study is performed to compare the discrete-time to the continuous-time estimations. A second simulation is also conducted to discuss the selection of the optimal sampling mesh in the continuous-time case. Finally, it is worth noting that our results are stated under ergodic assumption without assuming any classical mixing conditions.
This paper studies a memoryless state-dependent multiple access channel (MAC) where two transmitters wish to convey a message to a receiver under the assumption of causal and imperfect channel state information at transmitters (CSIT) and imperfect channel state information at receiver (CSIR). In order to emphasize the limitation of transmitter cooperation between physically distributed nodes, we focus on the so-called distributed CSIT assumption, i.e. where each transmitter has its individual channel knowledge, while the message can be assumed to be partially or entirely shared a priori between transmitters by exploiting some on-board memory. Under this setup, the first part of the paper characterizes the common message capacity of the channel at hand for arbitrary CSIT and CSIR structure. The optimal scheme builds on Shannon strategies, i.e. optimal codes are constructed by letting the channel inputs be a function of current CSIT only. For a special case when CSIT is a deterministic function of CSIR, the considered scheme also achieves the capacity region of a common message and two private messages. The second part addresses an important instance of the previous general result in a context of a cooperative multi-antenna Gaussian channel under i.i.d. fading operating in frequency-division duplex mode, such that CSIT is acquired via an explicit feedback of perfect CSIR. The capacity of the channel at hand is achieved by distributed linear precoding applied to Gaussian codes. Surprisingly, we demonstrate that it is suboptimal to send a number of data streams bounded by the number of transmit antennas as typically considered in a centralized CSIT setup. Finally, numerical examples are provided to evaluate the sum capacity of the binary MAC with binary states as well as the Gaussian MAC with i.i.d. fading.
Consider a message processing system whose objective is to produce the most current information as measured by the quantity known as "age of information". We have argued in previous papers that if we are allowed to design the message processing policy ad libitum, we should keep a small buffer and operate according to a LIFO policy. In this small note we provide an analysis for the AoI of the P_m system which uses a buffer of size m, a single server, operating without service preemption and in a LIFO manner for stored messages. Analytical expressions for the mean (or even distribution) of the AoI in steady-state are possible but with the aid computer algebra. We explain the the analysis for m=3.
Human conversation is a complex mechanism with subtle nuances. It is hence an ambitious goal to develop artificial intelligence agents that can participate fluently in a conversation. While we are still far from achieving this goal, recent progress in visual question answering, image captioning, and visual question generation shows that dialog systems may be realizable in the not too distant future. To this end, a novel dataset was introduced recently and encouraging results were demonstrated, particularly for question answering. In this paper, we demonstrate a simple symmetric discriminative baseline, that can be applied to both predicting an answer as well as predicting a question. We show that this method performs on par with the state of the art, even memory net based methods. In addition, for the first time on the visual dialog dataset, we assess the performance of a system asking questions, and demonstrate how visual dialog can be generated from discriminative question generation and question answering.
小貼士
登錄享
注冊地址： 北京市海淀區羊坊店路18號2幢3層301-191