This paper discusses the universal approximation theorem which states: There is a single hidden layer feedforward network that approximates any measurable function to any desired degree of accuracy.

For any unknown function $f(x)$ there exists a single hidden layer feedforward network $F(x)$ such that $  | F( x ) - f ( x ) | < \epsilon$ for some number of hidden units. 

$F(x)$ takes the following form where $h$ is some nonlinear activation function (relu, tanh, sigmoid). $w_i$ is a vector and $b_i$ and $v_i$ are scalars.

$$  F( x ) =
  \sum_{i=1}^{N} v_i h( w_i x + b_i)$$


Resources: 

http://deeplearning.cs.cmu.edu/notes/Sonia_Hornik.pdf

http://neuralnetworksanddeeplearning.com/chap4.html

This paper, by Yahoo, describes a new language called Pig Latin which is intended to provide a middle ground between declarative SQL-style language (which many developers find unnatural) and procedural map-reduce model (which is very low-level and rigid). It also introduces a novel, interactive debugging environment called Pig Pen.

#### Overview
A Pig Latin program is a sequence of steps — each step carrying out a single high-level transformation. Effectively the program specifies the query execution plan itself. The program then compiles into map-reduce jobs which are run on Hadoop (though other backends can also be plugged in). Pig Latin is more expressive than map-reduce which is essentially limited to use a one-input, two-stage data flow model. Moreover, since the map and reduce functions are opaque for each other, optimizations are hard to bake in the system itself. This limitation is also overcome with Pig Latin which allows the programmer to order the execution of individual steps by specifying the execution plan.
Unlike traditional DBMS, Pig does not require data to be imported into system managed tables as it meant for offline, ad-hoc, scan-centric, read-only workloads. Pig supports User Defined Functions (UDFs) out of the box. Since it targets only parallel processing, there is no inbuilt support for operations like non-equi joins or correlated subqueries. These operations can still be performed using UDFs.

#### Nested Data Model
Pig supports a flexible, nested data model with 4 supported types-

1. Atom: Simple values like string or integer. eg ‘medium’
2. Tuple: Sequence of ‘fields’ which can be of any type. eg (‘medium’, 12)
3. Bag: Collection of tuples. eg {(‘medium’, 12), ((‘github’, ‘twitter’), 12)}
4. Map: Collection of key-value pairs where keys are atoms and values can be any type. eg [‘key’ -> ‘value’, ‘anotherKey’ -> (‘another’, ‘value’)]

#### Inbuilt functions
1. FOREACH — Specifies how each tuple is to be processed. The semantics require that there should be no dependence between processing of different input tuples to allow parallel processing.
2. COGROUP — Suppose we have two datasets:
result = (query, url) //a query and its result url
revenue = (query, amount) //a query and revenue generated by the query.
Cogrouping these two datasets, we get
grouped_data = COGROUP results BY query, revenue BY query.
grouped_data would contain one tuple for each group. The first field of the tuple is the group identifier and the other fields are bags — one for each dataset being cogrouped.So 1st bag would correspond to results and other to revenue. A sample dataset has been shown here.
COGROUP is one level lower than JOIN as it only groups together tuples into nested bags. It can be followed by an aggregate operation or cross product operation (leading to the result expected from JOIN operation). GROUP is same as COGROUP on a single dataset.
3. Nested Operations where commands can be nested within FOREACH command to process bags within tuples.

Other functions include — LOAD, STORE, FILTER, JOIN, CROSS, DISTINCT, UNION and ORDER and are similar in operation to equivalent SQL operations.
It may be argued as to how does Pig differ from SQL-style query language when it seems to be using similar operations. Compare the following queries which generate the same result. The first one is written in SQL (declarative) and other in Pig (procedural)

    SELECT category, AVG(pagerank) FROM urls WHERE pagerank > 0.2 GROUP BY category HAVING COUNT(*) > 106
    good_urls = FILTER urls BY pagerank > 0.2;
    groups = GROUP good_urls BY category;
    big_groups = FILTER groups BY COUNT(good_urls)>106 ;
    output = FOREACH big_groups GENERATE category, AVG(good_urls.pagerank);

#### Implementation
The Pig interpreter parses the commands and verifies that the referred input files and bags are valid. It then builds a logical plan for every bag that is being defined using the logical plans for the input bags, and the current command. These plans are evaluated lazily to allow for in-memory pipelining and filter reordering. The parsing and logical plan construction are independent of the execution platform while the compilation of the logical plan into a physical plan depends on the execution platform.
For each COGROUP command, the compiler generates a map-reduce job where the map function assigns keys for grouping and the reduce function is initially a no-op. The commands intervening between two subsequent COGROUP commands A and B are pushed into the reduce function of A to reduce the amount of data to be materialized between different jobs. The operations before the very first COGROUP operation are pushed into the map function of A. The ORDER command compiles into two map-reduce jobs. The first job samples the input data to determine quantiles of the sort key. The second job range-partitions the input data according to the quantiles to provide equal-sized partitions, followed by local sorting in the reduce phase, resulting in a globally sorted file.

The inflexibility of the map-reduce primitive results in some overheads while compiling Pig Latin into map-reduce jobs. For example, data must be materialized and replicated on the distributed file system between successive map-reduce jobs. When dealing with multiple data sets, an additional field must be inserted in every tuple to indicate which data set it came from. However, the Hadoop map-reduce implementation does provide many desired properties such as parallelism, load balancing, and fault-tolerance. Given the productivity gains to be had through Pig Latin, the associated overhead is often acceptable. Besides, there is the possibility of plugging in a different execution platform that can implement Pig Latin operations without such overheads.

Since the files reside in the Hadoop distributed file system, LOAD operation can run in parallel. Similarly, parallelism is achieved for FILTER and FOREACH operation as any map-reduce job runs several map and reduce instances in parallel. COGROUP operation runs in parallel by re-partitioning the output from multiple map instances to multiple reduce instances.

To achieve efficiency when working with nested bags, Pig uses Hadoop’s combiner function to achieve a two-tier tree evaluation of algebraic functions. So all UDFs, of algebraic nature, benefit from this optimization. Of course, non-algebraic functions can not take advantage of this.

#### Pig Pen
It is the interactive debugging environment that also helps to construct Pig Latin program. Typically the programmer would write the a program and run it on a dataset, or a subset of the dataset (if running over the entire dataset is too expensive) to check for correctness and change the program accordingly. Pig Pen can dynamically create a side data set (a subset of the complete dataset), called sandbox dataset, that can be used to test the program being constructed. This dataset is aimed to be real (ie subset of actual data), concise and complete(illustrate the key semantics of each command). While the paper does not go into the depth of how this dataset is created, it does mention that it starts by taking small, random samples of base data and synthesizes additional data tuples to improve completeness.

Within Yahoo, Pig Latin has been used in a variety of scenarios like computing rollup aggregates and performing temporal and session analysis. While Pig Latin does provide a powerful nested data model and supports UDFs making it easier to write and debug map-reduce jobs, it does not deal with issues like materializing and replicating data between successive map-reduce jobs. The paper argues that this overhead is acceptable given the numerous advantages Hadoop offers. Pig has come a long way since the paper was written. A lot of new functions have been added and it now comes with an interactive shell called Grunt. Moreover, now UDFs can be written in various scripting languages and not just Java. All these changes have made Pig more powerful and accessible than before.

The propagation rule used in this paper is the following:

$$
H^l = \sigma \left(\tilde{D}^{-\frac{1}{2}} \tilde{A} \tilde{D}^{-\frac{1}{2}} H^{l-1} W^l \right)
$$

Where $\tilde{A}$ is the [adjacency matrix][adj] of the undirected graph (with self connections, so has a diagonal of 1s and is symmetric) and $H^l$ are the hidden activations at layer $l$. The $D$ matrices are performing row normalisation, $\tilde{D}^{-\frac{1}{2}} \tilde{A} \tilde{D}^{-\frac{1}{2}}$ is [equivalent to][pygcn] (with $\tilde{A}$ as `mx`):

```
rowsum = np.array(mx.sum(1))            # sum along rows
r_inv = np.power(rowsum, -1).flatten()  # 1./rowsum elementwise
r_mat_inv = sp.diags(r_inv)             # cast to sparse diagonal matrix
mx = r_mat_inv.dot(mx)                  # sparse matrix multiply
```

The symmetric way to express this is part of the [symmetric normalized Laplacian][laplace]. This work, and the [other][hammond] [work][defferrard] on graph convolutional networks, is motivated by convolving a parametric filter over $x$. Convolution becomes easy if we can perform a *graph Fourier transform* (don't worry I don't understand this either), but that requires us having access to eigenvectors of the normalized graph Laplacian (which is expensive).

[Hammond's early paper][hammond] suggested getting around this problem by using Chebyshev polynomials for the approximation. This paper takes the approximation even further, using only *first order* Chebyshev polynomial, on the assumption that this will be fine because the modeling capacity can be picked up by the deep neural network.

That's how the propagation rule above is derived, but we don't really need to remember the details. In practice $\tilde{D}^{-\frac{1}{2}} \tilde{A} \tilde{D}^{-\frac{1}{2}} = \hat{A}$ is calculated prior and using a graph convolutional network involves multiplying your activations by this sparse matrix at every hidden layer. If you're thinking in terms of a batch with $N$ examples and $D$ features, this multiplication happens *over the examples*, mixing datapoints together (according to the graph structure). If you want to think of this in an orthodox deep learning way, it's the following:

```
activations = F.linear(H_lm1, W_l)         # (N,D)
activations = activations.permute(1,0)     # (D,N)
activations = F.linear(activations, hat_A) # (D,N)
activations = activations.permute(1,0)     # (N,D)
H_l = F.relu(activations)
```

**Won't this be really slow though, $\hat{A}$ is $(N,N)$!** Yes, if you implemented it that way it would be very slow. But, many deep learning frameworks support sparse matrix operations ([although maybe not the backward pass][sparse]). Using that, a graph convolutional layer can be implemented [quite easily][pygcnlayer].

**Wait a second, these are batches, not minibatches?** Yup, minibatches are future work.

**What are the experimental results, though?** There are experiments showing this works well for semi-supervised experiments on graphs, as advertised. Also, the many approximations to get the propagation rule at the top are justified by experiment.

**This summary is bad.** Fine, smarter people have written their own posts: [the author's][kipf], [Ferenc's][ferenc].

[adj]: https://en.wikipedia.org/wiki/Adjacency_matrix
[pygcn]: https://github.com/tkipf/pygcn/blob/master/pygcn/utils.py#L56-L63
[laplace]: https://en.wikipedia.org/wiki/Laplacian_matrix#Symmetric_normalized_Laplacian
[hammond]: https://arxiv.org/abs/0912.3848
[defferrard]: https://arxiv.org/abs/1606.09375
[sparse]: https://discuss.pytorch.org/t/does-pytorch-support-autograd-on-sparse-matrix/6156/7
[pygcnlayer]: https://github.com/tkipf/pygcn/blob/master/pygcn/layers.py#L35-L68
[kipf]: https://tkipf.github.io/graph-convolutional-networks/
[ferenc]: http://www.inference.vc/how-powerful-are-graph-convolutions-review-of-kipf-welling-2016-2/

This paper describes the Bitcoin peer-to-peer currency system.

The paper first describes a bitcoin as a chain of transactions, the latest of which contains the current owner's public key, and is cryptographically signed by the previous owner.  The integrity of this chain (and therefore the ownership of the coin) is maintained as each transaction contains a hash of the previous transaction.  Therefore, it is impossible to corrupt any one transaction in the chain without affecting all future transactions as well.

https://i.imgur.com/hKbgsdi.png

The key issue with this system is *double counting* in a peer-to-peer environment.  In physical currency, this problem does not exist, as the purchase using a physical token precludes using the same token by the same owner again.  In other digital currencies, the problem of double counting is solved using a central arbiter.

The authors solve this using a timestamp service, which stamps a block of transactions.  The transaction which have the earliest timestamp is used as the true transaction.  The block of transactions is linked to a previous block, thereby forming a *blockchain*.

https://i.imgur.com/BYlVirg.png

To prevent the integrity of the blockchain, each block contains the previous hash, thereby ensuring the integrity of the chain.  There is also a nonce value, which is an input to a computationally difficult problem which must be solved in order to place a new block in the blockchain.  This makes it difficult for an attacker to tack on a new chain.  

The problem that must be solved is to increment the nonce such that the hash of the block contains a specified number of 0 bits.  The difficulty of this problem can be adjusted by increasing the number of 0's, and grows over time to accommodate the growing power of computer hardware.  Note that verifying that this problem is easily solved.

The resulting blockchain therefore constitutes a large investment of computational resources, with the longest blockchain being used as the standard.

Not all participants in bitcoin need to mine, so an incentive is given.  When a new block is mined, the individual who mines it is given some portion of bitcoin either out of thin-air or as a transaction fee.  This also deters would-be corruptors of the blockchain, as the computational resources needed may be better spent adding new blocks on the newest version of the blockchain.

This paper discusses the impact of the Affordable Care Act (ACA) on the United States. First there is discussion regarding what led up to health care reform followed by the impacts of the bill and the current trends. 

One motivation was that the "US system left more than 1 in 7 Americans without health insurance coverage in 2008." Also, there was an upward trend in how much the economy was spending on healthcare. 

The first results are shown in Figure 1. The number of uninsured dropped after the ACA. Maybe this is the most significant take away but it doesn't capture the quality and cost of care which are also addressed in the paper.

![](https://i.imgur.com/qrQ7nU9.png)

The paper states "Before the ACA, the health care system was dominated by 'fee-for-service' payment systems, which often penalized health care organizations and health care professionals who find ways to deliver care more efficiently, while failing to reward those who improve the quality of care. The ACA has changed the health care payment system in several important ways." 

The ACA modified payments for medicare services and introduced a "value-based payment" system with the goal of reducing overall cost. This is shown in Figure 4. What the plot is showing is the change over a time period. Between 2000-2005 the costs per payer were increasing in all programs. Between 2005-2010 medicaid cost to the person was decreasing and the other programs were still growing but growing slower. Between 2010-2014 the cost to both medicare and medicaid are both in decline. Private insurance costs are still increasing but they are increasing slower than before.

![](https://i.imgur.com/knBTQxK.png)

Another interesting take away is that "[t]he rate of hospital-acquired conditions (such as adverse drug events, infections, and pressure ulcers) has declined by 17%." This is reflected in the 30-day readmission rates dropping shown in Figure 6.

![](https://i.imgur.com/SmcxfoB.png)