Emerging V2X technology enables vehicles to exchange messages with each other (V2V) and with signaling infrastructure (I2V) on the roadways. Information propagation in transportation networks is highly influenced by both vehicle mobility and wireless communication. As for vehicle mobility, realistic traffic flow changes with time, exhibiting sharp time-triggered transitions, due to external factors such as traffic lights. Thus, mobility process is temporally heterogeneous and not smooth, which fundamentally alters the dynamics of V2X (V2V and I2V together) message propagation in a complex manner. As for wireless communication, communication heterogeneity is an integral component of V2X systems - different types of vehicles may have different communication capabilities, and V2V and I2V communications coexist. We propose a mathematical framework, based on a continuous-time Markov chain (CTMC), for characterizing the spatio-temporal spread of V2X information (1) when the traffic flow exhibits sharp time-triggered transitions and (2) when there exists communication heterogeneity comprising of different V2V commutation capabilities, different wireless communication conditions, and both V2V and I2V. We prove that the state evolutions under the CTMC model converge to a set of differential equations in the asymptotic limit of a large number of vehicles, enabling computations that gracefully scale with increase in network size and the number of vehicles. Our framework can accommodate arbitrary traffic synchronization patterns corresponding for example to incorporate the presence of an arbitrary number of traffic signals. Furthermore, numerical computations using this mathematical framework answer several questions that influence the practice of V2X network design and security.

Information propagation in V2V-enabled transportation networks is highly influenced by both vehicle mobility and wireless communication. The mobility patterns and communication conditions are not only heterogeneous, but also vary both temporally and spatially. In particular, realistic traffic flow changes with time, exhibiting sharp time-triggered transitions, due to external factors such as traffic lights, unpredictable disruptions (e.g., accidents), and planned disruptions (e.g., road-block). More specifically, traffic signals cause traffic synchronization, due to vehicles stopping during the red phase, and starting almost simultaneously during the green phase, which fundamentally alters the dynamics of V2V message propagation in a complex manner. In this paper, we propose a mathematical framework, starting from a continuous-time Markov chain, that characterizes the fraction of vehicles that have received a message over time and space in an arbitrary road network even when the traffic flow exhibits sharp time-triggered transitions. Our framework can accommodate arbitrary traffic synchronization patterns corresponding for example to the presence of an arbitrary number of traffic signals. The stochastic model for V2V message flow converges to a set of differential equations as the number of vehicles increases. The analytical characterization lends itself to a fast computation regardless of the number of vehicles and traffic synchronization patterns, while vehicular network simulators can only realistically simulate small-scale transportation networks. We find that V2V simulations of a statistical model with traffic synchronization and simulation of communications applied on a synthetic traffic trace well match our model solution.

Studies on the propagation of malware in mobile networks have revealed that the spread of malware can be highly inhomogeneous. Platform diversity, contact list utilization by the malware, clustering in the network structure, etc., can also lead to differing spreading rates. In this paper, a general formal framework is proposed for leveraging such heterogeneity to derive optimal patching policies that attain the minimum aggregate cost due to the spread of malware and the surcharge of patching. Using Pontryagin's Maximum Principle for a stratified epidemic model, it is analytically proven that in the mean-field deterministic regime, optimal patch disseminations are simple single-threshold policies. These policies are amenable to implementation and can serve as benchmarks for policies that have less knowledge of the network. Through numerical simulations, the behavior of optimal patching policies is investigated in sample topologies, and their advantages are demonstrated.

The openness of the Android operating system increased the number of applications developed, but it also introduced a new propagation vector for mobile malware. We model the propagation of mobile malware using epidemiology theory and study the problem as a function of the underlying mobility models. We define the optimal approach to heal an infected system with the help of a set of static healers that distribute patches, as the T-COVER problem and show that it is NP-HARD. We then propose two families of healer protocols that trade-off time recovery and energy consumed by sending patches. The first one uses randomization to ensure a small recovery time but may result in healers sending more patches than needed. The second one uses system feedback to optimize energy consumed by sending patches, but it may result in a larger recovery time. We show through simulations using the NS-3 simulator that despite lacking knowledge of the future, our protocols obtain a recovery time within a 10x bound of the oracle solution that knows the arrival time of the infected nodes.

In this work, we investigate the use of epidemic routing in energy constrained Delay Tolerant Networks (DTNs). In DTNs, connected paths between source and destination rarely materialize due to the mobility and sparse density of nodes. Epidemic routing is well-suited for these environments due to its simplicity and fully distributed implementation. In epidemic routing, messages are relayed by intermediate nodes at contact opportunities, i.e., when pairs of nodes come within transmission range. Each node needs to decide whether to forward its message upon contact with a new node based on its residual energy level and the age of that message.

Denial-of-service (DoS) attacks are considered within the province of a shared channel model in which attack rates may be large but are bounded and client request rates vary within fixed bounds. In this setting, it is shown that clients can adapt effectively to an attack by increasing their request rate based on timeout windows to estimate attack rates. The server will be able to process client requests with high probability while pruning out most of the attack by selective random sampling. The protocol introduced here, called Adaptive Selective Verification (ASV), is shown to use bandwidth efficiently and does not require any server state or assumptions about network congestion. The main results of the paper are a formulation of optimal performance and a proof that ASV is optimal.

We consider Denial of Service (DoS) attacks within the province of a shared channel model in which attack rates may be large but are bounded and client request rates vary within fixed bounds. In this setting it is shown that the clients can respond effectively to an attack by using bandwidth as a payment scheme and time-out windows to adaptively boost request rates. The server will be able to process client requests with high probability while pruning out most of the attack by selective random sampling. Our protocol, which we call Adaptive Selective Verification (ASV) is shown to be efficient in terms of bandwidth consumption using both a theoretical model and network simulations. It differs from previously-investigated adaptive mechanisms for bandwidth-based payment by requiring very limited state on the server.

For original article see ibid., vol.35, no.3, p.558-68, May 1989. The authors thank Jinwen Ma, Jianwei Wu, and Qiansheng Cheng for pointing out the overcount in the original proof.

A geometrically random network of sensors is obtained by modeling sensors as random points in the unit disc equipped with a local sensing capability and the ability to communicate with other sensors in their vicinity. Node extinctions in the network representing the finite battery lifetimes of the sensors are modeled as a sequence of independent random variables governed by a common probability distribution parametrized by the sensing and communication radii of the sensor nodes. Following its establishment, the devolution of the network with time is characterized by the appearance first of isolated nodes, then the growth of sensory lacunae or dead spots in the sensor field, and, eventually, a breakdown in connectivity between survivors. It is shown that these phenomena occur very sharply in time, these phase transitions occurring at times characteristic of the underlying probability law governing lifetimes. More precisely, it is shown that as the number of sensors grows there exists a critical point in time determined solely by the lifetime distribution at which the number of emergent lacunae of a given size is asymptotically Poisson

As batteries fail in wireless sensor networks there is an inevitable devolution of the network characterised by a breakdown in connectivity between the surviving nodes of the network. A sharp limit theorem characterising the time at which this phenomena makes an appearance is derived.

We call a learning environment partially blind when there is an admixture of supervised and unsupervised (or blind) learning. Such situations typically arise in practice when supervised training data labelled by a teacher are scarce or expensive and are supplemented by inexpensive unlabelled (or blind) data available in relative profusion. Vapnik-Cervonenkis theory can be deployed in such settings to quantify the relative worth of supervision (and the lack thereof) in learning. We illustrate the nature of the trade-offs possible in a simple setting of hyperplane decision functions and make explicit the role of dimensionality and side-information in these trade-offs in the context of d-variate Gaussian mixtures.

We derive the maximum a posteriori probability (MAP) receiver for orthogonal frequency-division multiplexed signals in a fading channel. As the complexity of the MAP receiver is high, we obtain a low-complexity, suboptimal receiver and evaluate its performance.

Pilot symbol assisted modulation is a promising scheme to mitigate the effect of fading in a wireless channel. Analytical results for the performance of this scheme are available. Although the use of diversity is known to improve the performance of receivers used in fading channels, pilot symbol assisted diversity reception has not been studied. In this paper, we derive an exact probability of error expression for such a receiver as a function of the channel estimation error variance and the number of diversity channels. An upper bound for the probability of error which illustrates the advantage of using diversity, is also obtained. A numerical example is provided.

Interest in OFDM has renewed with the standardization of OFDM for digital audio broadcasting in Europe. In this paper, we consider an adaptive, diversity receiver for OFDM signals in a Rayleigh fading channel. The diversity receiver has L branches with each branch receiving the signal from L independently fading diversity channels. We model the fading process as a vector auto-regressive process and use the Kalman filter to obtain the MMSE optimum channel estimates for each branch. The channel estimates and the signals are combined using the maximal ratio combining rule to obtain the decision variables. We analyze the performance of this receiver and provide a numerical example to highlight the advantage of using diversity.

Classical and recent results in statistical pattern recognition and learning theory are reviewed in a two-class pattern classification setting. This basic model best illustrates intuition and analysis techniques while still containing the essential features and serving as a prototype for many applications. Topics discussed include nearest neighbor, kernel, and histogram methods, Vapnik-Chervonenkis theory, and neural networks. The presentation and the large (though nonexhaustive) list of references is geared to provide a useful overview of this field for both specialists and nonspecialists.

Harmonic update is a randomized on-line algorithm which, given a random m-set of vertices $U(m)\subseteq\{-1,1\}^n$ in the n-dimensional cube, generates a random vertex $\bw\in\{-1,1\}^n$ as a putative solution to the system of linear inequalities: $\sum_{i=1}^n w_i u_i\geq0$ for each $\bu\in U(m)$. Using tools from large deviation multivariate normal approximation and Poisson approximation, we show that $\sqrt{n}\big/\!\sqrt{\log n}$ is a threshold function for the property that the vertex $\bw$ generated by harmonic update has positive inner product with each vertex in $U(m)$. More explicitly, let $P(n,m)$ denote the probability that $\sum_{i=1}^n w_i u_i\geq 0$ for each $\bu\in U(m)$. Then, as $n\to\infty$, $P(n,m)\to 0$ or 1 according to whether $m=m_n$ varies with n such that $m\gg\sqrt{n}\big/\!\sqrt{\log n}$ or $m\ll\sqrt{n}\big/\!\sqrt{\log n}$, respectively. The analysis also exposes the fine structure of the threshold function.

Using a mathematical model for an RNA molecule as a family of disjoint edge-colored interior planar graphs on a circle, we determine the expected number of secondary RNA structures that can form under various assumptions on the type and number of ribonucleotide bonds.

The majority rule algorithm for learning binary weights for a perceptron is analysed under the uniform distribution on inputs. It is shown that even though the algorithm is demonstrably inconsistent on random samples for very small sample sizes, it nevertheless exhibits a curious and abrupt asymptotic transition to consistency at moderate sample sizes. Particular consequences are that the algorithm PAC-learns majority functions in linear time from small samples and that, while the general variant of binary integer programming embodied here is NP-complete, almost all instances of the problem are tractable given a sufficient number of inequalities to be satisfies

Article Free Access Share on Learning from a mixture of labeled and unlabeled examples with parametric side information Authors: Joel Ratsaby Department of Electrical Engineering, Technion, Israel and Department of Electrical Engineering, University of Pennsylvania, Philadelphia, PA Department of Electrical Engineering, Technion, Israel and Department of Electrical Engineering, University of Pennsylvania, Philadelphia, PAView Profile , Santosh S. Venkatesh Department of Electrical Engineering, University of Pennsylvania, Philadelphia, PA Department of Electrical Engineering, University of Pennsylvania, Philadelphia, PAView Profile Authors Info & Claims COLT '95: Proceedings of the eighth annual conference on Computational learning theoryJuly 1995 Pages 412–417https://doi.org/10.1145/225298.225348Online:05 July 1995Publication History 41citation532DownloadsMetricsTotal Citations41Total Downloads532Last 12 Months29Last 6 weeks3 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

Article Free Access Share on Criteria for specifying machine complexity in learning Authors: Changfeng Wang Department of Electrical Engineering, University of Pennsylvania, Philadelphia, PA Department of Electrical Engineering, University of Pennsylvania, Philadelphia, PASearch about this author , Santosh S. Venkatesh Department of Electrical Engineering, University of Pennsylvania, Philadelphia, PA Department of Electrical Engineering, University of Pennsylvania, Philadelphia, PAView Profile Authors Info & Claims COLT '95: Proceedings of the eighth annual conference on Computational learning theoryJuly 1995Pages 273–280https://doi.org/10.1145/225298.225331Published:05 July 1995Publication History 0citation259DownloadsMetricsTotal Citations0Total Downloads259Last 12 Months8Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

The finite-sample risk of the k-nearest-neighbor classifier is analyzed for a family of two-class problems in which patterns are randomly generated from smooth probability distributions in an n-dimensional Euclidean feature space. First, an exact integral expression for the m-sample risk is obtained for a k-nearest-neighbor classifier that uses a reference sample of m labeled feature vectors. Using a multidimensional application of Laplace's method of integration, this integral can be represented as an asymptotic expansion in negative rational powers of m. The leading terms of this asymptotic expansion elucidate the curse of dimensionality and other properties of the finite-sample risk.

This paper presents a rigorous characterization of how a general nonlinear learning machine generalizes during the training process when it is trained on a random sample using a gradient descent algorithm based on reduction of training error. It is shown, in particular, that best generalization performance occurs, in general, before the global minimum of the training error is achieved. The different roles played by the complexity of the machine class and the complexity of the specific machine in the class during learning are also precisely demarcated.

The finite sample performance of a nearest neighbor classifier is analyzed for a two-class pattern recognition problem. An exact integral expression is derived for the m-sample risk R/sub m/ given that a reference m-sample of labeled points is available to the classifier. The statistical setup assumes that the pattern classes arise in nature with fixed a priori probabilities and that points representing the classes are drawn from Euclidean n-space according to fixed class-conditional probability distributions. The sample is assumed to consist of m independently generated class-labeled points. For a family of smooth class-conditional distributions characterized by asymptotic expansions in general form, it is shown that the m-sample risk R/sub m/ has a complete asymptotic series expansion R/sub m//spl sim/R/sub /spl infin//+/spl Sigma//sub k=2//sup /spl infin//c/sub k/m/sup -k/n/ (m/spl rarr//spl infin/), where R/sub /spl infin// denotes the nearest neighbor risk in the infinite-sample limit and the coefficients c/sub k/ are distribution-dependent constants independent of the sample size m. The analysis thus provides further analytic validation of Bellman's curse of dimensionality. Numerical simulations corroborating the formal results are included, and extensions of the theory discussed. The analysis also contains a novel application of Laplace's asymptotic method of integration to a multidimensional integral where the integrand attains its maximum on a continuum of points.>

Article Free Access Share on On the average tractability of binary integer programming and the curious transition to perfect generalization in learning majority functions Authors: Shao C. Fang View Profile , Santosh S. Venkatesh View Profile Authors Info & Claims COLT '93: Proceedings of the sixth annual conference on Computational learning theoryAugust 1993 Pages 310–316https://doi.org/10.1145/168304.168360Published:01 August 1993Publication History 3citation189DownloadsMetricsTotal Citations3Total Downloads189Last 12 Months9Last 6 weeks6 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

Learning real weights for a McCulloch-Pitts neuron is equivalent to linear programming and can hence be done in polynomial time. Efficient local learning algorithms such as Perceptron Learning further guarantee convergence in finite time. The problem becomes considerably harder, however, when it is sought to learn binary weights; this is equivalent to integer programming which is known to be NP-complete. A family of probabilistic algorithms which learn binary weights for a McCulloch-Pitts neuron with inputs constrained to be binary is proposed here, the target functions being majority functions of a set literals. These algorithms have low computational demands and are essentially local in character. Rapid (average-case) quadratic rates of convergence for the algorithm are predicted analytically and confirmed through computer simulations when the number of examples is within capacity. It is also shown that, for the functions under consideration, Preceptron Learning converges rapidly (but to an, in general, non-binary solution weight vector).

Recurrent networks of polynomial threshold elements with random symmetric interactions are studied. Precise asymptotic estimates are derived for the expected number of fixed points as a function of the margin of stability. In particular, it is shown that there is a critical range of margins of stability (depending on the degree of polynomial interaction) such that the expected number of fixed points with margins below the critical range grows exponentially with the number of nodes in the network, while the expected number of fixed points with margins above the critical range decreases exponentially with the number of nodes in the network. The random energy model is also briefly examined, and links with higher-order neural networks and higher-order spin glass models are made explicit.>

The following coin tossing game is analyzed: a store of N fair coins is given and it is desired to achieve M heads in a round of tosses of the coins. To allow for unfavorable sequences of tails, restarts are permitted at any epoch in the game where, in any restart, all coins are returned to store and tosses are begun anew from tabula rasa. A restart strategy is a prescription that specifies when a restart should be made. It is desired to estimate the minimum expected duration of the game over all restart strategies, and to find an optimal strategy that minimizes the expected duration of the game. This simple coin tossing game, proposed by R.L. Rivest, has cryptographic roots and is linked to issues in the factoring of integers.>

The finite sample performance of a nearest neighbor classifier is analyzed for a two-class pattern recognition problem. An exact integral expression is derived for the m-sample risk Rm given that a reference m-sample of labeled points, drawn independently from Euclidean n-space according to a fixed probability distri bution, is available to the classifier. For a family of smooth distributions, it is shown that the m-sample risk Rm has a complete asymptotic expansion ******, where ** denotes the nearest neighbor risk in the infinite sample limit. Explicit definitions of the expansion coefficents are given in terms of the underlying distribution. As the convergence rate of **** dramatically slows down as n increases, this analysis provides an analytic validation of Bellman's curse of dimensionality. Numerical simulations corroborating the formal results are included. The rates of convergence for less restrictive families of distributions are also discussed.

The authors investigate the computing capabilities of formal McCulloch-Pitts neurons when errors are permitted in decisions. They assume that m decisions are to be made on a randomly specified m set of points in n space and that an error tolerance of epsilon m decision errors is allowed, with 0>

An attempt is made to mathematically codify the belief that fully interconnected neural networks continue to function efficiently in the presence of component damage. Component damage is introduced in a fully interconnected neural network model of n neurons by randomly deleting the links between neurons. An analysis of the outer-product algorithm for this random graph model of sparse interconnectivity yields the following result: If the probability of losing any given link between two neurons is 1- , then the outer-product algorithm can store on the order of pn/log pn/sup 2/ stable memories correcting a linear number of random errors. In particular, the average degree of the interconnectivity graph dictates the memory storage capability, and functional storage of memories as stable states is feasible abruptly when the average number of neural interconnections retained by a neuron exceeds the order of log n links (of a total of n possible links) with other neurons.>

Discusses the development of formal protocols for handling error tolerance which allow a precise determination of the computational gains that may be expected. The error protocols are illustrated in the framework of a densely interconnected neural network architecture (with associative memory the putative application), and rigorous calculations of capacity ar shown. Explicit capacities are also derived for the case of feedforward neural network configurations.>

The focus of the paper is the estimation of the maximum number of states that can be made stable in higher-order extensions of neural network models. Each higher-order neuron in a network of n elements is modeled as a polynomial threshold element of degree d. It is shown that regardless of the manner of operation, or the algorithm used, the storage capacity of the higher-order network is of the order of one bit per interaction weight. In particular, the maximal (algorithm independent) storage capacity realizable in a recurrent network of n higher-order neurons of degree d is of the order of ndd!. A generalization of a spectral algorithm for information storage is introduced and arguments adducing near optimal capacity for the algorithm are presented.

Recent results on the memory storage capacity of the outer-product algorithm indicate that the algorithm stores of the order of n/log n memories in a network of n fully interconnected linear threshold elements when it is required that each memory be exactly recovered from a probe which is close enough to it. In this paper a rigourous analysis is presented of generalizations of the outer-product algorithm to higher-order networks of densely interconnected polynomial thresh-old units of degree d. Precise notions of memory storage capacity are formulated, and it is demonstrated that both static and dynamic storage capacities of all variants of the outer-product algorithm of degree d are of the order of nd/log n.

The maximin problem of the maximization of the minimum amount of information that a single bit of memory retains about the entire past is investigated. The problem is to estimate the supremum over all possible sequences of update rules of the minimum information that the bit of memory at epoch (n+1) retains about the previous n inputs. Using only elementary techniques, it is shown that the maximin covariance between the memory at epoch (n+1) and past inputs is Theta (1/n), the maximum average covariance is Theta (1/n), and the maximin mutual information is Omega (1/n/sup 2/). In a consideration of related issues, the authors also provide an exact count of the number of Boolean functions of n variables that can be obtained recursively from Boolean functions of two variables, discuss extensions and applications of the original problem, and indicate links with issues in neural computation.>

A model of associate memory incorporating global linearity and pointwise nonlinearities in a state space of n-dimensional binary vectors is considered. Attention is focused on the ability to store a prescribed set of state vectors as attractors within the model. Within the framework of such associative nets, a specific strategy for information storage that utilizes the spectrum of a linear operator is considered in some detail. Comparisons are made between this spectral strategy and a prior scheme that utilizes the sum of Kronecker outer products of the prescribed set of state vectors, which are to function nominally as memories. The storage capacity of the spectral strategy is linear in n (the dimension of the state space under consideration), whereas an asymptotic result of n/4 log n holds for the storage capacity of the outer product scheme. Computer-simulated results show that the spectral strategy stores information more efficiently. The preprocessing costs incurred in the two algorithms are estimated, and recursive strategies are developed for their computation.>

Techniques from coding theory are applied to study rigorously the capacity of the Hopfield associative memory. Such a memory storesn-tuple of\pm 1's. The components change depending on a hard-limited version of linear functions of all other components. With symmetric connections between components, a stable state is ultimately reached. By building up the connection matrix as a sum-of-outer products ofmfundamental memories, one hopes to be able to recover a certain one of themmemories by using an initialn-tuple probe vector less than a Hamming distancen/2away from the fundamental memory. Ifmfundamental memories are chosen at random, the maximum asympotic value ofmin order that most of themoriginal memories are exactly recoverable isn/(2 \log n). With the added restriction that every one of themfundamental memories be recoverable exactly,mcan be no more thann/(4 \log n)asymptotically asnapproaches infinity. Extensions are also considered, in particular to capacity under quantization of the outer-product connection matrix. This quantized memory capacity problem is closely related to the capacity of the quantized Gaussian channel.