text:
Journal cover Journal topic
Nonlinear Processes in Geophysics An interactive open-access journal of the European Geosciences Union
Journal topic
Nonlin. Processes Geophys., 25, 233–240, 2018
https://doi.org/10.5194/npg-25-233-2018
Nonlin. Processes Geophys., 25, 233–240, 2018
https://doi.org/10.5194/npg-25-233-2018

Research article 22 Mar 2018

Research article | 22 Mar 2018

# Complex network description of the ionosphere

Complex network description of the ionosphere
Shikun Lu1,2, Hao Zhang1, Xihai Li2, Yihong Li2, Chao Niu2, Xiaoyun Yang2, and Daizhi Liu2 Shikun Lu et al.
• 1Department of Electronic and Engineering, Tsinghua University, Beijing, China
• 2Xi'an Research Institute of Hi-Tech, Xi'an, China

Correspondence: Hao Zhang (haozhang@mail.tsinghua.edu.cn)

Abstract

Complex networks have emerged as an essential approach of geoscience to generate novel insights into the nature of geophysical systems. To investigate the dynamic processes in the ionosphere, a directed complex network is constructed, based on a probabilistic graph of the vertical total electron content (VTEC) from 2012. The results of the power-law hypothesis test show that both the out-degree and in-degree distribution of the ionospheric network are not scale-free. Thus, the distribution of the interactions in the ionosphere is homogenous. None of the geospatial positions play an eminently important role in the propagation of the dynamic ionospheric processes. The spatial analysis of the ionospheric network shows that the interconnections principally exist between adjacent geographical locations, indicating that the propagation of the dynamic processes primarily depends on the geospatial distance in the ionosphere. Moreover, the joint distribution of the edge distances with respect to longitude and latitude directions shows that the dynamic processes travel further along the longitude than along the latitude in the ionosphere. The analysis of “small-world-ness” indicates that the ionospheric network possesses the small-world property, which can make the ionosphere stable and efficient in the propagation of dynamic processes.

1 Introduction

Including large numbers of irregularities with different sizes and affected by various factors (like solar irradiation, geomagnetic field, gravity wave and tidal wave; ), the ionosphere performs as a complex system in terms of the spatial and temporal variation. A complex network is an efficient tool to study the characteristics of complex systems that contain a large number of interacting parts. Its application spans various scientific fields , such as biology (e.g., protein interaction networks), information technology (e.g., World Wide Web) and social sciences (e.g., social networks; ). The application of complex network theory to ionosphere science is still a young field, since few research studies have been reported. The network theory was discussed by Podolská et al. with two abstracts in the 2010 and 2012 EGU General Assembly Conference . The aim of the first abstract was to examine the influence of geomagnetic disturbances and solar activity on thermal plasma parameters. The other abstract was focused on an attempt to find out time shifts between fundamental ionospheric parameters. Therefore, none of them tried to describe the global ionosphere based on a complex network.

In modern statistical mechanics of geophysics, especially seismological science, the idea of complex networks is receiving significant attention. constructed directed networks of earthquakes by placing a link between pairs of events that were strongly correlated. Their results showed that the network was scale-free and highly clustered. constructed growing random networks by adding an edge between two successive earthquakes and found that these earthquake networks were scale-free and small-world. The constructions of the above two networks were based on the expert judgment of adding an edge and ignored the uncertainty in the system. divided the southern California region into cells of 0.1 and calculated the correlation of activities among them to create networks, which showed the small-world features. proposed a network-based method for the assessment of earthquakes' relationships in space–time–magnitude patterns and further applied the results for the study of temporal variations in volcanic seismicity patterns. Those two networks were built based on correlation, which was a linear measurement of the interactions in the objective system.

Another geophysical application of complex networks is in climate science . also built a temperature network by correlation and regarded the global grid points as nodes. They showed that the network characteristics of the North American region marked the differences between the eastern and western regions. Such differences can be viewed as a reflection of the presence of a large network community on the west side of the continent. To depict the nonlinearity and uncertainty in the climate, information theory is introduced to construct the complex network of climate. used complex networks to uncover a backbone structure carrying matter and energy in the global surface air temperature field. They used mutual information (MI) to construct the network, which was undirected because the mutual information was symmetric, in order to measure the dynamical similarity of surface air temperature between regions. investigated the reliability of directed climate networks being built by conditional mutual information (CMI), using dimensionality-reduced surface air temperature data. Compared with MI, CMI is asymmetric and able to build directed networks for global surface air temperature. However, both MI and CMI are standard bivariate methods, which only describe the interactions between two spatial points without considering the influence of the others. The same is true of the correlation. A probabilistic graph is an efficient method to describe the nonlinear interactions within the system from a holistic perspective . Furthermore, similar to seismology and climate science, the ionosphere is also distributed geographically. The ionospheric variation involves spatial interactions and flows. These research studies propose a possibility that approaches from the perspective of complex networks may also shed new light on ionospheric features. In this article, a probabilistic graph is employed to model the dynamic processes within the ionosphere and build the ionospheric complex network.

Within the global ionosphere, there are interactions among the variations over different positions. Variations over one position may cause variations over other positions. The motivation of the current study is to explore the causal interactions between the vertical total electron content (VTEC) over different positions or cells of a global ionosphere map (GIM) within the global ionosphere based on the directed complex network. Hence, we can have a deep understanding of the dynamic processes within the ionosphere. We interpret the dynamic ionospheric processes as the information flow in the directed network and explore the ionospheric characteristics on a global scale. The VTEC dataset supplied by the Centre for Orbit Determination in Europe (CODE) in 2012 is selected.

The article is organized as follows. The data and method description are provided in Sect. 2. Furthermore, the results about the patterns of the ionospheric interactions are presented in Sect. 3. The scale-free topology of the ionospheric network is checked by conducting a power-law hypothesis test. The distribution of the edge distances is calculated to analyze the propagation of the dynamic processes in the ionosphere. The small-world structure of the ionospheric network is explored to examine the stability of the ionosphere. Section 4 discusses the summaries and conclusions.

2 Description of data and methods

## 2.1 VTEC data source

As a critical physical quantity of the ionosphere, VTEC carries abundant information about the variations of the ionosphere . The International Global Navigation Satellite System Service (IGS) supplies global VTEC data with 2 h time resolution. The dataset is determined from more than 200 IGS stations on a global scale . CODE, as one of the analysis centers of IGS, has estimated VTEC from the dual-frequency code and phase data of GPS since April 1998 . In the current research, VTEC data are derived from CODE (ftp://ftp.aiub.unibe.ch/CODE/) in the form of a GIM. The GIM ranges from −180 to 180 along the longitude and from −87.5 to 87.5 along the latitude. The negative values stand for the south latitude and west longitude. The size of an elementary GIM cell is 5 along the longitude and 2.5 along the latitude. Each GIM cell is defined as a variable, which is a node in the ionospheric network. The VTEC data over the GIM cells are the observations. For the decrease of the computation by reducing the variables' quantity, the size of the GIM cells has been doubled. Therefore, the latitude and longitude of GIM cells become 5 and 10. The number of variables (GIM cells) is 36×36, which is 1296, because 180 and $-\mathrm{180}{}^{\circ }$ are the same for longitude. In this paper, we select the data from 2012.

## 2.2 Mapping the data to a complex network

As a complex system, the ionosphere is usually characterized by the presence of multiple interrelated aspects, which are spatially distributed. Affected by various factors, the ionosphere also involves a significant amount of uncertainty. Moreover, our observations are always noisy; even observed aspects are often measured with some error. Thus, probability needs to be used to represent such random properties. Furthermore, a probabilistic graph can efficiently describe the nonlinearity within the system from a holistic perspective . As a result, a probabilistic graph is selected to model the interrelation and uncertainty in the ionosphere. We describe the GIM data as the realization of a multivariate probabilistic graph on the global spatial grid.

Probabilistic graphs use a graph-based representation as the basis for compactly encoding a complex probabilistic distribution over a high-dimensional space . A probabilistic graph is a useful way of visualizing interactions between multiple variables. Therefore, in addition to inference, probabilistic graphs can also be used to discover the knowledge within the dataset. As a kind of complex network, probabilistic graphs are constructed to represent a joint distribution by making conditional independence (CI) assumptions. The nodes in the networks represent variables, and the edges represent CI assumptions (Murphy2012). The absence of an edge between two nodes implies that the corresponding variables are conditionally independent given all other nodes. Based on the probability theory, we say variables X and Y are CI if the conditional joint distribution can be written as a product of conditional marginal:

$\begin{array}{}\text{(1)}& X⟂Y|Z⟺p\left(X,Y|Z\right)=p\left(X|Z\right)p\left(Y|Z\right).\end{array}$

In our study, X and Y are the two given GIM cells and Z represents the GIM cells except X and Y. Thus, the analysis is performed from a holistic perspective. As suggested in , a directed complex network can offer additional knowledge, like the distinction between child and parent nodes. Thus, we construct the ionospheric networks that only include directed edges between GIM cells. Suppose two GIM cells are not directly connected (conditionally independent) within the ionospheric network, there should be no interactions between these cells after eliminating all of the existing edges. The directed edges here represent the causal interactions. In other words, after the variations of VTEC over a certain GIM cell, there are some related variations appearing over other GIM cells. In the following, the construction of the directed ionospheric network (also known as a Bayesian probabilistic graph or Bayesian network) is introduced to describe the dynamic processes in the global ionosphere. Dynamic processes are constituted by a series of causal interactions among the GIM cells. Conditional independence tests involving sets of variables can be used to determine the existence and direction of edges .

The cells in the GIMs are defined as the variables of VTEC distributed throughout the globe. As the nodes on the network, the variables are separated by their own geospatial locations. The VTEC of each variable is arranged in the form of a time series with 2 h time resolution. Thus, for the year 2012, the length of the observations is 4392 ($\mathrm{12}\phantom{\rule{0.25em}{0ex}}{\mathrm{day}}^{-\mathrm{1}}×\mathrm{366}\phantom{\rule{0.25em}{0ex}}\mathrm{days}$). We employ a structure learning algorithm for Bayesian networks as a basis for the construction of the ionospheric networks. In our study, the measurements of the 1296 variables are all continuous. To build the directed network, we should determine the existence and directions of edges between any two variables from a holistic perspective instead of just considering the two. The Fast Greedy Equivalence Search (FGS) algorithm proposed by  works well for large numbers of continuous variables to build Bayesian networks. This algorithm utilizes the strategy that edges are iteratively added starting with an empty network, according to maximal increases in the Bayesian information criterion (BIC) score (Schwarz1978). Here, the variables' distributions are assumed to be Gaussian. We use the implementation of the FGS algorithm in the TETRAD package (Version 5.3.0-2, available at http://www.phil.cmu.edu/projects/tetrad/, last access: 22 March 2018) and make the penalty discount 10. TETRAD possesses a convenient user interface to enter preknowledge. As the ionospheric network includes 1296 nodes and 10 985 directed edges in the globe, it is hard to fully present such a complex network. Here, we exhibit part of the ionospheric network. The result is shown in Fig. 1.

Figure 1The directed complex network of the ionosphere (in part). The network is developed from the GIM dataset by the FGS algorithm. The nodes indicate the GIM cells, while the directed edges represent causal interactions between cells.

Figure 2The degree distributions of the ionospheric network. Panel (a) shows the out-degree distribution; panel (b) shows the in-degree distribution. The red curves delineate the distribution fitting.

3 Results and discussion

## 3.1 Degree distribution of the ionospheric network

To explore the influence of the VTEC's variation over a certain GIM cell, the degree of the ionospheric complex network is employed. As one of the most critical parameters to depict the nodes in a complex network, the degree is the number of edges the node possesses. Concerning ionospheric networks, the degree of a cell can be selected to quantify how many GIM cells display a causal interaction with that given cell in the globe; that is to say, cells with a large degree can influence large numbers of GIM cells. In the complex network, “hubs” refer to the nodes with large numbers of links that significantly exceed the average. Hubs have a significant effect on the system, which is described by the network. The emergence of hubs results from the scale-free property of networks . Hence, to study the hub positions where the dynamic ionospheric processes mainly originate or converge, we have to check the scale-free topology of the degree distribution of the ionospheric network. The degree distribution is the probability distribution of these degrees over the whole network. For the directed ionospheric network, the degree distribution is divided into two different kinds, the out-degree distribution (the distribution of outgoing edges) and the in-degree distribution (the distribution of incoming edges). The degree distributions of the ionospheric network are shown in Fig. 2.

It has been reported that real complex networks often exhibit scale-free properties . This means their degree distribution follows a power law, at least asymptotically; that is, the number of links of a given node exhibits a power-law distribution, $P\left(k\right)\sim {k}^{-\mathit{\gamma }}$, where k is the number of links. P(k) can be calculated by the statistical frequency, and γ is a parameter whose value is typically in the range $\mathrm{2}<\mathit{\gamma }<\mathrm{3}$. From the distributions shown in Fig. 2, it is hard to determine whether the observed degree is drawn from a power-law distribution or not. presented a principled statistical framework for discerning power-law behavior in empirical data. As for the method shown in , we have tested the power-law hypothesis quantitatively. Both the results of the out-degree and in-degree distribution reject the hypothesis, indicating that the ionospheric network is not scale-free. Thus, most GIM cells have approximately the same number of edges, indicating that the causal interactions shown by the network of the global ionosphere are homogeneous. For the dynamic processes in the ionosphere, there is no unique spatial position acting as the source or sink. This property is completely different from that of the geomagnetic field. In other words, there are no visible hub GIM cells for the ionospheric variations. Moreover, from the curves of distribution fitting shown in Fig. 2, we can see that both the distributions are more likely Poisson, just like the network of climate .

Figure 3The distribution of the directed edge distances in the global ionospheric network. Panel (a) shows the distribution of edges against the latitudinal and longitudinal distances; panel (b) shows the distribution of edges against their latitudinal distances; panel (c) shows the distribution of edges against their longitudinal distances. The red curves delineate the distribution fitting.

## 3.2 Distribution of the edge distances

The propagation of the dynamic processes is related to the transmission of energy or particles in the ionosphere. To analyze such a transport property, the distribution of the edge distances is calculated. The edge distance is defined by the geographical distance between the origin and destination of an edge. The height of the VTEC supplied by CODE is H= 450 km. As the measurements are on the earth which can be regarded as a sphere, the distances between any two positions can be calculated by the arc lengths on the sphere d=Rθ, where $R={R}_{\mathrm{0}}+H$, R0 is the earth radius and θ is the corresponding central angle. Compared with the undirected probabilistic graphs, the directed ones can provide additional knowledge about the directions of the causal interactions within the ionosphere. To study the directional characteristics of the propagation of the dynamic ionospheric processes, the edge distances are mapped in the latitude and longitude directions.

The latitudinal distances are calculated by ${d}_{\text{lat}}=\left({\text{lat}}_{\mathrm{2}}-{\text{lat}}_{\mathrm{1}}\right)R$, where lat1 and lat2 are the latitudes of the origin and destination of the given edge. Meanwhile, the longitudinal distances are calculated by ${d}_{\text{long}}=\left({\text{long}}_{\mathrm{2}}-{\text{long}}_{\mathrm{1}}\right){R}^{\prime }$, where long1 and long2 are the longitudes of the origin and destination of the given edge. As the radii of different latitudinal circles are different, the radius of an equivalent latitudinal circle is calculated by the average of the radii of the two latitude circles on which the origin and destination of the given edge are located; i.e., ${R}^{\prime }=\frac{\mathrm{1}}{\mathrm{2}}\left[\mathrm{cos}\left({\text{lat}}_{\mathrm{1}}\right)+\mathrm{cos}\left({\text{lat}}_{\mathrm{2}}\right)\right]R$. The positive signs of the distances represent the directions of edges and can either be eastward or northward. The result is shown in Fig. 3.

As is shown in Fig. 3a, the edges are mainly distributed around the origin of the coordinate system in the ionospheric network. Thus, the GIM cells are mostly connected with their spatial neighbors. The local connections indicate that, in the ionosphere, the propagation of the dynamic processes is primarily affected by the geospatial distance and almost satisfies the proximity principle in geospace. Furthermore, from the approximate symmetry along the x axis in Fig. 3b and c, we can discover that it is almost the same for the westward and eastward propagation of the dynamic processes, and also for the southward and northward. From Fig. 3b and c, we can see that the number of edges decreases as the absolute value of latitudinal and longitudinal distance increases. This phenomenon also reveals that the local interactions account for a considerable proportion in the ionospheric network. The proximal propagation may be due to the diffusion effects of charged particles in the ionosphere. In addition, comparing the standard deviations (SDs) of the edges' longitudinal and latitudinal distances, which are 0.53 and 0.28, we find that the distribution curve in the latitude direction is steeper than that in the longitude direction. Therefore, the rate of decrease along the latitude is larger than that along the longitude. Accordingly, the dynamic processes are propagated more efficiently along the longitude than along the latitude. Such a phenomenon may relate to the north–south currents or geomagnetic field in the ionosphere. Moreover, the ionospheric network is not entirely connected locally. Long-range edges emerge both along the latitude and longitude. The long-range propagation may be caused by the geomagnetic field or other global factors. Thus, the ionospheric network possesses a primarily ordered structure with some exceptional long-range connections.

## 3.3 Small-world structure of the ionospheric network

As for a complex network, the concept of being “stable” is defined as the high capability of the dynamics in the network to withstand disturbance attacks. In other words, the topology structure of the stable network cannot be easily destroyed and the dynamics can still be propagated throughout the network, even when some edges are removed by the disturbance attacks. “Efficient” is defined as the ability of rapid and easy propagation of dynamics in the network. In this subsection, we explore the small-world structure of the ionospheric network to examine the stability and efficiency of the ionosphere, which is regarded as a dynamical system.

Lying between the completely random and completely regular network, the small-world network is a type of graph in which any given node is likely to reach every other node by a small number of steps compared with the total number of network nodes . The “six degrees of separation” in social networks is one of the most famous examples. initially found that some networks can be highly clustered, like regular lattices, yet have small characteristic path lengths, like random graphs. Networks of such a nature are called small-world networks. To investigate the small-world structure of the ionospheric network, the original network has to be reduced to an undirected graph . Furthermore, to mathematically describe the small-world property, two critical parameters are often selected, which are the average clustering coefficient C and the average shortest path length L. Their definitions are shown in Eqs. (2)–(2).

$\begin{array}{}\text{(2)}& & {C}_{i}=\frac{\mathrm{2}{\mathrm{\Delta }}_{i}}{{k}_{i}\left({k}_{i}-\mathrm{1}\right)},\text{(3)}& & C=\frac{\mathrm{1}}{N}\sum _{i=\mathrm{1}}^{N}{C}_{i},\text{(4)}& & L=\frac{\mathrm{2}}{N\left(N-\mathrm{1}\right)}\sum _{i\ge j}{d}_{ij}.\end{array}$

Here, Ci is the local clustering coefficient of node i; ki is the degree of node i and Δi denotes the number of edges between the neighbors of node i, with node i itself being excluded. The global clustering coefficient C is defined as the average of all local clustering coefficients Ci. N is the number of nodes and dij denotes the length of the shortest path between the nodes i and j; dij is calculated by Dijkstra's algorithm (Newman2010). Thus, C describes the local connections in the ionospheric networks, while L characterizes a network's connectivity structure globally .

To quantitatively define a small-world network, values for the network properties must be compared with those values acquired from the equivalent random networks, which have the same degree as the given network on average. A measurement of “small-world-ness” is proposed as follows :

$\begin{array}{}\text{(5)}& \mathit{\sigma }=\frac{C/{C}_{\mathrm{r}}}{L/{L}_{\mathrm{r}}}.\end{array}$

Here, C and L are the average clustering coefficient and the average shortest path length of the given network, while Cr and Lr are those of the equivalent random network. If the given network fulfills the conditions σ>1 and $C/{C}_{\mathrm{r}}>\mathrm{1}$, it meets the small-world criterion. To reduce the impact of randomness during the analysis of the ionospheric network, the results shown in Fig. 4 are calculated by 150 random networks.

From Fig. 4a and c, we can see that the results all satisfy σ>1 and $C/{C}_{\mathrm{r}}>\mathrm{1}$. Shown in Fig. 4b and d, the frequencies are approximately Gaussian, and the SDs are 0.028 and 0.035. Such small SDs indicate that the results are close to the real values (the averages) 6.64 and 8.08. Therefore, the ionospheric network behaves as a small-world graph. The propagation of the dynamic processes in the ionosphere exhibits a small-world property. As was defined by , the small-world network possesses a small average shortest path length (compared to the regular network) and a large clustering coefficient (compared to the random network). When the number of edges per node is high, networks have a high clustering coefficient. In this case, accidental removal of some edges does not break the network into unconnected parts; the network is stable. On the other hand, a small average shortest path length L means faraway nodes can be connected as easily as nearby nodes. The smaller the L, the easier the propagation in the network. Within the networks with small L, the propagation of dynamics is efficient. Thus, small-world networks are stable and efficient in reacting to the abrupt variations .

Figure 4The test of the small-world structure in the ionospheric network. Panel (a) shows the 150 results of σ; panel (b) shows the frequency of the results of σ; panel (c) shows the 150 results of CCr; panel (d) shows the frequency of the results of CCr.

As is shown by the results above, the ionospheric network is small-world with a small average shortest path length and a large clustering coefficient. Thus, the ionospheric network exhibits properties of stable networks and of networks where dynamic processes are transferred efficiently. For example, a solar flare may create a disturbance in the ionosphere at high latitudes. However, the small-world property of the ionospheric network allows the system to respond quickly and coherently to the anomalies introduced into the system. This dynamic propagation diffuses local anomalies, thereby reducing the possibility of prolonged local extremes and providing greater stability for the global ionosphere system. Thus, chances of major ionospheric shifts are reduced. The above theory and its application to the ionosphere data suggest that the ionosphere system may be inherently stable and efficient in transferring dynamics. Just as the small-world property in the atmosphere does , such an ionospheric property also results from the teleconnections beyond the geospatial distance in the ionospheric network. Such teleconnections play an important role in stabilizing the ionosphere system and cause the dynamic ionospheric processes to be transferred efficiently .

4 Conclusions

The ionosphere can be regarded as a spatially extended complex system. Therefore, the complex network is used to analyze the dynamic processes in the global ionosphere based on the VTEC from CODE. As a Bayesian probabilistic graph, the ionospheric network is constructed based on the conditional independence theory by the FGS algorithm. The edges of the network represent the causal relationships between any two GIM cells from a holistic perspective. We have analyzed the structure of the directed ionospheric network. The results of the power-law hypothesis test show that both the out-degree and in-degree distribution of the ionospheric network are not scale-free. The ionospheric network is homogenous. None of the geospatial positions play an eminently important role in the propagation of dynamic ionospheric processes. The importance of the ionosphere over various spatial locations in the propagation of the ionospheric dynamic processes is similar. Based on the latitudinal and longitudinal distances between the beginnings and ends of the edges, the joint distribution is analyzed to explore the propagation of the dynamic processes in the ionosphere. The results show that the edges principally exist between adjacent geographical locations, indicating that the propagation of the dynamic processes mainly satisfies the proximity principle in the ionosphere. Moreover, the joint distribution of the edge latitudinal and longitudinal distances shows that the dynamic processes travel more efficiently along the longitude than along the latitude. Also, the small-world structure is studied to examine the stability of the ionosphere. The small-world-ness of the ionospheric network is found to be larger than 1. Meanwhile, the clustering coefficient is larger than those of the equal random networks. Thus, the ionospheric network possesses a small-world property, which makes the ionosphere stable and efficient in the propagation of the dynamic processes. In general, the complex network provides a unique perspective in ionosphere research. Depending on the choice of nodes, edges and methods, ionospheric networks may take different forms to study different properties of the ionosphere.

Code availability
Code availability.

Code is available by email request.

Data availability
Data availability.

VTEC data are derived from CODE (ftp://ftp.aiub.unibe.ch/CODE/) (AIUB, 2018) in the form of a global ionospheric map.

Competing interests
Competing interests.

The authors declare that they have no conflict of interest.

Acknowledgements
Acknowledgements.

This work was supported by the National Natural Science Foundation of China (41374154 and 41774156). We are grateful to Adam Woods from CIRES, University of Colorado, David Skaggs Research Center, and Rolf Dach and Stefan Schaer from the Astronomical Institute, University of Bern. They are all so kind to help us with obtaining the data. Moreover, Shikun Lu would like to thank, in particular, the ongoing and unwavering support from Taotao Sun over the years.

Edited by: Stéphane Vannitsem
Reviewed by: three anonymous referees

References

Abe, S. and Suzuki, N.: Complex-network description of seismicity, Nonlin. Processes Geophys., 13, 145–150, https://doi.org/10.5194/npg-13-145-2006, 2006. a, b

Abe, S. and Suzuki, N.: Main shocks and evolution of complex earthquake networks, Braz. J. Phys., 39, 428–430, 2009. a

AIUB: VTEC data, available at: ftp://ftp.aiub.unibe.ch/CODE/, last access: 22 March 2018.

Baiesi, M. and Paczuski, M.: Complex networks of earthquakes and aftershocks, Nonlin. Processes Geophys., 12, 1–11, https://doi.org/10.5194/npg-12-1-2005, 2005. a

Barabási, A. L. and Albert, R.: Emergence of Scaling in Random Networks, Science, 286, 509–512, 1999. a, b

Clauset, A., Shalizi, C. R., and Newman, M. E. J.: Power-Law Distributions in Empirical Data, Siam Rev., 51, 661–703, 2009. a, b

Donges, J. F., Zou, Y., Marwan, N., and Kurths, J.: The backbone of the climate network, Europhys. Lett., 87, 48007–48012, 2009a. a

Donges, J. F., Zou, Y., Marwan, N., and Kurths, J.: Complex networks in climate dynamics – Comparing linear and nonlinear network construction methods, The European Physical Journal Special Topics, 174, 157–179, 2009b. a, b, c

Ebert-Uphoff, I. and Deng, Y.: A new type of climate network based on probabilistic graphical models: Results of boreal winter versus summer, Geophys. Res. Lett., 39, L19701-1–L19701-7, 2012. a

Ercha, A., Huang, W., Yu, S., Liu, S., Shi, L., Gong, J., Chen, Y., and Hua, S.: A regional ionospheric TEC mapping technique over China and adjacent areas on the basis of data assimilation, J. Geophys. Res.-Space, 120, 1–13, 2015. a

Gallos, L. K., Song, C., and Makse, H. A.: A review of fractality and self-similarity in complex networks, Physica A, 386, 686–691, 2007. a

Guo, J., Li, W., Liu, X., and Kong, Q.: Temporal-Spatial Variation of Global GPS-Derived Total Electron Content 1999–2013, Plos One, 10, 1–21, https://doi.org/10.1371/journal.pone.0133378, 2015. a

Hlinka, J., Hartman, D., Vejmelka, M., Runge, J., Marwan, N., Kurths, J., and Palus, M.: Reliability of Inference of Directed Climate Networks Using Conditional Mutual Information, Entropy, 15, 2023–2045, 2013. a

Humphries, M. D. and Gurney, K.: Network 'small-world-ness': a quantitative method for determining canonical network equivalence, Plos One, 3, e0002051-1–e0002051-10, 2008. a

Humphries, M. D., Gurney, K., and Prescott, T. J.: The brainstem reticular formation is a small-world, not scale-free, network, P. Roy. Soc. B-Biol. Sci., 273, 503–511, 2011. a

Jiménez, A., Tiampo, K. F., and Posadas, A. M.: Small world in a seismic network: the California case, Nonlin. Processes Geophys., 15, 389–395, https://doi.org/10.5194/npg-15-389-2008, 2008. a

Kelly, M.: The Earth's Ionosphere: Plasma Physics and Electrodynamics, 2nd edn., Academic Press (Elsevier), San Diego, CA, USA, 2009. a

Koller, D. and Friedman, N.: Probabilistic Graphical Models: Principles and Techniques – Adaptive Computation and Machine Learning, MIT Press, Cambridge, MA, USA, 2009. a, b, c

Murphy, K. P.: Machine Learning: A Probabilistic Perspective, MIT Press, Cambridge, MA, USA, 2012. a

Newman, M.: Networks: An Introduction, Oxford University Press Inc., Oxford, UK, 2010. a

Nocke, T., Buschmann, S., Donges, J. F., Marwan, N., Schulz, H.-J., and Tominski, C.: Review: visual analytics of climate networks, Nonlin. Processes Geophys., 22, 545–570, https://doi.org/10.5194/npg-22-545-2015, 2015. a

Peron, T. K. D., Comin, C. H., Amancio, D. R., da F. Costa, L., Rodrigues, F. A., and Kurths, J.: Correlations between climate network and relief data, Nonlin. Processes Geophys., 21, 1127–1132, https://doi.org/10.5194/npg-21-1127-2014, 2014. a

Podolská, K., Truhlík, V., and T$\stackrel{\mathrm{¨}}{\mathrm{r}}$ísková, L.: Analysis of ionospheric parameters using graphical models, in: EGU General Assembly Conference, 2–7 May 2010, Vienna, Austria, 2010. a

Podolská, K., Truhlík, V., and T$\stackrel{\mathrm{¨}}{\mathrm{r}}$ísková, L.: Study of Correlationships between Main Ionospheric Parameters by Stochastic Modeling, in: EGU General Assembly Conference, 22–27 April 2012, Vienna, Austria, 2012. a

Ramsey, J., Glymour, M., Sanchezromero, R., and Glymour, C.: A million variables and more: the Fast Greedy Equivalence Search algorithm for learning high-dimensional graphical causal models, with an application to functional magnetic resonance images, International Journal of Data Science and Analytics, 3, 121–129, 2017.  a

Schwarz, G.: Estimating the Dimension of a Model, Ann. Stat., 6, 15–18, 1978. a

Suteanu, M.: Scale free properties in a network-based integrated approach to earthquake pattern analysis, Nonlin. Processes Geophys., 21, 427–438, https://doi.org/10.5194/npg-21-427-2014, 2014. a

Tsonis, A. A., Swanson, K. L., and Wang, G.: On the Role of Atmospheric Teleconnections in Climate, J. Climate, 21, 2990–3001, 2007. a, b, c

Wang, J., Jiang, C., Quek, T. Q., and Ren, Y.: The Value Strength Aided Information Diffusion in Online Social Networks, in: IEEE Global Conference on Signal and Information Processing (GlobalSIP), 1–6, Washington, DC, USA, 2016a. a

Wang, J., Jiang, C., Quek, T. Q., Wang, X., and Ren, Y.: The Value Strength Aided Information Diffusion in Socially-Aware Mobile Networks, IEEE Access, 4, 3907–3919, 2016b. a

Watts, D. J. and Strogatz, S. H.: Collective dynamics of 'small-world' networks, Nature, 393, 440–442, 1998. a, b

Wei, N., SHI, and Zou, R.: Analysis and Assessments of IGS Products Consistencies, Geomatics and Information Science of Wuhan University, 34, 1363–1367, 2009. a

Zerenner, T., Friederichs, P., Lehnertz, K., and Hense, A.: A Gaussian graphical model approach to climate networks, Chaos an Interdisciplinary Journal of Nonlinear Science, 24, 023103-1–023103-10, 2014. a, b, c


text:
# The gas mileage of a car is 28.16 miles per gallon. how many gallons per mile is this?

Feb 8, 2018

$1$ gallon per $\frac{25}{704}$ miles, or $1$ gallon per about $0.0355$ miles

#### Explanation:

We can set up a proportion :

$\frac{28.16}{1} = \frac{1}{x}$

We don't want decimals in a fraction, so multiply $\frac{1}{28.16}$ by 100/100 (=1).

$\frac{28.16}{1} \cdot \frac{100}{100}$

$\frac{2816}{100}$

Now simplify:

$\frac{2816 \div 4}{100 \div 4}$

$\frac{704}{25}$

Back to the equation:

$\frac{704}{25} = \frac{1}{x}$

Cross-multiply:

$704 x = 25 \cdot 1$

Divide both sides by $704$:

$x = \frac{25}{704}$ or about $0.0355$

So, the answer is $\frac{25}{704}$ or $0.0355$ about gallons per mile.

An alternate approach...

#### Explanation:

We're told that we have a car that uses 1 gallon of gas to go 28.16 miles:

$\text{miles"/"gallon} = \frac{28.16}{1}$

What we want to know is how many gallons per mile:

$\text{gallon"/"miles}$

We already know the ratio, $\frac{28.16}{1}$, so we need to invert the fraction:

$\frac{1}{28.16} \approx 0.0355$ gallons per mile

Feb 22, 2018

28.16 miles per gallon

Written mathematically we have:

28.16 miles = 1 gallon

Dividing by 28.16 on both sides we get:

1 mile = $\left(1 \div 28.16\right)$ gallons

or, 1 mile = 0.0355114 gallons

:)>

Feb 26, 2018

Approximately $0.0356 \text{ mpg}$ to 4 decimal places
Exactly $\frac{27}{704} \text{ mpg}$

#### Explanation:

The lovely thing about ratios when in the format of a fraction is that you can manipulate them into any form you wish. That is, as long as you follow the 'rules' of mathematics.

Consider the wording: mile per gallon. This is a unit of measurement and is actually in the fraction format
$\left(\text{miles")/("gallons}\right) \to \frac{m}{g}$

The word per means 'for each' so 'miles per gallon' means; how many miles can you travel for 1 gallon.

So we have as given: $\left(\text{miles")/("gallons}\right) \to \frac{28.16}{1}$

However, we need 'gallons per mile' so we can 'flip' the units of measurement upside down (invert it). Giving:

$\left(\text{gallons")/("miles}\right) \to \frac{1}{28.16}$

The target for this is gallons per mile. So we naeed to change the 28.16 miles into the value of 1.

For multiply or divide in fractions or fraction format, what we do to the bottom we also do to the top.

We need to change the 28.16 into 1 so we divide it by itself.

$\left(\text{gallons")/("miles}\right) \to \frac{1}{28.16} \equiv \frac{1 \div 28.16}{28.16 \div 28.16} = \frac{0.0355113 \ldots}{1}$

Rounding this to 4 decimal places we have

$\left(\text{gallons")/("miles}\right) = \frac{0.0356}{1}$

We don't bother with the one as it is understood to be there. So we end up with:

$\left(\text{gallons")/("miles}\right) = 0.0356$ to 4 decimal places
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Note that the decimal is not precise. As a fraction we have

$\left(\text{gallons")/("miles}\right) \to \frac{1}{28.16} \to \frac{1 \times 100}{28.16 \times 100} = \frac{100}{2816} = \frac{25}{704}$

So we have $\frac{27}{704} \text{ miles per gallon}$

As a check: $27 \div 704 \approx 0.0355113 \ldots$

format: plain


text:
# Sparse Principal Component Analysis

I'd like to run sparse PCA on some economic data. There appear to be several R functions available including elasticnet and PMA but I wanted to check if anyone had something coded up directly in MMA they might be willing share?

Thanks, Peter

-
Did you give RLink a try? Its meant for such purpose where you can mix and use existing R code/library on the fly from your Mathematica code. –  PlatoManiac Jan 25 at 12:32
@PlatoManiac Thanks, yes intend to use RLink if no MMA code available. Wanted to check if MMA version available so I might have more control over algo and diagnostics. –  pjc42 Jan 25 at 19:10


text:
电子工程代写|计算机及网络安全代写Computer and Network Security代考|CS155

statistics-lab™ 为您的留学生涯保驾护航 在代写计算机及网络安全Computer and Network Security方面已经树立了自己的口碑, 保证靠谱, 高质且原创的统计Statistics代写服务。我们的专家在代写计算机及网络安全Computer and Network Security方面经验极为丰富，各种代写计算机及网络安全Computer and Network Security相关的作业也就用不着说。

• Statistical Inference 统计推断
• Statistical Computing 统计计算
• (Generalized) Linear Models 广义线性模型
• Statistical Machine Learning 统计机器学习
• Longitudinal Data Analysis 纵向数据分析
• Foundations of Data Science 数据科学基础

电子工程代写|计算机及网络安全代写Computer and Network Security代考|Multiplexing of Transmission Signals

Quite often during the transmission of data over a network medium, the volume of transmitted data may far exceed the capacity of the medium. Whenever this happens, it may be possible to make multiple signal carriers share a transmission medium. This is referred to as multiplexing. There are two ways in which multiplexing can be achieved: time-division multiplexing (TMD) and frequency- division multiplexing (FDM).

In FDM, all data channels are first converted to analog form. Since a number of signals can be carried on a carrier, each analog signal is then modulated by a separate and different carrier frequency, and this makes their recovery possible during the demultiplexing process. The frequencies are then bundled on the carrier. At the receiving end, the demultiplexer can select the desired carrier signal and use it to extract the data signal for that channel in such a way that the bandwidths do not overlap. FDM has the advantage of supporting full-duplex communication.

TDM, on the other hand, works by dividing the channel into time slots that are allocated to the data streams before they are transmitted. At both ends of the transmission, if the sender and receiver agree on the time-slot assignments, then the receiver can easily recover and reconstruct the original data streams. Thus, multiple digital signals can be carried on one carrier by interleaving portions of each signal in time.

电子工程代写|计算机及网络安全代写Computer and Network Security代考|Wired Transmission Media

Wired transmission media are used in fixed networks physically connecting every network element. There are different types of physical media, the most common of which are copper wires, twisted pairs, coaxial cables, and optical fibers.

Copper Wires have been traditionally used in communication because of their low resistance to electrical currents that allows signals to travel even further. However, copper wires suffer interference from electromagnetic energy in the environment, and thus they must always be insulated.

Twisted Pair is a pair of wires consisting of one insulated copper wire wrapped around the other, forming frequent and numerous twists. Together, the twisted, insulated copper wires act as a full-duplex communication link. The twisting of the wires reduces the sensitivity of the cable to electromagnetic interference and also reduces the radiation of radio frequency noises that may interfere with nearby cables and electronic components. The capacity of the transmitting medium can be increased by bundling more than one pair of the twisted wires together in a protective coating. Because twisted pairs were far less expensive, easy to install, and had a high quality of voice data, they were widely used in telephone networks. However, because they are poor in upward scalability in transmission rate, distance, and bandwidth in LANs, twisted pair technology has been abandoned in favor of other technologies. Figure $1.8$ shows a twisted pair.

Coaxial Cables are dual-conductor cables with a shared inner conductor in the core of the cable protected by an insulation layer and the outer conductor surrounding the insulation. These cables are called coaxial because they share the inner conductor. The inner core conductor is usually made of solid copper wire but, at times, can also be made up of stranded wire. The outer conductor, which is made of braided wires, but sometimes made of metallic foil or both, commonly forms a protective tube around the inner conductor. This outer conductor is also further protected by annther outer enating called the sheath. Figure $1.9$ shows a enaxial eable. Coaxial cables are commonly used in television transmissions. Unlike twisted pairs, coaxial cables can be used over long distances. There are two types of coaxial cables: thinnet, a light and flexible cabling medium that is inexpensive and easy to install, and the thicknet, which is thicker and harder to break and can carry more signals for a longer distance than thinnet.

广义线性模型代考

statistics-lab作为专业的留学生服务机构，多年来已为美国、英国、加拿大、澳洲等留学热门地的学生提供专业的学术服务，包括但不限于Essay代写，Assignment代写，Dissertation代写，Report代写，小组作业代写，Proposal代写，Paper代写，Presentation代写，计算机作业代写，论文修改和润色，网课代做，exam代考等等。写作范围涵盖高中，本科，研究生等海外留学全阶段，辐射金融，经济学，会计学，审计学，管理学等全球99%专业科目。写作团队既有专业英语母语作者，也有海外名校硕博留学生，每位写作老师都拥有过硬的语言能力，专业的学科背景和学术写作经验。我们承诺100%原创，100%专业，100%准时，100%满意。

MATLAB代写

MATLAB 是一种用于技术计算的高性能语言。它将计算、可视化和编程集成在一个易于使用的环境中，其中问题和解决方案以熟悉的数学符号表示。典型用途包括：数学和计算算法开发建模、仿真和原型制作数据分析、探索和可视化科学和工程图形应用程序开发，包括图形用户界面构建MATLAB 是一个交互式系统，其基本数据元素是一个不需要维度的数组。这使您可以解决许多技术计算问题，尤其是那些具有矩阵和向量公式的问题，而只需用 C 或 Fortran 等标量非交互式语言编写程序所需的时间的一小部分。MATLAB 名称代表矩阵实验室。MATLAB 最初的编写目的是提供对由 LINPACK 和 EISPACK 项目开发的矩阵软件的轻松访问，这两个项目共同代表了矩阵计算软件的最新技术。MATLAB 经过多年的发展，得到了许多用户的投入。在大学环境中，它是数学、工程和科学入门和高级课程的标准教学工具。在工业领域，MATLAB 是高效研究、开发和分析的首选工具。MATLAB 具有一系列称为工具箱的特定于应用程序的解决方案。对于大多数 MATLAB 用户来说非常重要，工具箱允许您学习应用专业技术。工具箱是 MATLAB 函数（M 文件）的综合集合，可扩展 MATLAB 环境以解决特定类别的问题。可用工具箱的领域包括信号处理、控制系统、神经网络、模糊逻辑、小波、仿真等。

电子工程代写|计算机及网络安全代写Computer and Network Security代考|ICCWS2022

statistics-lab™ 为您的留学生涯保驾护航 在代写计算机及网络安全Computer and Network Security方面已经树立了自己的口碑, 保证靠谱, 高质且原创的统计Statistics代写服务。我们的专家在代写计算机及网络安全Computer and Network Security方面经验极为丰富，各种代写计算机及网络安全Computer and Network Security相关的作业也就用不着说。

• Statistical Inference 统计推断
• Statistical Computing 统计计算
• (Generalized) Linear Models 广义线性模型
• Statistical Machine Learning 统计机器学习
• Longitudinal Data Analysis 纵向数据分析
• Foundations of Data Science 数据科学基础

电子工程代写|计算机及网络安全代写Computer and Network Security代考|Analog Encoding of Digital Data

Recall that digital information is in the form of $1 \mathrm{~s}$ and $0 \mathrm{~s}$. To send this information over some analog medium such as the telephone line, for example, which has limited bandwidth, digital data needs to be encoded using modulation and demodulation to produce analog signals. The encoding uses a continuous oscillating wave, usually a sine wave, with a constant frequency signal called a carrier signal.

The carrier has three modulation characteristics: amplitude, frequency, and phase shift. The scheme then uses a modem, a modulation-demodulation pair, to modulate and demodulate the data signal based on any one of the three carrier characteristics or a combination. The resulting wave is between a range of frequencies on both sides of the carrier, as shown below [1]:

• Amplitude modulation represents each binary value by a different amplitude of the carrier frequency. The absence of or low carrier frequency may represent a 0 , and any other frequency then represents a 1 . However, this is a rather inefficient modulation technique and is therefore used only at low frequencies up to 1200 bps in voice grade lines.
• Frequency modulation also represents the two binary values by two different frequencies close to the frequency of the underlying carrier. Higher frequencies represent a 1 , and low frequencies represent a 0 . The scheme is less susceptible to errors.
• Phase shift modulation changes the timing of the carrier wave, shifting the carrier phase to encode the data. A 1 is encoded as a change in phase by $180^{\circ}$, and a 0 may be encoded as a 0 change in phase of a carrier signal. This is the most efficient scheme of the three, and it can reach a transmission rate of up to 9600 bps.

电子工程代写|计算机及网络安全代写Computer and Network Security代考|Digital Encoding of Digital Data

In this encoding scheme, which offers the most common and easiest way to transmit digital signals, two binary digits are used to represent two different voltages. Within a computer, these voltages are commonly 0 and 5 volts. Another procedure uses two representation codes: nonreturn to zero level $(N R Z-L)$, in which negative voltage represents binary one and positive voltage represents binary zero, and nonreturn to zero, invert on ones (NRZ-I). See Figs. $1.6$ and $1.7$ for an example of these two codes. In NRZ-L, whenever a 1 occurs, a transition from one voltage level to another is used to signal the information. One problem with NRZ signaling techniques is the requirement of a perfect synchronization between the receiver and transmitter clocks. This is, however, reduced by sending a separate clock signal. There are yet other representations such as the Manchester and differential Manchester, which encode clock information along with the data.

One may wonder, why go through the hassle of digital encoding and transmission? There are several advantages over its cousin, analog encoding. These include the following:

• Plummeting costs of digital circuitry
• More efficient integration of voice, video, text, and images
• Reduction of noise and other signal impairment because of the use of repeaters
• The capacity of channels is utilized best with digital techniques
• Better encryption and hence better security than in analog transmission

电子工程代写|计算机及网络安全代写Computer and Network Security代考|Analog Encoding of Digital Data

• 幅度调制通过载波频率的不同幅度来表示每个二进制值。载波频率的缺失或低可以表示 0 ，而任何其他频率则表示 1 。然而，这是一种相当低效的调制技术，因此仅用于语音等级线路中高达 1200 bps 的低频。
• 频率调制还通过接近底层载波频率的两个不同频率来表示两个二进制值。高频代表 1 ，低频代表 0 。该方案不易出错。
• 相移调制改变载波的时序，移动载波相位以对数据进行编码。A 1 被编码为相位变化180∘，并且0可以被编码为载波信号的相位变化0。这是三者中效率最高的方案，它可以达到高达 9600 bps 的传输速率。

电子工程代写|计算机及网络安全代写Computer and Network Security代考|Digital Encoding of Digital Data

• 数字电路成本直线下降
• 更高效的语音、视频、文本和图像的集成
• 由于使用中继器，减少了噪音和其他信号损伤
• 数字技术最好地利用信道容量
• 比模拟传输更好的加密，因此更好的安全性

广义线性模型代考

statistics-lab作为专业的留学生服务机构，多年来已为美国、英国、加拿大、澳洲等留学热门地的学生提供专业的学术服务，包括但不限于Essay代写，Assignment代写，Dissertation代写，Report代写，小组作业代写，Proposal代写，Paper代写，Presentation代写，计算机作业代写，论文修改和润色，网课代做，exam代考等等。写作范围涵盖高中，本科，研究生等海外留学全阶段，辐射金融，经济学，会计学，审计学，管理学等全球99%专业科目。写作团队既有专业英语母语作者，也有海外名校硕博留学生，每位写作老师都拥有过硬的语言能力，专业的学科背景和学术写作经验。我们承诺100%原创，100%专业，100%准时，100%满意。

MATLAB代写

MATLAB 是一种用于技术计算的高性能语言。它将计算、可视化和编程集成在一个易于使用的环境中，其中问题和解决方案以熟悉的数学符号表示。典型用途包括：数学和计算算法开发建模、仿真和原型制作数据分析、探索和可视化科学和工程图形应用程序开发，包括图形用户界面构建MATLAB 是一个交互式系统，其基本数据元素是一个不需要维度的数组。这使您可以解决许多技术计算问题，尤其是那些具有矩阵和向量公式的问题，而只需用 C 或 Fortran 等标量非交互式语言编写程序所需的时间的一小部分。MATLAB 名称代表矩阵实验室。MATLAB 最初的编写目的是提供对由 LINPACK 和 EISPACK 项目开发的矩阵软件的轻松访问，这两个项目共同代表了矩阵计算软件的最新技术。MATLAB 经过多年的发展，得到了许多用户的投入。在大学环境中，它是数学、工程和科学入门和高级课程的标准教学工具。在工业领域，MATLAB 是高效研究、开发和分析的首选工具。MATLAB 具有一系列称为工具箱的特定于应用程序的解决方案。对于大多数 MATLAB 用户来说非常重要，工具箱允许您学习应用专业技术。工具箱是 MATLAB 函数（M 文件）的综合集合，可扩展 MATLAB 环境以解决特定类别的问题。可用工具箱的领域包括信号处理、控制系统、神经网络、模糊逻辑、小波、仿真等。

电子工程代写|计算机及网络安全代写Computer and Network Security代考|ClS654

statistics-lab™ 为您的留学生涯保驾护航 在代写计算机及网络安全Computer and Network Security方面已经树立了自己的口碑, 保证靠谱, 高质且原创的统计Statistics代写服务。我们的专家在代写计算机及网络安全Computer and Network Security方面经验极为丰富，各种代写计算机及网络安全Computer and Network Security相关的作业也就用不着说。

• Statistical Inference 统计推断
• Statistical Computing 统计计算
• (Generalized) Linear Models 广义线性模型
• Statistical Machine Learning 统计机器学习
• Longitudinal Data Analysis 纵向数据分析
• Foundations of Data Science 数据科学基础

电子工程代写|计算机及网络安全代写Computer and Network Security代考|Computer Network Models

There are several configuration models that form a computer network. The most common of these are the centralized and distributed models. In a centralized model, several computers and devices are interconnected and can talk to each other. However, there is only one central computer, called the master, through which all correspondence must take place. Dependent computers, called surrogates, may have reduced local resources, such as memory, and sharable global resources are controlled by the master at the center. Unlike the centralized model, however, the distributed network consists of loosely coupled computers interconnected by a communication network consisting of connecting elements and communication channels. The computers themselves may own their resources locally or may request resources from a remote computer. These computers are known by a string of names, including host, client, or node. If a host has resources that other hosts need, then that host is known as a server. Communication and sharing of resources are not controlled by the central computer but are arranged between any two communicating elements in the network. Figures $1.2$ and $1.3$ show a centralized network model and a distributed network model, respectively.

A computer network with two or more computers or clusters of network and their resources connected by a communication medium sharing communication protocols and confined in a small geographic area, such as a building floor, a building, or a few adjacent buildings, is called a local area network (LAN). The advantage of a LAN is that all network elements are close together, and thus the communication links maintain a higher speed of data movement. Also, because of the proximity of the communicating elements, high-cost and high-quality communicating elements can be used to deliver better service and high reliability. Figure $1.4$ shows a LAN.

电子工程代写|计算机及网络安全代写Computer and Network Security代考|Transmission Technology

The media through which information has to be transmitted determine the signal to be used. Some media permit only analog signals. Some allow both analog and digital. Therefore, depending on the media type involved and other considerations, the input data can be repreesenteed as either a digital or an analog signal. In an analog format, data is sent as continuous electromagnetic waves on an interval representing things such as voice and video and propagated over a variety of media that may include copper wires, a twisted coaxial pair or cable, fiber optics, or wireless. We will discuss these media later in the chapter. In a digital format, on the other hand, data is sent as a digital signal, a sequencé of voltage pulses that can be reepreesenteed as a stream of binary bits. Both analog and digital data can be propagated and oftentimes represented as either analog or digital.

Transmission itself is the propagation and processing of data signals between network elements. The concept of representation of data for transmission, either as an analog or a digital signal, is called an encoding scheme. Encoded data is then transmitted over a suitable transmission medium that connects all network elements. There are two encoding schemes, analog and digital. Analog encoding propagates analog signals representing analog data such as sound waves and voice data. Digital encoding, on the other hand, propagates digital signals representing either an analog or a digital signal representing digital data of binary streams by two voltage levels. Since our interest in this book is in digital networks, we will focus on the encoding of digital data.

广义线性模型代考

statistics-lab作为专业的留学生服务机构，多年来已为美国、英国、加拿大、澳洲等留学热门地的学生提供专业的学术服务，包括但不限于Essay代写，Assignment代写，Dissertation代写，Report代写，小组作业代写，Proposal代写，Paper代写，Presentation代写，计算机作业代写，论文修改和润色，网课代做，exam代考等等。写作范围涵盖高中，本科，研究生等海外留学全阶段，辐射金融，经济学，会计学，审计学，管理学等全球99%专业科目。写作团队既有专业英语母语作者，也有海外名校硕博留学生，每位写作老师都拥有过硬的语言能力，专业的学科背景和学术写作经验。我们承诺100%原创，100%专业，100%准时，100%满意。

MATLAB代写

MATLAB 是一种用于技术计算的高性能语言。它将计算、可视化和编程集成在一个易于使用的环境中，其中问题和解决方案以熟悉的数学符号表示。典型用途包括：数学和计算算法开发建模、仿真和原型制作数据分析、探索和可视化科学和工程图形应用程序开发，包括图形用户界面构建MATLAB 是一个交互式系统，其基本数据元素是一个不需要维度的数组。这使您可以解决许多技术计算问题，尤其是那些具有矩阵和向量公式的问题，而只需用 C 或 Fortran 等标量非交互式语言编写程序所需的时间的一小部分。MATLAB 名称代表矩阵实验室。MATLAB 最初的编写目的是提供对由 LINPACK 和 EISPACK 项目开发的矩阵软件的轻松访问，这两个项目共同代表了矩阵计算软件的最新技术。MATLAB 经过多年的发展，得到了许多用户的投入。在大学环境中，它是数学、工程和科学入门和高级课程的标准教学工具。在工业领域，MATLAB 是高效研究、开发和分析的首选工具。MATLAB 具有一系列称为工具箱的特定于应用程序的解决方案。对于大多数 MATLAB 用户来说非常重要，工具箱允许您学习应用专业技术。工具箱是 MATLAB 函数（M 文件）的综合集合，可扩展 MATLAB 环境以解决特定类别的问题。可用工具箱的领域包括信号处理、控制系统、神经网络、模糊逻辑、小波、仿真等。


text:
## Profile

Qiaochu Yuan
Worked at Machine Intelligence Research Institute
Attends University of California, Berkeley
Lives in Berkeley, CA
2,313 followers|155,855 views

## Stream

### Qiaochu Yuan

Shared publicly  -

Very nice visualization of prime factorizations.
9
4

iirc, this is included in http://incrediblenumbersapp.com/, which is a nice app for kids

### Qiaochu Yuan

Shared publicly  -

Here's a dumb riddle. We all know that a meromorphic function on a Riemann surface is a function to CP^1. We also all know that meromorphic functions on a Riemann surface form a field, and in particular a ring. So... why isn't CP^1 a ring object in the category of Riemann surfaces?

(It took me an embarrassingly long time to figure this out.)
1

Is it because the point is not a Riemann surface?

### Qiaochu Yuan

Shared publicly  -
8

Ah, technology. It's a blessing and a curse. To help get more people to read your posts is pure pleasure on my side! In that reign, I tried some categorification-without-looking-at-literature myself, to come up with an alternative to burritos. And these notes want out, if I'd only dare to post them. Maybe more programmers people would like categorification if they knew more...

There. It's promised, nothing can go wrong now. And maybe it even works and someone shows up here for better, or for more.

### Qiaochu Yuan

Shared publicly  -

Among all of the standard algebraic structures that a student typically encounters in an introduction to abstract algebra (groups, rings, fields, modules), commutative rings are somehow special: th...
4
2

### Qiaochu Yuan

Shared publicly  -

Previously we learned how to count the number of finite index subgroups of a finitely generated group $latex G$. But for various purposes we might instead want to count conjugacy classes of finite ...
4

### Qiaochu Yuan

Shared publicly  -
2
Have them in circles
2,313 people

### Qiaochu Yuan

Shared publicly  -

It's common to think of monads as generalized algebraic theories; the most familiar examples, such as the monads on $latex \text{Set}$ encoding groups, rings, and so forth, have this flavor. Howeve...
4
1

### Qiaochu Yuan

Shared publicly  -

Once upon a time I imagine people were very happy to think of Lie algebras as "infinitesimal groups," but presumably when infinitesimals fell out of favor this interpretation did too. In this post ...
9
3

You can write code to "implement" a Lie algebra by writing polymorphic code for the group and replacing the base field of reals with the reals extended by infintesimals: http://blog.sigfpe.com/2008/04/infinitesimal-rotations-and-lie.html

The variable I call 'e' gives the comultiplication.

### Qiaochu Yuan

Shared publicly  -

Previously we claimed that if you want to check whether a category $latex C$ "behaves like a category of spaces," you can try checking whether it's distributive. The goal of today's post is to just...
3

### Qiaochu Yuan

Shared publicly  -

Let $latex 2$ be a set with two elements. The category of Boolean functions is the category whose objects are the finite powers $latex 2^k, k \in \mathbb{Z}_{\ge 0}$ of $latex 2$ and whose morphism...
5
1

### Qiaochu Yuan

Shared publicly  -

I have a dumb question about physics. Let's consider the one-dimensional heat equation du/dt = d^2 u / dx^2 with boundary conditions u(0, t) = u(L, t) = 0. An example of a solution is u = e^{-t^2/2} sin (pi x / L).

Now, if I think of this solution as being supported on the interval [0, L], then energy is clearly not conserved. But the Wikipedia article claims that the physical derivation of the heat equation assumes conservation of energy. So what gives? Are the boundary conditions somehow sucking all of the energy away?
3

: thanks again! That was very helpful.

### Qiaochu Yuan

Shared publicly  -

What's going on with Wordpress's LaTeX? I can't see anything when I try to write new posts.
2

I'm not having this problem, but my last post was on November, 16.
People
Have them in circles
2,313 people
Work
Occupation
Employment
• Machine Intelligence Research Institute
Visiting Fellow, 2013 - 2013
• PROMYS
Counselor, 2012 - 2012
• Stack Overflow, Inc.
Intern, 2011 - 2011
Places
Currently
Berkeley, CA
Previously
Boston, MA - New York, NY - Bellevue, WA - Nanjing, China - Singapore - Vancouver, WA - Cambridge, UK
Story
Introduction
I'm a third-year graduate student in mathematics at UC Berkeley.
Bragging rights
USA Mathematical Olympiad Honorable Mention (2006), Siemens-Westinghouse Science and Technology Competition Semifinalist (2007), Intel Science Talent Search Finalist (2008), William Lowell Putnam Mathematical Competition Honorable Mention (2009), NSF Fellow (2012)
Education
• University of California, Berkeley
Mathematics, 2012 - present
• Massachusetts Institute of Technology
Mathematics, 2008 - 2012
• University of Cambridge
Mathematics, 2010 - 2011


text:
# A digression on linear systems thinking

You probably don’t have to read this if you read my blog at all; but just in case… Skip this if you are familiar with linear systems.

I’ve sometimes been asked to make my blog posts simpler to understand for the typical photographer. All this mathematics on diffraction and photons and such is not within the backgrounds of most practicing photographers, whether pros or amateurs. I’ve thought about this, but often, as Vincent Versace likes to quote Einstein all the time, we can make something as simple as possible, but no simpler. Instead, my aim here is to provide a clear and basic understanding of one of the central underpinnings of all analysis of cameras and images.

This notion is that a camera and its component parts can be assumed to be a linear system. What this implies is that the light falling on the camera can be taken as some sort of input signal and the image that comes out can be taken as an output signal. All of the component parts of the camera, lens, optical filters, sensor, electronics, and so on, operate on this input signal to produce an output signal.

To say that the system is linear implies among other things that if you had an input signal I and another input signal J, and you knew the output signals for each of these, call them O and P, so that our camera maps $I \longrightarrow O$ and $J \longrightarrow P$, then our camera will map $I+J \longrightarrow O+P$.

In its most basic form, this means that we can break an input signal down into distinct component parts, say points of light, and treat each point on its own. We can then consider how the camera will handle each point of light and build up the resulting image, or output signal, up out of the sum of the entire set of results to each distinct point.

This doesn’t always work. Every system has its limits. If our input was a single point of light that just saturated the limits of a sensor well yielding over-exposure, then adding in two of these points of light won’t deliver twice as much over-exposure. Instead, we’re likely to see a non-linear phenomenon called inter-pixel interference (IPI) where the adjacent pixels will start to show values that were due to electrons spilling over into the associated sensor wells. To avoid these limits, we often have to limit our models to small signals, values of input that can be summed up without over-stressing the system. When these non-linearities occur, we get results like this:

$I + J \overset{\text{Camera}}{\rightarrow }O + P + a O^2 + b P^2 + c O P +\text{other stuff}$

where a, and b, and c and so on are constants that indicate how much of each kind of non-linearity is present. In sound systems, these higher order terms are sometimes called harmonic distortion. Aliasing, which I’ve written about a good deal here lately, yields a kind of sub-harmonic distortion. Anytime you put in content at one frequency and get out content at another frequency, you’ve found a non-linearity. We’ll come back to why this is later. But enough of non-linearities for now.

If we’re going to represent cameras and scenes as linear systems and signals, then we need some mathematical way of representing systems as operations and the signals that are operated on. One natural way is in terms of space. We can break the scene down into points of light coming in from some direction. In one limit, this is basically geometric optics and ray-tracing. This doesn’t work very well once we encounter the wave character of light with diffraction, and so some other machinery is required. However, a DSLR sensor and its output files are perfect instrument for considering in this fashion. For each pixel position, the file reports values of red, green, and blue. So, if we number pixels columns from 1 to $N$ and pixel rows from 1 to $M$, then we can describe an image file as RGB(n, m) where n and m are the row and column values. We can transform these RGB values into La*b* or CMYK or whatever else as well.

Let’s take an example of a system. Suppose we take a file and apply a blur to it. Each pixel has 8 neighboring pixels, 2 up and down, 2 right and left, and 4 more on the diagonals. Let’s say that our blur maps the central pixel value as 80% into the central pixel, 4% into each of the up/down and right/left pixels, and 1% into each of the diagonal pixels. The total sums to 100% so no signal strength is lost. This is a perfectly linear operation. We could compute the output image one input pixel at a time and add up the results to get the final blurred image. Although the actual parameters differ from what I’ve quoted here, blur functions in Photoshop work exactly like this.

But back to where our overall thinking about lenses and such doesn’t quite fit the geometric optics model. Often the solution is in terms of a trick sponsored by Mr Fourier (Joe to his friends). Let’s consider our output signal in terms of a print. Say we used as an input signal a single point of light, so our print is mainly black with some small white blob in the middle. [We are already in some intellectual difficulty since we have to think of paper white as something and black ink as nothing; but work with me here.] We can give the print some $x, y$ co-ordinates and describe the blob mathematically in terms of the intensities of red, green and blue, or cyan, magenta, yellow and black. Mr Fourier’s trick is to show that he could have created that same white blob by adding up a bunch of sine waves lined up properly in the horizontal and vertical directions. Say we start with horizontal sine waves. We get the first one with one wavelength across the horizontal direction and lined up so its peak value is right where the blob is. Then we get another with two wavelengths and line it up with the location of the blob. And so on. With an infinite number of sine waves. What we’ll find is that right at the blob, these waves all interfere constructively, because we made it that way. Away from the blob, they all interfere destructively and the result is nothing. So, we have a thin vertical line. Then we repeat in the vertical direction, and we get our blob. If we can do this trick with any point, we can do it for any shape made up of points.

Here’s an example for our point, given in just one dimension, up to the first 2 sine waves:

Fourier expansion of a point at the origin, 2 terms

Here’s what we get at 10 terms:

Fourier expansion at 10 terms

And here’s after 1000 terms:

Fourier expansion of a point, 1000 terms

Here’s what we’d get in a 3-D plot expanding only to the first 3 terms in Mr Fourier’s world:

2-D Fourier expansion of a point, 3 terms

Looks a bit like an Airy disk, no? Back to that later.

Let’s think for a moment about what’s going on here. We began by thinking of our signal in terms of some intensity of light at a point in space, say $I(x,y)$. What this means is that our signal has some given value $I$ at each point $x,y$. But now, we’re saying that we could have made the exact same signal up out of some sine waves by specifying their intensity and phase, $A_x, \phi_x, A_y, \phi_y$, at each wavelength $2 \pi n_x/L_x, 2 \pi n_y/L_y$, where the $n_x, n_y$ run from 1 to infinity. When we represent our signal in the form $I(x,y)$ we are using a Cartesian co-ordinate system in $x$ and $y$. When we represent it in Mr Fourier’s system of sine waves, we are just using another Cartesian co-ordinate system in $n_x$ and $n_y$.

What we have done in going into Mr Fourier’s world is to change our co-ordinate system; and Mr Fourier’s transformations are nothing more or less than a rotation of co-ordinates. This is why these optical engineers are all uptight about these resolution charts. They understand that any image can be made up out of these little squiggles of sine waves in the same way that it can be made up out of points of light.

This tells us that a signal is some thing in a space of many dimensions. If we think about our DSLR sensor, say from my beautiful Nikon D700, we have 2832 rows and 4256 columns. At each one of these row and column positions, we can have a discrete R or G or B value of between 0 and $2^14-1 = 16,383$. The number of dimensions is equal to the number of pixel positions, 12,052,992. That’s a lot of dimensions. Still, many problems in Fourier analysis have infinite dimensions. When we get to systems like this sensor or its output files, where the number of dimensions are finite and the values in each dimension are quantized, we will use something called the discrete Fourier transform or DFT. Same basic idea, slightly different math: sums instead of integrals.

A central dogma of linear systems thinking is that systems have characteristic functions, called their impulse response, that they apply to any impulse of energy applied to them. The underlying theory is that any linear system uses up energy in a unique way. A classic case might be a pendulum. Hit it with a hammer and the pendulum will swing at some characteristic frequency for a while and gradually slow to a stop. In the case of a camera, with a nearly circular aperture, we have seen before in other posts that the result is an Airy disk. If the aperture is square, the result is much more like the approximation to a pulse that we just saw using Fourier series. The concept of an impulsive input signal is that it quickly delivers energy into the system. The way in which the system degrades that energy can depend thereafter only on its structure. In the case of a camera, if we deliver a short sharp pulse of light, the response is called the point spread function (PSF). If we imagine that any scene is comprised of a huge number of such discrete pulses, then we can further assume that an image is composed of a sum of point spread functions weighted by the unique intensities and colors of each point from the scene.

We looked earlier at a blur function in some post processing system like Photoshop. This blur had its own unique impulse response or PSF, just as we gave earlier. If we applied this blur function across every point (or dimension) in the image file, we would be doing an operation called convolution. A mathematical expression for convolution is as follows:

$\text{Output}(n, m) = \underset{j=0}{\overset{J-1}{ \sum }} \underset{k=0}{\overset{K-1}{ \sum }} \text{Input}(j, k)*\text{ImpulseResponse}(n-j, m-k)$

Admittedly, this may look ugly. But it’s just some math to describe what we said; namely, to find the output value at some point n, m we take the input at n, m and add up all the possible values of the impulse response around it. In many cases, like our blur function, the impulse response is very limited. Summing over the j and k values is just this process of sliding the impulse response around until we’ve collected all the input values that could impact the output position.

There is another way to handle this convolution procedure, in Mr Fourier’s world. The notion is similar to using logarithms to multiply. Anybody remember that? If you want to multiply two numbers, you can take their logarithms and add them, then find the antilogarithm of the result; and that’s your answer. In the Fourier world, the equivalent of convolution is just multiplication. So, if we know the Fourier transform of an input signal and the Fourier transform of a system’s PSF (or what’s equivalent, its MTF), then we can multiply these two together; and that’s the Fourier transform of the output. (OK, I’m neglecting phase terms here for those of you who understand all this… Why are you here anyway?) If you want the result back in regular space, take the inverse Fourier transform; and violà, the answer. One of the reasons that folks into digital signal processing love their Fourier transforms so much is that multiplying signals in Fourier’s world is much much less time consuming of computer resources than convolution in regular space (or time). Even throwing in the computational cost of Fourier transforms, it’s often much faster.

In the real world, we find that many optical components do not have uniform MTFs over their entire surface. Lenses get soft at the edges. Sensors show vignetting at their boundaries. So, the MTF that we find near the optical axis is not the MTF at the edge. Likewise, we can find that the MTF depends on the orientation of line pairs. Horizontal MTF is not the same as vertical MTF is not the same as tangential MTF. Fourier theory actually accounts for this reasonably well; and would tell us that we need to look separately at horizontal and vertical spatial frequencies. But we should be able to compute tangential MTFs from the combination of horizontal and vertical MTFs; and if that isn’t true, then we have a linearity problem. The dependence of MTF on location is in itself a kind of non-linearity; but one that is easy to work with. We would have a similar situation with a sound system whose frequency response changed as it warmed up. So long as the rate of change of the frequency response is slow, say on the order of several seconds, with respect to the audio frequencies (20 – 20,000 Hz) we have no big problems. In our lenses though, life is a little tougher since we find MTFs changing across spatial dimensions that are of the order of the system’s spatial frequency response. What saves our linear modeling in this case is that it’s the high spatial frequencies that are impacted as we move to the edge. The lower spatial frequencies, representing content that spans the entire image, remain reasonably constant in most cases.

So, our central idea is that we can decompose a signal into its component parts. We can choose those parts for our convenience. A similar situation occurs in, say, your car stereo when you turn up the bass. You’ve set the electronic system to increase the lower frequencies selectively. The same thing can be done for spatial systems as well.

Let’s show a simple example. Here’s a circular aperture, represented in Photoshop as a white disk in the center of a black background.

Circular aperture

And here is the magnitude of its Discrete Fourier Transform (DFT):

DFT of circular aperture

Now, I should probably explain some mathematical niceties in this representation. First, this is just our old friend, the Airy disk, which we first encountered here in discussions of diffraction. Looking at this image, you’ll notice certain symmetries. What you’re seeing is, in effect, the Airy disk sliced into four pieces and put together backwards. This is just a side-effect of the way in which the software I’m using (Wolfram Mathematica) computes the DFT. The low spatial frequencies are clustered in the left-hand corner, where, as the scales show, both the frequencies in the x and y axes are near 0.

Let’s see what happens if we apply a low pass filter to this circular disk. The DFT now looks like this, with those few higher spatial frequency ripples gone:

Airy Disk low-pass filtered

And this is the resulting image:

Circular aperture, smoothed

You can see the obvious smoothing of the sharp edges of the disk. Let’s go the other way. Let’s enhance the higher frequencies and remove the low ones.

High pass filter applied

You might have to look at this for a moment, but what’s happened is that the low frequencies are completely removed and the higher frequency ripples have been amplified. Here’s the resulting image:

circular aperture, high pass filtered

Cool, eh? We just have the edge of the disk left. Just in case you thought this didn’t work; it actually works a hot damn.

In another post here, I showed how the human eye is a bandpass system in terms of its contrast sensitivity function (CSF). What is quite astounding about the CSF chart shown there is that our eyes are obviously processing the image on the basis of its spatial frequency content and not just the points of light. The peak values of the points of light are exactly the same along any horizontal line. But we don’t see them as equal. We see them in a way that depends on the local variation in spatial frequency. Our perceptual apparatus, our perceptual system, has a bandpass MTF!

As a thing of some not insignificant beauty, depending on your point of view I guess, the following is the DFT of that CSF chart:

DFT of the CSF chart

Click on the image for the larger view and pay careful attention to the area around 0,0 in the left hand corner. You should see a bit of a dotted line there indicating the very low frequency values corresponding to the uniform gray of the image. The very fine spatial frequency structure shows the information content of the image; and the notches tell that many spatial frequencies are missing. Nonetheless, this view of the CSF chart in Mr Fourier’s world is perhaps even more amazing that the regular view we have in our own; don’t you think?


text:
# Partitioning polynomials in $\mathbb{Z}[x,y]$ by the primes they represent

Suppose you have a set $S\subset\mathbb{Z}[x,y].$ How can one efficiently partition the polynomials into sets such that the primes represented by the polynomials in any given set are identical? For these purposes, "efficient" can be interpreted as "subquadratic", though I'm interested in practical as well as theoretical/worst-case.

A special case of particular interest: binary quadratic forms $ax^2+bxy+cy^2.$

For any pair of polynomials, it's possible to check if the two are equivalent forms. Of course this requires checking quadratically many pairs. One practical speedup would be to first partition the polynomials by discriminant—in the case of binary quadratic forms, $b^2-4ac.$ This takes only (essentially) linear time, and results in speedup by a factor of $k$ if there are $k$ discriminants with roughly equal numbers of polynomials for each (time $n^2/k^2$ for each discriminant, $k$ discriminants). Are there further invariants that can be used in similar fashion?

-
A good reference might be David Cox's "Primes of the Form x^2+ny^2." He discusses some applications of genus theory, class field theory, and complex multiplication to this kind of problem. –  Tony Mar 21 '11 at 2:52

First partition the polynomials $ax^2+bxy+cy^2$ by their discriminant $\Delta=b^2-4ac$, as mentioned in the question. Polynomials with $\Delta>0$ have a unique reduced form, that is, can be represented uniquely as $ax^2+bxy+cy^2$ with $$\left|\sqrt\Delta-2|c|\right|<b<\sqrt\Delta$$
Polynomials with negative discriminant have only finitely many forms with $$|b|\le a\le c$$ (To be reduced, $b\ge0$ if $a\in\{|b|,c\},$ but of course finitude does not depend on this.) It's not clear that this is practical when comparing forms; it depends on the size of the coefficients and the number of forms of a given discriminant.
Of course since only the primes in those discriminants are desired, certain transformations can be made that would otherwise be impermissible. For example, polynomials with non-unitary content $c$ can be reduced to either $\{c\}$ or $\emptyset$ as appropriate. Broadening slightly to binary quadratic polynomials, parity substitutions can be made: $$x^2+2y^2\mapsto (2x+1)^2+2y^2$$


text:
Decision Tree

# Decision Tree

Donny
March 16, 2019
March 18, 2019
1037
-

Tags in blue are handcrafted tags; Tags in green are generated using AutoTag.

## Information Content

$$I(X) = log_b(\frac{1}{P(X)})$$

where,

• I : the information content of X. An X with greater I value contains more information.

• P : the probability mass function.

• $$log_b$$ : b is the base of the logarithm used. Common values of b are 2 (bits), Euler's number e (nats), and 10 (bans).

## Entropy (Information Theory)[1]

$$H(X) = E[I(X)] = E[-log(P(X))]$$

where,

• H : the entropy H. Named after Boltzmann's H-theorem (but the definition is proposed by Shannon). H indicates the uncertainty of X.

• P : probability mass function.

• I : the information content of X.

• E : the expected value operator.

The entropy can explicitly be written as:

$$H(X) = - \sum_{i=1}^{n}{ P(x_i) log_b{P(x_i)} }$$

## ID3[2]

Use ID3 to build a decision tree:

1. Calculate the entropy $$E_0$$ of the samples under the current node.

2. Find a feature F that can maximize the information gain. The information gain is calculatd by:

$$\Delta{E} = E - E_0$$

where E is the entropy of the samples after being seperated by the feature F with the value V.

3. Use the feature F to seperate samples.

4. Repeat step 1 and 2 until the classification result is satisfactory.

Except from Shannon's Entropy, other measures can also be used to measure the impurity of the samples, such as Gini Impurity (aka. Square Impurity).

Gini Impurity:

\begin{align*} I(N) &= \sum_{m \neq n}{ P(\omega_m) P(\omega_n) } \\ &= 1 - \sum_{j=1}^{k}{ P^2(\omega_j) } \end{align*}

## ID4.5[2]

In ID4.5, Information Gain Ratio is used instead of Information Gain.

$$\Delta{E_R(N)} = \frac{ \Delta{E(N)} }{E(N)}$$

### Continuous Values

ID4.5 supports features with continuous values by dividing the samples into two group with every possible value from the samples. Then chooses the division that maximize the Information Gain Ratio, and compares it with the other features' Information Gain Ratio.

### Missing Values

Given all samples (in this node) as set $$D$$, samples with property $$a$$ (in this node) as set $$\tilde{D}$$.

If the weight of each sample $$x$$ is $$\omega_x$$ (the initial weight is 1), we define:

\begin{align*} \rho &= \frac{ \sum_{ x \in \tilde{D} }{ \omega_x } }{ \sum_{ x \in D }{ \omega_x } } \\ \tilde{p}_k &= \frac{ \sum_{ x \in \tilde{D}_k }{ \omega_x } }{ \sum_{ x \in \tilde{D} }{ \omega_x } } \quad ( 1 <= k <= |\gamma| ) \\ \tilde{r}_v &= \frac{ \sum_{ x \in \tilde{D}^v }{ \omega_x } }{ \sum_{ x \in \tilde{D} }{ \omega_x } } \quad ( 1 <= v <= V ) \end{align*}

where,

• $$\rho$$ : the ratio of the weight of samples in $$\tilde{D}$$ against the weight of all samples (in this node).

• $$\tilde{p}_k$$ : the ratio of the weight of samples in $$\tilde{D}$$ that belongs to class k against the weight of samples in $$\tilde{D}$$.

• $$\tilde{r}_v$$ : the ratio of the weight of samples that has value $$a^v$$ for property $$a$$ against the weight of samples in $$\tilde{D}$$.

Then, we can calculate the information gain by:

\begin{align*} Gain(D, a) &= \rho \times Gain(\tilde{D}, a) \\ &= \rho \times ( E(\tilde{D}) - \sum_{v=1}^{V}{ \tilde{r}_v E(\tilde{D}^v) } ) \end{align*}

And the entropy is calculated by:

$$E(\tilde{D}) = - \sum_{k=1}^{|\gamma|}{ \tilde{p}_k log_2{\tilde{p}_k} }$$

## Cutting Decision Trees (CDT)[2]

We can cut a decision tree after it is built, or while it is being built.

Cutting a decision tree under construction means that if adding a child to a node will result in reducing in accuracy on validation set, no child will be added, and the node will turn into a leaf.

Cutting a decision tree after it is constructed:

1. First generate a decision tree from the training set.

2. Check each node, remove it if the accuracy on the validation set will improve without it.

## CART (Classification And Regression Tree)

CART in regression:

Given a set of samples $$X$$, and corresponding ground true outputs $$y$$.

1. For a feature $$F$$, choose a value $$V_m$$, which divides the samples into two groups (one lager than value $$V_m$$, one smaller or equal to value $$V_m$$). The output for group $$G_j$$ is set to $$f_j$$.

2. Choose the feature $$F$$ and the value $$V_m$$ and the outputs $$f_j$$ that minimizes the square loss:

\begin{align*} & F, V_m, f_j = argmin_{F, V_m, f_j}( L(X) ) \\ & where, \\ & L(X) = \sum_{i=0}{N}{ (y_i - f(x_i))^2 } \\ & N = |X| (the number of samples in X) \\ & f(x_i) = f_j (x_i \in G_j) \\ \end{align*}

It's obvious that $$f_j$$ should be the average of the outputs for samples in group $$G_j$$:

$$f_j = ave(y_i | x_i \in G_j)$$

So we just need to loop through features and possible values to find $$F$$ and $$V_m$$.

The algorithm:

import numpy as np

def CART_next_node(X, Y):
samples_count, features_count = np.shape(X)

best_F = np.nan; best_V = np.nan; min_L = np.inf
for F in range(0, features_count):
XF = X[:, F]

min_V = np.nan; min_Lv = np.inf
for V in XF:
if (XF <= V).all(): continue
f1 = np.average(Y[XF <= V])
f2 = np.average(Y[XF > V])
Lv = np.sum([
np.square( y - (lambda x: (f1 if x <= V else f2))(x) )
for x, y in zip(XF, Y)
])
if Lv < min_Lv:
min_V = V
min_Lv = Lv

if min_Lv < min_L:
best_F = F
best_V = min_V
min_L = min_Lv

return best_F, best_V, min_L

A test result:

This (CART) yields piecewise constant models. Although they are simple to interpret, the prediction accuracy of these models often lags behind that of models with more smoothness.

It can be computationally impracticable, however, to extends this approach to piecewise linear models, because two linear models (one for each child node) must be fitted for every candidate split.

(So there is M5', an adaptation of a regression tree algorithm by Quinlan, which uses a more computationally efficient strategy to construct piecewise linear models.)

— Wei-Yin Loh.
(2011). Classification and regression trees.[3]

## Reference

1. More information can be found on Entropy (Information Theory) - Wikipedia.

2. Chapter 4: Decision Tree. Zhihua, Zhou. (2016). Machine Learning. Tsinghua University Press.

3. Regression trees. Wei-Yin Loh. (2011). Classification and regression trees. John Wiley & Sons, Inc.

4. Source of the banner poster.


text:
# Are there subexponential algorithms for PLANAR SAT known?

Some NP-hard problems which are exponential on general graphs are subexponential on planar graphs because the treewidth is at most $4.9 \sqrt{|V(G)|}$ and they are exponential in the treewidth.

Basically I am interested if there are subexponential algorithms for PLANAR SAT which is NP-complete.

Let $\phi$ be a CNF formula on variables $x_i$ and the $i$-th clause is $c_i$.

The incidence graph p. 5 $G$ of $\phi$ is on vertices $V(G)=\{x_i\} \cup \{c_i\}$ and edges $(x_i,c_i)$ iff $x_i \in c_i$ or $\lnot x_i \in c_i$.

$\phi$ is in PLANAR SAT if the incidence graph is planar.

Are there subexponential algorithms for PLANAR SAT in terms of $\phi$?

I don't exclude the possibility reduction SAT to PLANAR SAT to make this possible, though SAT still to be exponential and $\phi$ is subexponential because of the increase in the size.

• There is an extra condition in the definition of PLANAR SAT, the variables must be connected with a cycle through them. What you have described is known as PLANAR* SAT. Mar 21 '15 at 21:43
• @domotorp I think I cited correctly and the paper claims the graph is bipartite. Maybe in other papers the same name is used for something else.
– joro
Mar 22 '15 at 13:25
• Well, you can apply the planar separator theorem together with dynamic programming and get running time $2^{O( \sqrt{n})}$, where $n$ is the number of vertices in the graph. I assume you want something better? Mar 23 '15 at 4:35
• @SarielHar-Peled Yours will be an answer, don't need something better (though better is welcome). Bugs me different formulas might have the same graph -- negate a literal.
– joro
Mar 23 '15 at 5:30
• The standard reduction from SAT to planar SAT shows that under the exponential time hypothesis, $2^{o(\sqrt{n})}$ is impossible, so the algorithm from Sariel's comment is optimal up to constants in the exponent. (this is for what domotorp calls PLANAR* SAT though, but i'm pretty sure the lower bound can be shown for PLANAT SAT too) Mar 24 '15 at 22:31

Well, you can apply the planar separator theorem together with dynamic programming and get running time $2^{O(\sqrt{n})}$, where $n$ is the number of vertices in the graph. The idea being that you try all possible assignments for the variable vertices on the separator, and all variables mentioned in clauses in the separator (assuming each clause has a constnat number of variables).
• More generally it is well-known that if the incidence graph of a SAT formulat has treewidth at most $k$ then one can check satisfiability in $2^{O(k)} poly(|\phi|)$ time. Planar graphs with $n$ vertices are guaranteed to have treewidth $O(\sqrt{n})$ due to the planar separator theorem. More generally graphs that exclude any fixed graph $H$ has a minor have treewidth $O(\sqrt{n})$ where the constant depends on size of $H$. Mar 26 '15 at 23:47
• Indeed, if the formula has $n$ variables and $m$ clauses then the treewidth is at most $O(\sqrt{n})$ (as opposed to the more crude $O(\sqrt{n+m})$ bound). The $O(\sqrt{n})$ upper bound follows from the fact hat the variables are a vertex cover of the incidence graph, and planar graphs with a vertex cover of size $n$ have treewidth $O(\sqrt{n})$. Mar 27 '15 at 23:07


text:
# Thread: Complex Analysis (A Few Clarifying Questions On Practice Problems)

1. ## Complex Analysis (A Few Clarifying Questions On Practice Problems)

I am having a few issues with Complex Analysis. I've done as much as I could on a few practice problems hoping I would understand it but I'm a bit stuck.

1) Find a parameterization of the line segment joining $\small 2i$ and $\small 1+i$. Find the image of the segment under the mapping $\small f(z)=i\bar{z}$.
This is what I did:
$\small z_{o} = 2i$ and $\small z_{1} = 1+i$
$\small z(t)=z_{0}(1+t)+z_{1}t$ for $\small 0\leq t\leq 1$
$\displaystyle =2i(1-t)+(1+t)i$
$\displaystyle =2i-2t+i-1$
$\displaystyle =3i-2it-1$
$\displaystyle f(z)=i(\bar{3i-2it-1})$
$\displaystyle =i(\bar{-1+3-2t)i})$
$\displaystyle =i(-1-(3-2t)i)$
$\displaystyle =i(-1-(3i-2it))$
$\displaystyle =i(-1-3i+2it)$
$\displaystyle =-i-3i^{2}+2i^{2}t$
$\displaystyle =-i+3-2t$ for $\displaystyle 0\leq t \leq 1$

The graph doesn't look look right. I've reworked it a few times and I keep getting the same answer. Am I making a silly algebraic mistake somewhere?

2)Find the image $\displaystyle S'$ of the set $\displaystyle S$ under the given complex mapping $\displaystyle w=f(z)$
$\displaystyle f(z)=\bar{z}$; $\displaystyle S$ is the line $\displaystyle y=x$

A friend told me to do it this way:
$\displaystyle Re(z)=Im(z)$ $\displaystyle \therefore$ $\displaystyle w=\bar{z}=Re(z)=-Im(z)$
Is this correct?

I'll just submit the two problems I'm having the most problem with. Thanks for looking at this.

2. ## Re: Complex Analysis (A Few Clarifying Questions On Practice Problems)

Originally Posted by DrKittenPaws
I am having a few issues with Complex Analysis. I've done as much as I could on a few practice problems hoping I would understand it but I'm a bit stuck.

1) Find a parameterization of the line segment joining $\small 2i$ and $\small 1+i$. Find the image of the segment under the mapping $\small f(z)=i\bar{z}$.
This is what I did:
$\small z_{o} = 2i$ and $\small z_{1} = 1+i$
$\small z(t)=z_{0}(1+t)+z_{1}t$ for $\small 0\leq t\leq 1$
$\displaystyle =2i(1-t)+(1+t)i$
$\displaystyle =2i-2t+i-1$
$\displaystyle =3i-2it-1$
$\displaystyle f(z)=i(\bar{3i-2it-1})$
$\displaystyle =i(\bar{-1+3-2t)i})$
$\displaystyle =i(-1-(3-2t)i)$
$\displaystyle =i(-1-(3i-2it))$
$\displaystyle =i(-1-3i+2it)$
$\displaystyle =-i-3i^{2}+2i^{2}t$
$\displaystyle =-i+3-2t$ for $\displaystyle 0\leq t \leq 1$

The graph doesn't look look right. I've reworked it a few times and I keep getting the same answer. Am I making a silly algebraic mistake somewhere?

2)Find the image $\displaystyle S'$ of the set $\displaystyle S$ under the given complex mapping $\displaystyle w=f(z)$
$\displaystyle f(z)=\bar{z}$; $\displaystyle S$ is the line $\displaystyle y=x$

A friend told me to do it this way:
$\displaystyle Re(z)=Im(z)$ $\displaystyle \therefore$ $\displaystyle w=\bar{z}=Re(z)=-Im(z)$
Is this correct?

I'll just submit the two problems I'm having the most problem with. Thanks for looking at this.

the parameterization of the segment is simply

$2\imath + (1-\imath)t~~0\leq t \leq 1$

try redoing the problem with this.

3. ## Re: Complex Analysis (A Few Clarifying Questions On Practice Problems)

Originally Posted by romsek
the parameterization of the segment is simply

$2\imath + (1-\imath)t~~0\leq t \leq 1$

try redoing the problem with this.
Well, that was dumb of me. Let me try to work it out again and I'll get back to ya on what I got. Thanks!

4. ## Re: Complex Analysis (A Few Clarifying Questions On Practice Problems)

Originally Posted by DrKittenPaws
I am having a few issues with Complex Analysis. I've done as much as I could on a few practice problems hoping I would understand it but I'm a bit stuck.

1) Find a parameterization of the line segment joining $\small 2i$ and $\small 1+i$. Find the image of the segment under the mapping $\small f(z)=i\bar{z}$.
This is what I did:
$\small z_{o} = 2i$ and $\small z_{1} = 1+i$
$\small z(t)=z_{0}(1+t)+z_{1}t$ for $\small 0\leq t\leq 1$
$\displaystyle =2i(1-t)+(1+t)i$
$\displaystyle =2i-2t+i-1$
$\displaystyle =3i-2it-1$
$\displaystyle f(z)=i(\bar{3i-2it-1})$
$\displaystyle =i(\bar{-1+3-2t)i})$
$\displaystyle =i(-1-(3-2t)i)$
$\displaystyle =i(-1-(3i-2it))$
$\displaystyle =i(-1-3i+2it)$
$\displaystyle =-i-3i^{2}+2i^{2}t$
$\displaystyle =-i+3-2t$ for $\displaystyle 0\leq t \leq 1$

The graph doesn't look look right. I've reworked it a few times and I keep getting the same answer. Am I making a silly algebraic mistake somewhere?

2)Find the image $\displaystyle S'$ of the set $\displaystyle S$ under the given complex mapping $\displaystyle w=f(z)$
$\displaystyle f(z)=\bar{z}$; $\displaystyle S$ is the line $\displaystyle y=x$

A friend told me to do it this way:
$\displaystyle Re(z)=Im(z)$ $\displaystyle \therefore$ $\displaystyle w=\bar{z}=Re(z)=-Im(z)$
Is this correct?

I'll just submit the two problems I'm having the most problem with. Thanks for looking at this.

You should have $z_0(1 - t)$ and not $z_0(1 + t)$.

For your second problem, you have the elements on your line are complex numbers of the form: $z = x + ix$.

From this, we see that the images are of the form: $f(z) = \overline{z} = \overline{x+ix} = x - ix$, so that these lie on the line $y = -x$.

5. ## Re: Complex Analysis (A Few Clarifying Questions On Practice Problems)

Originally Posted by DrKittenPaws
I am having a few issues with Complex Analysis. I've done as much as I could on a few practice problems hoping I would understand it but I'm a bit stuck.
1) Find a parameterization of the line segment joining $\small 2i$ and $\small 1+i$. Find the image of the segment under the mapping $\small f(z)=i\bar{z}$.
Consider a vector approach. Express the points a vectors.
$(0,2)~\&~(1,1)\\(0,2)+t(1,-1),~0\le t\le 1\\(t,2-t),~0\le t\le 1\\t+i(2-t),~0\le t\le 1$
that is the parameterzation of the line segment.